Computing Publications

Publications Home » Towards a Parallel Disk-Based Alg...

Towards a Parallel Disk-Based Algorithm for Multilevel k-way Hypergraph Partitioning

Aleksandar Trifunovic, William J. Knottenbelt

Conference or Workshop Paper
5th Workshop on Parallel and Distributed Scientific and Engineering Computing

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 (212 kilobytes)
(need help viewing PDF files?)
Postscript of full publication (554 kilobytes)
(need help viewing Postscript files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.