This paper presents the design and preliminary evaluation of
hierarchical partitioning and load-balancing techniques for
distributed Structured Adaptive Mesh Refinement (SAMR)
applications. The overall goal of these techniques is to enable
the load 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. The hierarchical partitioning
algorithm (HPA) partitions the computational domain into
subdomains and assigns them to hierarchical processor groups. 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 setup during initialization
and remains unchanged during application execution. It is
experimentally shown that SHPA reduces communication costs as
compared to the Non-HPA scheme, and reduces overall application
execution time by up to
. The Adaptive Hierarchical
Partitioning Algorithm (AHPA) dynamically partitions the
processor pool into hierarchical groups that match the structure
of the adaptive grid hierarchy. Initial evaluations of AHPA show
that it can reduce communication costs by up to
.
Keywords: Dynamic Load Balancing, Hierarchical Partitioning Algorithm,
Distributed Computing, Structured Adaptive Mesh Refinement
