Parallel dynamic load balancing strategies for adaptive irregular applications

Dynamic unstructured mesh adaptation is a powerful technique for solving co mputational problems with evolving physical features; however, an efficient parallel implementation is rather difficult because of the load imbalance that mesh adaptation creates. To address this problem, we have developed tw o dynamic load balancing strategies for parallel adaptive irregular applica tions. The first, called PLUM, is an architecture-independent framework par ticularly geared toward adaptive numerical computations and requires that a ll data be globally redistributed after each adaptation to achieve load bal ance. The second is a more general-purpose topology-independent load balanc er that utilizes symmetric broadcast networks (SBN) as the underlying commu nication pattern, with a goal to providing a global view of system loads ac ross processors. Results indicate that both PLUM and the SBN-based approach have their relative merits, and that they achieve excellent load balance a t the cost of minimal extra overhead. (C) 2000 Elsevier Science Inc. All ri ghts reserved.