Adaptive scientific simulations require that periodic repartitioning occur dynamically throughout the course of the computation. The repartitionings should be computed so as to minimize both the inter-processor communications incurred during the iterative mesh-based computation and the data redistribution costs required to balance the load. Recently developed schemes for computing repartitionings provide the user with only a limited control of the tradeoffs among these objectives. This paper describes a new Unified Repartitioning Algorithm that can tradeoff one objective for the other dependent upon a user-defined parameter describing the relative costs of these objectives. We show that the Unified Repartitioning Algorithm is able to reduce the precise overheads associated with repartitioning as well as or better than other repartitioning schemes for a variety of problems, regardless of the relative costs of performing inter-processor communication and data redistribution. Our experimental results show that this scheme is extremely fast and scalable to large problems.
|Original language||English (US)|
|Title of host publication||SC 2000 - Proceedings of the 2000 ACM/IEEE Conference on Supercomputing|
|Publisher||Association for Computing Machinery|
|State||Published - 2000|
|Event||2000 ACM/IEEE Conference on Supercomputing, SC 2000 - Dallas, United States|
Duration: Nov 4 2000 → Nov 10 2000
|Name||Proceedings of the International Conference on Supercomputing|
|Conference||2000 ACM/IEEE Conference on Supercomputing, SC 2000|
|Period||11/4/00 → 11/10/00|
Bibliographical noteFunding Information:
Acknowledgements This work was supported by National High Technology Programs of China (Grant No. 102-08-01-03) and Natural Science Fund Program of Guangdong Province (Grant No.001098).
© 2000 IEEE.
- Adaptive mesh computations
- Dynamic graph partitioning
- Multilevel diffusion
- Unified repartitioning algorithm