Multilevel Diffusion Schemes for Repartitioning of Adaptive Meshes
| Kirk Schloegel, George Karypis, and Vipin Kumar |
| Journal of Parallel and Distributed Computing, Vol. 47, pp. 109 - 124, 1997 |
Download Paper  |
| Abstract For a large class of irregular grid applications, the structure of the mesh changes from one phase of the computation to the next. Eventually, as the graph evolves, the adapted mesh has to be repartitioned to ensure good load balance. If this new graph is partitioned from scratch, it will lead to an excessive migration of data among processors. In this paper, we present two new schemes for computing repartitionings of adaptively refined meshes. These schemes perform diffusion of vertices in a multilevel framework and minimize vertex movement without significantly compromising the edge-cut. We present heuristics to control the tradeoff between edge-cut and vertex migration costs. We also show that multilevel diffusion produces results with improved edge-cuts over single-level diffusion, is potentially much faster than single-level diffusion in a parallel context, and is better able to make use of heuristics to control the trade-off between edge-cut and vertex migration costs than single-level diffusion. |
| Research topics: Graph partitioning | Parallel processing | ParMETIS |