loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Aleksandar Trifunovic, Imperial College London
William J. Knottenbelt, Imperial College London
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.