Superlinealidad sobre Clusters : Análisis experimental en el problema del Puzzle N² -1

En este trabajo se analiza la escalabilidad de algoritmos paralelos superlineales ejecutándose sobre arquitecturas de cluster. El caso de estudio es la resolución del problema del Puzzle N² -1 y en él se analiza la implementación de una solución paralela sobre clusters, basada en el algoritmo A*. En particular se presentan resultados que relacionan el speedup en función del número de procesadores en el cluster y se discute la superlinealidad y eficiencia (o seudoeficiencia) alcanzable al escalar la arquitectura y/o la dimensión del problema. Por último se presentan líneas de investigación futuras orientadas a predecir la superlinealidad alcanzable en función del grado de desorden inicial. This paper analyzes the scalability of superlinear parallel algorithms run over cluster architectures. The case study is the resolution of the N² -1 Puzzle problem and, in it, the implementation of a parallel solution over clusters -based on the A* algorithm- is analyzed. In particular, the results relating the speedup in function of the number of processors in the clusters are presented together with a discussion on the superlinearity and efficiency (or pseudo-efficiency) attainable when scaling the architecture and / or the dimension of the problem. Finally, some future research lines, oriented to predicting the attainable superlinearity in function of the initial disorder degree, are presented. VIII Workshop de Procesamiento Distribuido y Paralelo