Wavefront Diffusion and LMSR: Algorithms for Dynamic Repartitioning of Adaptive Meshes

Kirk Schloegel, George Karypis, and Vipin Kumar
IEEE Transactions on Parallel and Distributed Systems. Vol. 12, No. 5, 451 - 466, 2001
Download Paper
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.
Research topics: Graph partitioning | Parallel processing | ParMETIS | Scientific computing