Abstract: "Dynamic mesh adaption on unstructured grids is a powerful tool for efficiently computing unsteady problems to resolve solution features of interest. Unfortunately, this causes load imbalance among processors on a parallel machine. This paper describes the parallel implementation of a tetrahedral mesh adaption scheme and a new global load balancing method. A heuristic remapping algorithm is presented that assigns partitions to processors such that the redistribution cost is minimized. Results indicate that the parallel performance of the mesh adaption code depends on the nature of the adaption region and show a 35.5X speedup on 64 processors of an SP2 when 35% of the mesh is randomly adapted. For large-scale scientific computations, our load balancing strategy gives almost a sixfold reduction in solver execution times over non-balanced loads. Furthermore, our heuristic remapper yields processor assignments that are less than 3% off the optimal solutions but requires only 1% of the computational time."

Abstract: "The computational requirements for an adaptive solution of unsteady problems change as the simulation progresses. This causes workload imbalance among processors on a parallel machine which, in turn, requires significant data movement at runtime. We present a new dynamic load-balancing framework, called JOVE, that balances the workload across all processors with a global view. Whenever the computational mesh is adapted, JOVE is activated to eliminate the load imbalance. JOVE has been implemented on an IBM SP2 distributed-memory machine in MPI for portability. Experimental results for two model meshes demonstrate that mesh adaption with load balancing gives more than a sixfold improvement over one without load balancing. We also show that JOVE gives a 24-fold speedup on 64 processors compared to sequential execution."

This IMA Volume in Mathematics and its Applications GRID GENERATION AND ADAPTIVE ALGORITHMS is based on the proceedings of a workshop with the same title. The work shop was an integral part of the 1996-97 IMA program on "MATHEMAT ICS IN HIGH-PERFORMANCE COMPUTING. " I would like to thank Marshall Bern (Xerox, Palo Alto Research Cen ter), Joseph E. Flaherty (Department of Computer Science, Rensselaer Polytechnic Institute), and Mitchell Luskin (School of Mathematics, Uni versity of Minnesota), for their excellent work as organizers of the meeting and for editing the proceedings. I also take this opportunity to thank the National Science Founda tion (NSF), Department of Energy (DOE), and the Army Research Office (ARO), whose financial support made the workshop possible. Willard Miller, Jr. , Professor and Director v PREFACE Scientific and engineering computation has become so complex that traditional numerical computation on uniform meshes is generally not pos sible or too expensive. Mesh generation must reflect both the domain geometry and the expected solution characteristics. Meshes should, fur thermore, be related to the solution through computable estimates of dis cretization errors. This, suggests an automatic and adaptive process where an initial mesh is enriched with the goal of computing a solution with prescribed accuracy specifications in an optimal manner. While automatic mesh generation procedures and adaptive strategies are becoming available, major computational challenges remain. Three-dimensional mesh genera tion is still far from automatic.

Abstract: "Mesh adaptation is a powerful tool for efficient unstructured-grid computations but causes load imbalance on multiprocessor systems. To address this problem, we have developed PLUM, an automatic portable framework for performing adaptive large-scale numerical computations in a message-passing environment. This paper presents several experimental results that verify the effectiveness of PLUM on sequences of dynamically adapted unstructured grids. We examine portability by comparing results between the distributed-memory system of the IBM SP2, and the Scalable Shared-memory MultiProcessing (S2MP) architecture of the SGI/Cray Origin2000. Additionally, we evaluate the performance of five state-of-the-art partitioning algorithms that can be used within PLUM. Results indicate that for certain classes of unsteady adaption, globally repartitioning the computational mesh produces higher quality results than diffusive repartitioning schemes. We also demonstrate that a coarse starting mesh produces high quality load balancing, at a fraction of the cost required for a fine initial mesh. Finally, we show that the data redistribution overhead can be significantly reduced by applying our heuristic processor reassignment algorithm to the default partition-to-processor mapping given by partitioners."

A procedure to support parallel refinement and redistribution of two dimensional unstructured finite element meshes on distributed memory computers is presented. The procedure uses the mesh topological entity hierarchy as the underlying data structures to easily support the required adjacency information. Mesh refinement is done by employing links back to the geometric representation to place new nodes on the boundary of the domain directly on the curved geometry. The refined mesh is then redistributed by an iterative heuristic based on the Leiss/Reddy 9 load balancing criteria. A fast parallel tree edge-coloring algorithm is used to pair processors having adjacent partitions and forming a tree structure as a result of Leiss/Reddy load request criteria. Excess elements are iteratively migrated from heavily loaded to less loaded processors until load balancing is achieved. The system is implemented on a massively parallel MasPar MP-1 system with a SIMD style of computation and uses message passing primitives to migrate elements during the mesh redistribution phase. Performance results of the redistribution heuristics on various test meshes are given.

This text on high-performance computing includes coverage of the topics: applications; I/O and compilers; scientific computing; data and file management; interconnection networks; compilers; image and signal processing; distributed systems; algorithms; architecture; and parallel programming.