Algoritmos Paralelos Distribuidos para Búsquedas en Profundidad sobre Grafos

FAPITALLE, FEDERICO; VAZQUEZ, GUSTAVO E.; PONZONI, IGNACIO; BRIGNOLE, NÉLIDA B.

Córdoba, Argentina

Congreso; ENIEF 2001, (12º Congreso sobre Métodos Numéricos y sus Aplicaciones); 2001

AMCA (Asociación Argentina de Mecánica Computacional)

En este artículo se presenta un algoritmo paralelo distribuido descentralizado para realizar búsquedas en profundidad de caminos sobre grafos. El método se basa en un nueva arquitectura paralelo distribuida, propuesta en este trabajo, en la cual se distribuyen las tareas de cómputo sobre tres tipos de nodos de procesamiento: el Master, los Supervisors y los Workers. Básicamente, el Master organiza la distribución de los distintos subespacios de búsqueda entre los Supervisores. Cada Supervisor encomienda la exploración de los subcaminos correspondientes a su subespacio a diferentes Workers que están a su cargo. Cada Worker efectúa la exploración de una parte del espacio de búsqueda y le envía a su Supervisor cada uno de los subcaminos hallados. Por último, el Supervisor se encarga de recombinar sus subcaminos con los subcaminos almacenados por otros Supervisores. El nuevo algoritmo fue implementado en lenguaje C utilizando la librería de pasaje de mensajes PVM y su desempeño fue evaluado en términos de eficiencia y speed-up.