Aleksandar Trifunovic, William J. Knottenbelt

Conference or Workshop Paper

5th Workshop on Parallel and Distributed Scientific and Engineering Computing

2004

Abstract

In this paper we present a disk-based parallel formulation of the multilevel k-way hypergraph partitioning algorithm. This algorithm provides the capability to partition very large hypergraphs that hitherto could not be partitioned since the memory required exceeds that available on a single workstation. The algorithm has three main phases: parallel coarsening, sequential partitioning of the coarsest hypergraph and parallel refinement. At each parallel coarsening and refinement step disk is used to minimise memory usage. We apply the algorithm to very large hypergraphs with Theta(10^7) vertices from the domain of performance modelling and show that the partitioning quality is approximately 20% better in terms of the k-1 metric than approximate partitionings produced by a state of-the-art parallel graph partitioning tool.

PDF of full publication (211.6 kilobytes)

(need help viewing PDF files?)

Postscript of full publication (554.3 kilobytes)

(need help viewing Postscript files?)

Information from pubs.doc.ic.ac.uk/disk-based-parallel-algorithm.