PLUM - PARALLEL LOAD BALANCING FOR ADAPTIVE UNSTRUCTURED MESHES

Mesh adaption is a powerful tool for efficient unstructured-grid compu tations but causes load imbalance among processors on a parallel machi ne. We present a novel method called PLUM to dynamically balance the p rocessor workloads with a global view. This paper describes the implem entation and integration of all major components within our dynamic lo ad balancing strategy for adaptive grid calculations. Mesh adaption, r epartitioning, processor assignment, and remapping are critical compon ents of the framework that must be accomplished rapidly and efficientl y so as not to cause a significant overhead to the numerical simulatio n. A data redistribution model is also presented that predicts the rem apping cost on the SP2. This model is required to determine whether th e gain from a balanced workload distribution offsets the cost of data movement. Results presented in this paper demonstrate that PLUM is an effective dynamic load balancing strategy which remains viable on a la rge number of processors. (C) 1998 Academic Press.