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 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 load by using local optimality criteria within overlapping processor neighborhoods. Elemental data are migrated between processors within the same neighborhoods to restore balance. Tiling is restricted to uniform two-dimensional meshes and provides limited control of communications volume by priority-based element selection criteria. These shortcomings can potentially be overcome by creating a dynamic partition graph connecting processors and their neighboring regions. After coloring the edges of the graph, elemental data are iteratively transferred between processors by pairwise exchange to permit a more global migration. Octree decomposition of a spatail domain is a successful three-dimensional mesh generation strategy. The octree structure facilitates a rapid load balancing procedure by performing tree traversals that (i) appraise subtree cost and (ii) partition spatial regions accordingly. Computational results are reported for two- and three-dimensional problems using nCUBE/2 hypercube, MasPar MP-2, and Thinking Machines CM-5 computers.