Análisis de Perfomance en el Procesamiento Paralelo sobre Clusters del Problema del Puzzle N2-1

Abstract

En este trabajo se presenta un análisis de la solución paralela del Puzzle N2-1 utilizando clusters. El problema es especialmente interesante por su complejidad y sus posibles aplicaciones, en particular en el campo de la robótica.
Resolver el Puzzle N2-1 es un problema de optimización discreta tipo BFS (Best First Search), cuya complejidad y costo computacional favorecen el desarrollo de soluciones paralelas. Básicamente se trata de evolucionar desde un estado inicial, explorando en paralelo posibles recorridos, hasta alcanzar un estado solución. El número de movimientos requeridos es la función a optimizar.
En el trabajo se desarrolla una variación de la heurística clásica para la distribución de trabajo en el cluster, así como para decidir el avance del procesamiento paralelo en los procesos que se crean dinámicamente.
Posteriormente se presenta la solución paralela sobre cluster y se analiza el speedup alcanzable, en relación con el tiempo del algoritmo secuencial A*.
Un aspecto de interés es la posibilidad de superlinealidad (que surge de la clase de problema paralelo que representan los algoritmos de búsqueda en árboles como A*), así como el análisis de la eficiencia y escalabilidad de la solución distribuida desarrollada.
Se presenta un trabajo experimental con diferentes configuraciones de cluster, así como diferentes dimensiones del problema (variando N) y estados iniciales con distinto grado de desorden (calculado a partir de la distancia de Manhattan modificada).
Por último se discute la generalización del problema, para aplicarlo al movimiento de multi-robots con múltiples objetivos, y se analiza preliminarmente la migración del algoritmo a esquemas multi-cluster o Grid.