Accession Number : ADA290450

Title :   Load Balancing for the Parallel Adaptive Solution of Partial Differential Equations.

Descriptive Note : Technical rept.,

Corporate Author : RENSSELAER POLYTECHNIC INST TROY NY SCIENTIFIC COMPUTATION RESEARCH CENTER

Personal Author(s) : DECougny, H. L. ; Devine, K. D. ; Flaherty, J. E. ; Loy, R. M. ; Ozturan, C.

PDF Url : ADA290450

Report Date : APR 1994

Pagination or Media Count : 36

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.

Descriptors :   *FINITE ELEMENT ANALYSIS, *PARTIAL DIFFERENTIAL EQUATIONS, ALGORITHMS, SPATIAL DISTRIBUTION, COMPUTATIONS, STRATEGY, LOW COSTS, EDGES, GRAPHS, PARALLEL PROCESSING, MESH, THREE DIMENSIONAL, SOLUTIONS(GENERAL), BALANCE, ADAPTIVE SYSTEMS, NUMERICAL METHODS AND PROCEDURES, DECOMPOSITION.

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE