| Author | H. L. deCougny, K. D. Devine, J. E. Flaherty, R. M. Loy, C. Ozturan and M. S. Shephard |
|---|---|
| Title | Load Balancing for the Parallel Adaptive Solution of Partial Differential Equations |
| Year | 1994 |
| Journal | Applied Numerical Mathematics |
| Volume | 16 |
| Pages | 157-182 |
| Abstract | An adaptive technique for a partial differential system automatically adjusts a computational mesh or varies the order of a numerical procedure with a goal of obtaining a solution satisfying prescribed accuracy criteria in an optimal fashion. Processor load imbalances will, therefore, be introduced at adaptive enrichment steps during the course of a parallel computation. We develop and describe three procedures for retaining and restoring load balance that have low unit cost and are appropriate for use in an adaptive solution environment. Tiling balances loading by using local optimality criteria within overlapping processor neighborhoods. Elemental data are migrated between processors within the same neighborhoods to restore balance. Tiling can potentially be improved by creating a dynamic partition graph connecting processors and their neighboring regions. After coloring the edges of the graph, elemental data are transferred between processors by pairwise exchange. Octree decomposition of a spatial domain is a successful three-dimensional mesh generation strategy. By performing tree traversals that (i) appraise subtree costs and (ii) partition spatial regions accordingly, we show that octree structures may also be used to balance processor loading. Computational results are reported for two- and three-dimensional systems using nCUBE/2 hypercube, MasPar MP-2 and Thinking Machines CM-5 computers. |
| PDF File |  Download |