LOAD BALANCING FOR THE PARALLEL ADAPTIVE SOLUTION OF PARTIAL-DIFFERENTIAL EQUATIONS

An adaptive technique for a partial differential system automatically adjusts a computational mesh or varies the order of a numerical proced ure with a goal of obtaining a solution satisfying prescribed accuracy criteria in an optimal fashion. Processor load imbalances will, there fore, be introduced at adaptive enrichment steps during the course of a parallel computation. We develop and describe three procedures for r etaining and restoring load balance that have low unit cost and are ap propriate for use in an adaptive solution environment.Tiling balances load by using local optimality criteria within overlapping processor n eighborhoods. Elemental data are migrated between processors within th e same neighborhoods to restore balance. Tiling is restricted to unifo rm two-dimensional meshes and provides limited control of communicatio ns volume by priority-based element selection criteria. These shortcom ings can potentially be overcome by creating a dynamic partition graph connecting processors and their neighboring regions. After coloring t he edges of the graph, elemental data are iteratively transferred betw een processors by pairwise exchange to permit a more global migration. Octree decomposition of a spatail domain is a successful three-dimens ional mesh generation strategy. The octree structure facilitates a rap id load balancing procedure by performing tree traversals that (i) app raise subtree cost and (ii) partition spatial regions accordingly. Com putational results are reported for two- and three-dimensional problem s using nCUBE/2 hypercube, MasPar MP-2, and Thinking Machines CM-5 com puters.