Walshaw, C. ORCID: 0000-0003-0253-7779, Cross, M. and Everett, M. G. (1997) Mesh partitioning and load balancing for distributed memory parallel systems. In: Parallel and Distributed Computing for Computational Mechanics, April 1997, Lochinver, Scotland.

Full text not available from this repository.

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.

Item Type:	Conference or Conference Paper (Paper)
Uncontrolled Keywords:	graph-partitioning, unstructured meshes, load-balancing, parallel scientific computation
Pre-2014 Departments:	School of Computing & Mathematical Sciences
Last Modified:	14 Oct 2016 09:00
URI:	http://gala.gre.ac.uk/id/eprint/407

Actions (login required)

View Item