# Mesh partitioning and load-balancing for distributed memory parallel systems

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

**April '97**

### 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.

**Key words.** graph-partitioning, unstructured meshes, load-balancing,
parallel scientific computation.

* *

Fri Aug 13 13:40:30 BST 2004