Uppsala University Department of Information Technology

Technical Report 2001-002

Dynamic Structured Grid Hierarchy Partitioners Using Inverse Space-Filling Curves

Johan Steensland

February 2001

Abstract:
This paper discusses partitioning of dynamic structured grid hierarchies, occuring in structured adaptive mesh refinement (SAMR) applications. When a SAMR method is executed on a parallel computer, the work load will change dynamically. Thus, there is need for dynamic load balancing. Inverse space-filling curve partitioning (ISP) is appealing for load balancing in parallel SAMR, because of its speed. In this paper, ISP is considered as part of a partitioning approach, which combines structured and unstructured techniques. More precisely, various design decisions for the structured partitioning are considered. Different design choices lead to graphs with different properties. The main objective is to investigate how these differences affect the behavior of ISP. The paper contributes by (a) identifying certain design choices as being advantageous, and (b) presenting four new partitioning algorithms that correspond to these design decisions.

Available as PDF (256 kB, no cover) and compressed Postscript (102 kB, no cover)

Download BibTeX entry.



Uppsala Universitet