A Performance Characterization of Load Balancing Algorithms for Parallel SAMR Applications

We perform a comprehensive performance characterization of load balancing algorithms for parallel structured adaptive mesh refinement (SAMR) applications. Using SAMR, computational resources are dynamically concentrated to areas in need of a high accuracy. Because of the dynamic resource allocation, the workload must repeatedly be partitioned and distributed over the processors. For an efficient parallel SAMR implementation, the partitioning algorithm must be dynamically selected at run-time with regard to both the application and computer state. We characterize and compare a common partitioning algorithm and a large number of alternative partitioning algorithms. The results prove the viability of dynamic algorithm selection and show the benefits of using a large number of complementing partitioning algorithms.