Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs

TLDR

The paper proposes a parallel multilevel k‑way graph partitioning algorithm. The algorithm achieves high concurrency while preserving partition quality, with runtime only marginally longer than the graph redistribution step. Experiments on finite‑element graphs demonstrate that the parallel algorithm produces high‑quality partitions in seconds—e.g., a 128‑way partition of a one‑million‑vertex graph in just over two seconds—while maintaining edge‑cut quality within 5% of the serial method, making frequent repartitioning practical.

Abstract

In this paper we present a parallel formulation of a multilevel k-way graph partitioning algorithm. A key feature of this parallel formulation is that it is able to achieve a high degree of concurrency while maintaining the high quality of the partitions produced by the serial multilevel k-way partitioning algorithm. In particular, the time taken by our parallel graph partitioning algorithm is only slightly longer than the time taken for re-arrangement of the graph among processors according to the new partition. Experiments with a variety of finite element graphs show that our parallel formulation produces high-quality partitionings in a short amount of time. For example, a 128-way partitioning of graphs with one million vertices can be computed in a little over two seconds on a 128-processor Cray T3D. Furthermore, the quality of the partitions produced is comparable (edge-cuts within 5%) to those produced by the serial multilevel k-way algorithm. Thus our parallel algorithm makes it feasible to perform frequent repartitioning of graphs in dynamic computations without compromising the partitioning quality.