18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 13 Towards a Parallel Disk-Based Algorithm for Multilevel k-way Hypergraph Partitioning Santa Fe, New Mexico April 26-April 30 ISBN: 0-7695-2132-0
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 re.nement step disk is used to minimise memory usage. We apply the algorithm to very large hypergraphs with Θ(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.
Citation:
Aleksandar Trifunovic, William J. Knottenbelt, "Towards a Parallel Disk-Based Algorithm for Multilevel k-way Hypergraph Partitioning," ipdps, vol. 14, pp.236b, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 13, 2004 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||