Algoritmos Paralelos Distribuidos para Búsquedas en Profundidad sobre Grafos

Abstract

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.

A descentralized parallel-distributed algorithm to carry out depth-first searches along graphs is presented. The method is based on a new parallel-distributed architecture that is proposed in this article. In this formulation the computing tasks are distributed among three kinds of nodes: the Master, the Supervisors and the Workers. The Master organizes the distribution of the various search subspaces among the Supervisors. In turn, each Supervisor delegates the exploration of the subpaths inside the assigned subspace to the Workers under its control. So, each Worker explores a given part of the search space, sending its Supervisor information about the subpaths it could find. Finally, the Supervisor has to recombine its own subpaths with those stored by the other Supervisors. The new algorithm was implemented in C using the PVM messagepassage library and its performance was evaluated in terms of speed-up and efficiency.