Parallel Algorithms for Dynamically Partitioning Unstructured Grids

Pedro Diniz
Department of Computer Science,
University of California at Santa Barbara
Santa Barbara, CA 93106-5110

and

Bruce Hendrickson, Robert Leland and Steve Plimpton
Sandia National Laboratories
Albuquerque, NM 87185-1110

Keywords

graph partitioning, parallel computation, load balancing.

Abstract

Grid partitioning is the method of choice for decomposing a wide variety of computational problems into naturally parallel pieces. In problems where computational load on the grid or the grid itself changes as the simulation progresses, the ability to repartition dynamically and in parallel is attractive for achieving higher performance. We describe three algorithms suitable for parallel dynamic load--balancing which attempt to partition unstructured grids so that computational load is balanced and communication is minimized. The execution time of the algorithms and the quality of the partitions they generate are compared to results from serial partitioners for two large grids. The integration of the algorithms into a parallel particle simulation is also briefly discussed.

AMS(MOS) subject classification. C5C85, 68R10, 65Y05

Postscript Document