Grid-enabled parallel divide-and-conquer
Chun-Hsi Huang · 2002
This paper presents a general methodology for the communication-efficient parallelization of graph algorithms using the divide-and-conquer approach. The algorithm is communication-free in the conquer stage and uses only a small amount of messages while partitioning the input. Specifically, a practical parallel algorithm with full scalability, based on the BSP model, for finding Hamiltonian paths in tournaments is presented.Experiments have been carried out on two architecturally different systems, which stand for the possible site variety of a computational grid. These include a distributed-memory system: a Solaris cluster of 32 Sun Ultra5 computers on Myrinet network and a distributed shared-memory system: an SGI Origin 2000 with 32 R10000 processors, using MPICH-GM and MPT, respectively. Both implementations are compatible with the grid-enabled MPI implementation, MPICH-G2.