文章基本信息

标题：Análisis de Perfomance en el Procesamiento Paralelo sobre Clusters del Problema del Puzzle N2-1
本地全文：下载
作者：Victoria Sanz ; Franco Chichizola ; Armando E. De Giusti 等
期刊名称：Mecánica Computacional
印刷版ISSN：2591-3522
出版年度：2008
卷号：XXVII
期号：39
页码：2967-2978
出版社：CIMEC-INTEC-CONICET-UNL
摘要：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.