HPC. La versión paralela del método de la patente US 8266089.

La paralelización del método de la patente US 8266089 es evidente para cualquiera skilled in the art e igual no hacía falta publicar nada al respecto (como se verá es prácticamente idéntico al método secuencial, iniciando varios hilos en paralelo que implementan éste, intercalando en cada etapa la subrutina que ya existe de coherencia gloabal). Pero en caso de que el lector se quiera ahorrar el mínimo esfuerzo que pueda requerir el obtener una idea de la versión paralela, lo hacemos nosotros por él.

La versión paralela ya está en formato papel y se publicará en breve en el blog.

Se pueden paralelizar varios pasos del método. Adelantamos la idea principal de la fase de búsqueda una vez que ya está construido el dígrafo y el conjunto de IASes, una vez que el vértice final e inicial ya están marcados, que se ha activado el IAS inicial y se han extraído todas las consecuencias de ésta activación. Quede claro que todas éstas operaciones iniciales también se pueden paralelizar. En lo que sigue nos centramos en la aplicación a un caso smooth.

En la patente, una vez realizados los pasos preliminares, hemos planteado una búsqueda secuencial: elegir la primera opción (primer arco), sacar las consecuencias correspondientes de ésta primera opción (activar los IASes correspondientes a éste arco, comprobar que al marcar éste arco o los de  sus IASes correspondientes no se genera ni un ciclo no hamiltoniano ni un camino no hamiltoniano que comience por el vértice final y termine en el vértice inicial), elegir la segunda opción (marcar el segundo arco), sacar las consecuencias correspondientes a ésta segunda opción etc…

La alternativa paralela, tras la fase inicial, consiste en elegir varias opciones a la vez (marcar varios arcos iniciales, uno del vértice inicial, otro del vértice final y otros elegidos, por ejemplo al azar o de otro modo, con elecciones equilibradas entre los dos generadores en función de su orden, más de los de mayor orden; independientemente de la manera de elegirlos lo mejor es que estén distribuidos de manera espaciada en el dígrafo) en paralelo de manera independiente, a la vez, y extraer las consecuencias de cada una de las elecciones. En general, si el dígrafo es grande y smooth (como estamos suponiendo) y los arcos elegidos se han espaciado, las consecuencias serán locales y compatibles entre ellas hasta que se hayan marcado una mayoría de arcos.

En cualquier caso se debe de añadir  una subrutina (que de alguna manera ya se aplicaba en el en el algoritmo secuencial, y vale la misma (paralelizada), que se podrá incluir desde el principio tras las primeras elecciones paralelas o más adelante, en el  momento en el que se considere que ya hay una cantidad crítica de arcos marcados como para que emerjan contradicciones entre las elecciones), una subrutina decimos que haga una comprobación global de que estas activaciones de arcos o elecciones son compatibles entre ellas, que no generan contradicción y si generasen contradicción marcar otros arcos alternativos tal que se eviten  éstas contradicciones.

Hay que determinar cual es el número óptimo de opciones que se puede marcar a la vez en el primer ciclo o etapa. El equilibrio está en que al marcar un número determinado de opciones en paralelo no se pierda luego más tiempo en aplicar la subrutina  que las haga compatibles.

Cada arco marcado inicialmente en esta primera etapa genera un hilo paralelo,  y a cada uno de éstos hilos se empieza a aplicar el algoritmo secuencial de manera independiente, eligiendo opciones y extrayendo las consecuencias de éstas, alternando en cada etapa la subrutina de coherencia global (que de alguna manera ya se hacía en el algoritmo secuencial).

Al final el resultado es el mismo que el algoritmo secuencial o se obtiene un recorrido hamiltoniano o la prueba de que éste no existe. Por supuesto con ésta paralelización, se acelerará brutalmente el proceso de búsqueda de soluciones.

Entrada comenzada en la fecha de publicación y actualizada el día 26 de junio de 2015 a las 21:00.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: