Partitioning Graphs on Message-passing Machines by Pairwise Mincut
Realizing the potential of massively parallel machines requires good solutions to the problem of mapping computations among processors so that execution is load-balanced with low inter-processor communication resulting in low execution time. This problem is typically treated as a graph partitioning problem. We develop a parallel heuristic algorithm for partitioning the vertices of a graph into many clusters so that the number of inter-cluster edges is minimized. The algorithm is designed for message-passing machines such as hypercubes. This algorithm is suitable for use with runtime approaches that have been recently developed for parallelizing unstructured scientific computations. We present a parallelization of the Kernighan-Lin heuristic that starts with an initial random multiway partition and performs pairwise improvements through application of the mincut bisection heuristic, known as Partitioning by Pairwise Mincut (PPM). A novel parallel scheme providing nearly linear speedup is developed for PPM that is optimal in terms of communication.
P. Sadayappan et al., "Partitioning Graphs on Message-passing Machines by Pairwise Mincut," Information Sciences, Elsevier, Nov 1998.
The definitive version is available at http://dx.doi.org/10.1016/S0020-0255(98)10005-1
Louisiana Board of Regents
National Science Foundation (U.S.)
Keywords and Phrases
Graph Partitioning; Linear Speedup; Mapping; Parallel Partitioning By Pairwise Mincut; Hypercube
Article - Journal
© 1998 Elsevier, All rights reserved.