Partitioning Graphs on Message-passing Machines by Pairwise Mincut

Abstract

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.

Department(s)

Computer Science

Sponsor(s)

Louisiana Board of Regents
National Science Foundation (U.S.)

Keywords and Phrases

Graph Partitioning; Linear Speedup; Mapping; Parallel Partitioning By Pairwise Mincut; Hypercube

International Standard Serial Number (ISSN)

0020-0255

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1998 Elsevier, All rights reserved.

Publication Date

01 Nov 1998

Link to Full Text

Share

 
COinS