1.1 Related work

There exist a number of infrastructures that support parallel and distributed implementations of SAMR applications. Each such system represents a combination of design decisions in terms of algorithms, data structures, user interfaces, decomposition, mapping, and distribution and communication mechanisms. Table 1 summarizes a selection of the existing SAMR infrastructures and the partitioning approach used by them. Related work in hierarchical load-balancing is described below.

Table 1: Distributed SAMR Infrastructures

Infrastructure	Description
PARAMESH [9]	Extends serial code to parallel code based on partitioning tree representation of adaptive grid structure
SAMRAI [8]	Object oriented framework (based on LPARX) with patches mapped across processors at a level
BATSRUS [1]	Block-based approach with adaptation distributed over processors in computational pool in phases

Pollack [12] proposed a scalable hierarchical approach for dynamic load balancing in parallel and distributed systems and implemented a system, named PaLaBer (Parallel Load Balancer), on the Intel Paragon XP/S. It uses multilevel control for dynamic load balancing and for the communication manager. This hierarchical load balancer uses non-preemptive as well as preemptive process migration to balance load between the processors. However, the load balancing hierarchy is static in that once created the configuration remains fixed for the entire run. PaLaBer targets overall scheduling and load-balancing of tasks from multiple applications rather than dynamic load-balancing for adaptive applications such as SAMR. Compared to PalaBer, HPA strategy is more flexible and can be static or adaptive. Furthermore, HPA strategy addresses SAMR applications by taking into account the features of the computational domain and the adaptive nature of SAMR applications. Another related approach by Furuchi et al. [7] addressed load balancing for parallel OR-search programs. This load balancing system consists of a subtask generator that partitions a program into independent subtasks, and distributes them to the processing elements so as to balance workload. In this scheme, each subtask generator is in charge of a certain fixed number of processors, which form a processor group. The rest of the paper is organized as follows. Section 2 provides a short introduction to SAMR and distributed SAMR implementations. Section 3 describes the hierarchical partitioning algorithm. The general HPA scheme is first presented and is followed by two variant, viz. Static HPA and Adaptive HPA. Experimental and simulation results are also presented and discussed. Conclusions are presented in Section 4.