Technical Report 2008-017

Design and Implementation of a Dynamic and Adaptive Meta-Partitioner for Parallel SAMR Grid Hierarchies

Henrik Johansson

June 2008

Abstract:

In this paper we present a pilot implementation of the Meta-Partitioner, a partitioning framework that automatically selects, configures, and invokes suitable partitioning algorithms for Structured Adaptive Mesh Refinement (SAMR) applications. Efficient use of SAMR on parallel computers requires that the dynamic grid hierarchy is repeatedly repartitioned and redistributed. The partitioning process needs to consider all factors that contribute to the run-time, i.e. computational load, communication volume, synchronization delays, and data movement. There is no partitioning algorithm that performs well for all possible grid hierarchies - instead the algorithms must be selected dynamically during run-time.

At each repartitioning, the Meta-Partitioner uses performance data from previously encountered application states to select the partitioning algorithm with the best predicted performance. Before the repartition, we determine a partitioning focus to direct the partitioning effort to the performance-inhibiting factor that currently has the largest impact on the execution time.

The implementation uses component-based software engineering (CBSE) to allow for easy expansion and modification. Also, by employing CBSE it is easy to adapt existing SAMR engines for use with the Meta-Partitioner.

Available as PDF (750 kB, no cover)

Download BibTeX entry.