Current multilevel repartitioning schemes tend to perform well on certain types of problems while obtaining worse results for other types of problems. We present two new multilevel algorithms for repartitioning adaptive meshes that improve the performance of multilevel schemes for the types of problems that current schemes perform poorly while maintaining similar or better results for those problems that current schemes perform well. Specifically, we present a new scratch-remap scheme called Locally-matched Multilevel Scratch-remap (or simply LMSR) for repartitioning of adaptive meshes. LMSR tries to compute a high-quality partitioning that has a large amount of overlap with the original partitioning. We show that LMSR generally decreases the data redistribution costs required to balance the load compared to current scratch-remap schemes. We present a new diffusion-based scheme that we refer to as Wavefront Diffusion. In Wavefront Diffusion, the flow of vertices moves in a wavefront from overweight to underweight subdomains. We show that Wavefront Diffusion obtains significantly lower data redistribution costs while maintaining similar or better edge-cut results compared to existing diffusion algorithms. We also compare Wavefront Diffusion with LMSR and show that these provide a trade-off between edge-cut and data redistribution costs for a wide range of problems. Our experimental results on a Cray T3E, an IBM SP2, and a cluster of Pentium Pro workstations show that both schemes are fast and scalable. For example, both are capable of repartitioning a seven million vertex graph in under three seconds on 128 processors of a Cray T3E. Our schemes obtained relative speedups of between nine and 12 when the number of processors was increased by a factor of 16 on a Cray T3E.
|Original language||English (US)|
|Number of pages||16|
|Journal||IEEE Transactions on Parallel and Distributed Systems|
|State||Published - May 2001|
Bibliographical noteFunding Information:
This work was supported by the US Department of Energy, contract number LLNL B347881, by the US National Science Foundation, grant CCR-9972519, by Army Research Office contracts DA/DAAG55-98-1-0441 and DA/DAAH04-95-1-0244, by the Army High Performance Computing Research Center cooperative agreement number DAAH04-95-2-0003/ contract number DAAH04-95-C-0008. The content of this work does not necessarily reflect the position or the policy of the government and no official endorsement should be inferred. Additional support was provided by the IBM Partnership Award and by the IBM SUR equipment grant. Access to computing facilities was provided by the AHPCRC, and the Minnesota Supercomputer Institute. Related papers are available via WWW: www.cs.umn.edu/ ~karypis.
- Adaptive mesh computations
- Dynamic graph partitioning
- Multilevel diffusion
- Wavefront diffusion