Run-Time Selection of Partitioning Algorithms for Parallel SAMR Applications

Henrik Johansson

March 2009

Abstract:

Parallel structured adaptive mesh refinement methods decrease the execution time and memory requirements of partial differential equation solvers. These methods result in an adaptive and dynamic grid hierarchy that repeatedly needs to be re-partitioned and distributed over the processors. No single partitioning algorithm can consistently construct high-quality partitionings for all possible grid hierarchies. Instead, the partitioning algorithm needs to be selected during run-time. In this paper, an initial implementation of the Meta-Partitioner is presented. At each re-partitioning, the Meta-Partitioner autonomously selects, configures, and invokes the partitioning algorithm predicted to result in the best performance. To predict the performance of the partitioning algorithms, the Meta-Partitioner uses historic performance data for grid hierarchies with properties similar to the current hierarchy. The Meta-Partitioner focuses the partitioning effort on the most performance-inhibiting factor - either the load imbalance or the synchronization delays. The performance evaluation shows a small but noticeable performance increase compared to the best static algorithm. Compared to the average performance for a large number of partitioning algorithms, the Meta-Partitioner consistently generates partitionings with a significantly better performance.

Available as PDF (152 kB, no cover)

Download BibTeX entry.