Load Balancing for the Parallel Adaptive Solution of Partial DifferentialEquations

摘要

An adaptive technique for a partial differential system automatically adjusts acomputational 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