 | Abstracts for the Conference on
Grid Adaptivity in Computational PDEs,
Edinburgh, July 96 |  Next |
| Previous |
 Index |
Dynamic load balancing for adaptive methods on massively parallel computers
K D Devine¹ & J E Flaherty
¹Parallel Computer Sciences Department
Sandia National Laboratories
Albuquerque, NM 87185-1111, USA
Abstract
On massively parallel computers, load imbalance arises in the implementation
of adaptive finite-element and finite-difference methods. With adaptive order
(p-) refinement strategies, high-order elements require much more computation
time than low-order elements. With adaptive mesh (h-) refinement, localized
refinements may be restricted to a small subset of processors, assigning
larger numbers of elements to the processors or causing other processors to be
idle while local time-stepping is performed. We have adapted the local load-
balancing strategy of Wheat [1] for use with adaptive refinement methods. Global
load balance is achieved by performing local optimizations within overlapping
sets of neighboring processors. Individual elements are migrated from heavily
loaded processors to more lightly loaded neighboring processors. Elements are
weighted with their individual work loads to account for differing numbers of
degrees of freedom associated with adaptive p-refinement. Each level of mesh
refinement is balanced so that refined meshes are evenly distributed over the
processor array. The overhead associated with this load-balancing strategy is
small. Only local information is used to perform load balancing within
processor neighborhoods, so the algorithm scales to large numbers of
processors. The redistribution of work causes uniform subdomains to become
irregular, increasing communication costs during the adaptive computation.
However, the cost of the additional communication and load-balancing overhead
are outweighed by the time savings relative to a non-balanced adaptive
strategy. We will demonstrate the performance of this local load-balancing
strategy and compare its performance with global load-balancing techniques.
[1] S. Wheat. A Fine Grained Data Migration Approach to Application Load
Balancing on MP MIMD Machines. Ph.D. Dissertation. University of New
Mexico, Department of Computer Schience, Albuquerque, NM, 1992.
Last modified Fri Jun 21 19:19:12 GB-Eire 1996
(DBD)