| Author | Can Ozturan |
|---|---|
| Title | Distributed Environment and Load Balancing for Adaptive Unstructured Meshes |
| Year | 1995 |
| School | Computer Science |
| Institution | RPI |
| Abstract | Parallel adaptive finite element methods on distributed memory computers requires capabilities for mesh refinement and coarsening as well as a subsequent dynamic load balancing of processors. For their implementation, these procedures need a greater repertoire of entity adjacency and update operators on the distributed mesh and a migration procedure to facilitate arbitrary mobility of elements among processors. PMDB, Parallel Mesh Database, is a software tool developed using message passing libraries to provide one common runtime library for finite element analysis, mesh generation, refinement, coarsening and load balancing procedures on complex geometry unstructured meshes. We develop data structures which augment the hierarchical mesh entity relationships by attaching inter-processor links to shared entities on partition boundaries. The inter-processor links are managed by doubly linked structures to provide various query routines such as processor adjacency, lists of entities on partition boundaries, and update operators such as insertion and deletion of these entities. For entity migration, we use an owner updates rule which lets the processor owning a shared entity on partition boundary to collect and inform the updated links to the processors holding these entities. The updating process is restricted only to migrated boundary entities. In addition, global entity identification generation can also be replaced with the notion of ownership generation for new boundary entities. These approaches enable us to develop a scalable procedure for mesh migration. Finally, we develop a new iterative dynamic load balancing algorithm which uses Leiss and Reddy's [43] and Devine and Flaherty's [22] approach of requesting work from the most heavily loaded neighbor, but which proposes to view the load requests as a forest of trees. We present tree edge coloring and load balancing algorithms on trees linearized by the depth first search links. Each of the trees is then balanced by computing load migrations using logarithmic scan operations. We establish the convergence of the algorithm. We also present a comparison of the performance of load balancing and parallel inertia recursive bisection partitioning on various meshes and on an adaptive computational fluid dynamics application. |
| PDF File |  Download |