1 Introduction

With the rapid growth in computing and communication technology, the past decade has witnessed a proliferation of powerful parallel and distributed systems and an ever-increasing demand for and practice of high performance computing [3,6]. A key issue in parallel and distributed computing is the partitioning, balancing and scheduling of computational loads among processors to efficiently utilize the available computing, communication and storage resources, and to maximize overall performance and scalability. This is especially true in the case of dynamically adaptive applications such as those based on the adaptive mesh refinement methods, where the computational load of these applications changes as the application evolves. In this paper, we present the design and preliminary evaluation of hierarchical partitioning and load-balancing techniques for distributed Structured Adaptive Mesh Refinement (SAMR) applications. Dynamically adaptive mesh refinement (AMR) [2] methods for the numerical solution of partial differential equations employ locally optimal approximations, and can yield highly advantageous ratios for cost/accuracy when compared to methods based upon static uniform approximations. These techniques seek to improve the accuracy of the solution by dynamically refining the computational grid in regions of high local solution error. Distributed implementations of these methods offer the potential for accurate solutions of physically realistic models of complex physical phenomena. These implementations also lead to interesting challenges in dynamic resource allocation, data-distribution, and load balancing. Critical among these is the dynamic partitioning of the adaptive grid hierarchy at runtime to balance load, optimize communication and synchronization, minimize data migration costs, and maximize available parallelism. Traditional distributed implementation of SAMR applications [1,8,9,11] have used dynamic partitioning/load-balancing algorithms that view the system as a flat pool of (usually homogeneous) processors. These approaches are typically based on a global knowledge of the state of the adaptive grid hierarchy, and partition the grid hierarchy across the set of processors. Global synchronizations and communications is required to maintain this global knowledge and can lead to significant overheads on large systems. Furthermore, these approaches do not exploit the hierarchical nature of the grid structure and the distribution of communications and synchronizations in this structure. The overall goal of the hierarchical partitioning algorithms (HPA) presented in this paper is to allow the distribution to reflect the state of the adaptive grid hierarchy and exploit it to reduce synchronization requirements, improve load-balance, and enable concurrent communications and incremental redistribution. These techniques partition the computational domain into subdomains and assigns these subdomains to dynamically configured hierarchical processor groups. Processor hierarchies and groups are formed to match natural hierarchies in the grid structure. In addition to providing good load-balance, this approach allows a large fraction of the communications required by the adaptive algorithms to be localized within a group. Furthermore, communications with different groups can proceed concurrently. Hierarchical partitioning also reduces the dynamic partitioning and data migration overheads by allowing these operations to be performed concurrently within different groups and incrementally across the domain. Two variants of HPA are presented in this paper. The Static Hierarchical Partitioning Algorithm (SHPA) assigns portions of overall load to processor groups. In SHPA, the group size and the number of processors in each group is set in advance and remains unchanged during the execution. While SHPA is static in the sense that its group topology is unchanged during the execution, it does perform dynamic load balancing. To overcome the static nature of SHPA, we propose an Adaptive Hierarchical Partitioning Algorithm (AHPA) that dynamically partitions the processor pool into hierarchical groups that match the structure of the adaptive grid hierarchy. AHPA naturally adapts to the runtime behavior of SAMR applications. A preliminary evaluation of these two algorithms is presented. It is experimentally shown that SHPA reduces communication costs as compared to the Non-HPA scheme and results in a reduction in overall application execution time up to $41\%$. Furthermore, initial evaluations shows that AHPA reduces the communication cost up to $70\%$.