Parallel multilevel algorithms for hypergraph partitioning

Aleksandar Trifunović

doi:10.1016/j.jpdc.2007.11.002

Return

Parallel multilevel algorithms for hypergraph partitioning

2008-05-01

Aleksandar Trifunović

William J. Knottenbelt

DOI：10.1016/j.jpdc.2007.11.002

Original

Save

View PDF

Abstract

En 中文

In this paper, we present parallel multilevel algorithms for the hypergraph partitioning problem. In particular, we describe for parallel coarsening, parallel greedy k-way refinement and parallel multi-phase refinement. Using an asymptotic theoretical performance model, we derive the isoefficiency function for our algorithms and hence show that they are technically scalable when the maximum vertex and hyperedge degrees are small. We conduct experiments on hypergraphs from six different application domains to investigate the empirical scalability of our algorithms both in terms of runtime and partition quality. Our findings confirm that the quality of partition produced by our algorithms is stable as the number of processors is increased while being competitive with those produced by a state-of-the-art serial multilevel partitioning tool. We also validate our theoretical performance model through an isoefficiency study. Finally, we evaluate the impact of introducing parallel multi-phase refinement into our parallel multilevel algorithm in terms of the trade off between improved partition quality and higher runtime cost. (C) 2007 Elsevier Inc. All rights reserved.

Keywords:

parallel hypergraph partitioning

parallel graph partitioning

parallel sparse matrix-vector multiplication

sparse matrix decomposition

load balancing

data partitioning

VLSI circuit design

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.