Licentiate thesis 2001-002

Domain-based partitioning for parallel SAMR applications

Johan Steensland

March 2001


This thesis presents a study of domain-based partitioning techniques for dynamic structured grid hierarchies, occuring in structured adaptive mesh refinement (SAMR) methods. Such methods for obtaining the numerical solution to partial differential equations yield highly advantageous ratios for cost/accuracy as compared to methods based upon static uniform approximations. Distributed implementations of these techniques have the potential for enabling realistic simulations of complex systems. These implementations however, present significant challenges in dynamic data-distribution and load balancing. That is, when SAMR is executed on a parallel computer, the work load will change dynamically. Thus, there is need for dynamic load balancing in order to efficiently utilize the resourses of the parallel computer. Inverse space-filling curve partitioning (ISP) is appealing for load balancing in parallel SAMR, because of its speed. In this work, ISP is considered as part of a partitioning approach, which combines structured and unstructured techniques.

Various design decisions for the structured partitioning are considered. Different design choices lead to graphs with different properties. One objective is to investigate how these differences affect the behavior of ISP. This thesis contributes by identifying certain design choices as being advantageous, and by presenting four new partitioning algorithms that correspond to these design decisions.

An experimental comparison of dynamic partitioning techniques for blockwise parallel structured adaptive mesh refinement applications is presented. It is shown that an ISP-based technique can compete with other approaches for certain classes of applications. Moreover, an extended experimental characterization of dynamic partitioning/load-balancing techniques for general adaptive grid hierarchies is presented. Techniques studied include newly proposed as well as existing approaches. It was found that two of the proposed algorithms were particularly useful: pBD-ISP for the more communication dominated applications, and G-MISP+SP for the computation dominated applications.

Policies for the automatic selection of partitioner based on application and system state are outlined. Recommendations for appropriate partitioning techniques, given application and system state, are given. The overall motivation is the formulation of policies required to drive a dynamically adaptive meta-partitioner for SAMR grid hierarchies capable of selecting the most appropriate partitioning strategy at runtime, based on current application and system state. Such a partitioner may significantly decrease application execution time.

Download BibTeX entry.