A unified algorithm for load-balancing adaptive scientific simulations

Kirk Schloegel, George Karypis, Vipin Kumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

37 Scopus citations

Abstract

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 languageEnglish (US)
Title of host publicationSC 2000 - Proceedings of the 2000 ACM/IEEE Conference on Supercomputing
PublisherAssociation for Computing Machinery
ISBN (Electronic)0780398025
DOIs
StatePublished - 2000
Event2000 ACM/IEEE Conference on Supercomputing, SC 2000 - Dallas, United States
Duration: Nov 4 2000Nov 10 2000

Publication series

NameProceedings of the International Conference on Supercomputing
Volume2000-November

Conference

Conference2000 ACM/IEEE Conference on Supercomputing, SC 2000
Country/TerritoryUnited States
CityDallas
Period11/4/0011/10/00

Bibliographical note

Funding 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).

Publisher Copyright:
© 2000 IEEE.

Keywords

  • Adaptive mesh computations
  • Dynamic graph partitioning
  • Multilevel diffusion
  • Scratch-remap
  • Unified repartitioning algorithm

Fingerprint

Dive into the research topics of 'A unified algorithm for load-balancing adaptive scientific simulations'. Together they form a unique fingerprint.

Cite this