Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Computational Science, Engineering & Technology Series
ISSN 1759-3158
CSETS: 2
PARALLEL AND DISTRIBUTED PROCESSING FOR COMPUTATIONAL MECHANICS: SYSTEMS AND TOOLS
Edited by: B.H.V. Topping
Chapter 6

Mesh Partitioning and Load Balancing for Distributed Memory Parallel Architectures

C. Walshaw, M. Cross and M.G. Everett

University of Greenwich, London, United Kingdom

Full Bibliographic Reference for this chapter
C. Walshaw, M. Cross, M.G. Everett, "Mesh Partitioning and Load Balancing for Distributed Memory Parallel Architectures", in B.H.V. Topping, (Editor), "Parallel and Distributed Processing for Computational Mechanics: Systems and Tools", Saxe-Coburg Publications, Stirlingshire, UK, Chapter 6, pp 110-123, 1999. doi:10.4203/csets.2.6
Keywords: graph-partitioning, unstructured meshes, load-balancing, parallel scientific computation.

Abstract
A method is outlined for optimising graph partitions which arise in mapping unstructured mesh calculations to parallel computers. The method employs a relative gain iterative technique to both evenly balance the workload and minimise the number and volume of interprocessor communications. A parallel graph reduction technique is also briefly described and can be used to give a global perspective to the optimisation. The algorithms work efficiently in parallel as well as sequentially and when combined with a fast direct partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two-stage process proves itself to be both a powerful and flexible solution to the static graph-partitioning problem. Experiments indicate that the resulting parallel code can provide high quality partitions, independent of the initial partition, within a few seconds. The algorithms can also be used for dynamic load-balancing, reusing existing partitions and in this case the procedures are much faster than static techniques, provide partitions of similar or higher quality and, in comparison, involve the migration of a fraction of the data.

purchase the full-text of this chapter (price £20)

go to the previous chapter
go to the next chapter
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)