A Heuristic Re-mapping Algorithm Reducing Inter-level Communication in SAMR Applications

J. Steensland and J. Ray (USA)


Dynamic load balancing, structured adaptive mesh refinement, meta-partitioner, run-time management


This paper aims at decreasing execution time for large scale structured adaptive mesh refinement (SAMR) appli cations by proposing a heuristic re-mapping algorithm and experimentally showing its effectiveness in reducing inter level communication for five applications. The overall goal is a dynamically adaptive meta-partitioner capable of se lecting and configuring the most appropriate partitioning strategy based on current system and application state. The meta-partitioner can significantly reduce execution times for SAMR applications. Computer simulations of physical phenomena are of ten based on solving partial differential equations by nu merical methods. Adaptive methods are crucial to effi ciently use computer resources. But even with adapta tion, the simulations are computationally demanding and yield huge data sets. Parallelization and efficient data par titioning are necessary. Adaptation causes the workload to change dynamically, calling for dynamic (re-) partitioning to maintain efficient resource utilization. Our algorithm reduced total communication volume with up to 30 percent. Since the complexity of the algo rithm is low, this decrease was relatively inexpensive. We conclude that the algorithm could lower execution times for many large SAMR applications, and that, due to its param eterization, it would constitute a natural component of the meta-partitioner.

Important Links:

Go Back