INVESTIGADORES
BRIGNOLE Nelida Beatriz
artículos
Título:
Algoritmos Paralelos Distribuidos para Búsquedas en Profundidad sobre Grafos
Autor/es:
FAPITALLE, F; VAZQUEZ, G.E; PONZONI, I; BRIGNOLE, N.B
Revista:
Mecánica Computacional
Editorial:
Asociación Argentina de Mecánica Computacional
Referencias:
Año: 2001 p. 468 - 473
ISSN:
1666-6070
Resumen:
En este artículo se presenta un algoritmo paralelo distribuido descentralizado pararealizar búsquedas en profundidad de caminos sobre grafos. El método se basa en unnueva arquitectura paralelo distribuida, propuesta en este trabajo, en la cual sedistribuyen las tareas de cómputo sobre tres tipos de nodos de procesamiento: elMaster, los Supervisors y los Workers. Básicamente, el Master organiza ladistribución de los distintos subespacios de búsqueda entre los Supervisores. CadaSupervisor encomienda la exploración de los subcaminos correspondientes a susubespacio a diferentes Workers que están a su cargo. Cada Worker efectúa laexploración de una parte del espacio de búsqueda y le envía a su Supervisor cada unode los subcaminos hallados. Por último, el Supervisor se encarga de recombinar sussubcaminos con los subcaminos almacenados por otros Supervisores. El nuevoalgoritmo fue implementado en lenguaje C utilizando la librería de pasaje de mensajesPVM y su desempeño fue evaluado en términos de eficiencia y speed-up.
