An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations

TLDR

Efficient use of a distributed memory parallel computer requires load balancing that minimizes interprocessor communication. The paper proposes a new domain mapping algorithm that extends spectral graph theory approaches to partition parallel computations. The algorithm generalizes spectral graph bisection by employing multiple eigenvectors for recursive 4‑ or 8‑way decomposition, supports arbitrary nonnegative vertex and edge weights for inhomogeneous workloads, and introduces a new spectral lower bound for graph bisection. Experimental results show the method yields better, more economical, and robust decompositions than previous spectral techniques.

Abstract

Efficient use of a distributed memory parallel computer requires that the computational load be balanced across processors in a way that minimizes interprocessor communication. A new domain mapping algorithm is presented that extends recent work in which ideas from spectral graph theory have been applied to this problem. The generalization of spectral graph bisection involves a novel use of multiple eigenvectors to allow for division of a computation into four or eight parts at each stage of a recursive decomposition. The resulting method is suitable for scientific computations like irregular finite elements or differences performed on hypercube or mesh architecture machines. Experimental results confirm that the new method provides better decompositions arrived at more economically and robustly than with previous spectral methods. This algorithm allows for arbitrary nonnegative weights on both vertices and edges to model inhomogeneous computation and communication. A new spectral lower bound for graph bisection is also presented.