Paralelização da Técnica Branch and Bound com PVM

Abstract

Resumo: Este trabalho aborda a implementação paralela da técnica Branch-and-Bound em problemas de otimização combinatoria, especificamente busca em grafos. E utilizado na implementação o modelo de programação paralela por troca de mensagens com o uso da biblioteca Parallel Virtual Machine (PVM) sobre o sistema operacional Linux em uma arquitetura multicomputador. E analisado o comportamento da técnica Branch-and-Bound, em particular a relação entre (a) três critérios de busca, (b) a utilização dos recursos de memória e (c) granularidade de, processamento e comunicação entre processos. E proposto um esquema de implementação com processos mestre-escravos semi-distribuído, onde o processo mestre é responsável pela distribuição de tarefas e os processos escravos pela disseminação de resultados parciais no sistema. Resultados experimentais dessa implementação são exibidos e analisados, assim como algumas características relevantes ao desempenho global encontradas no uso da biblioteca PVM para esta arquitetura. De um modo geral obtivemos em média para os problemas investigados uma eficiência da execução paralela da ordem de 98% em comparação à execução serial.

Abstract: This work presents a parallel implementation employing the Branch-and-Bound technique for solving combinatorial optimization problems, specifically search in graphs. The implementation is based on message passing, using the Parallel Virtual Machine (PVM) library on top of the Linux operational system on a network of PCs. The behaviour of this implementations of Branch-and-Bound is analyzed,whith emphasis on the relationships between (a) three graph search strategies, (b) memory resources utilization, (c) granularity (computation versus communication). The implementation consists of a master and slave processes. The master process is responsible for allocation of work amongst the slaves, and the slave processes for performing the graph search and communicating the parcial results to the master. We present experimental data of several runs of the program on the network of PCs, and analyse the performance of the implementation. We also discuss several issues related to the global performance attained, and on the use of the PVM library in this architecture. Our implementation achieved up to 98% of eficiency in some of the experiments performed.