# Multilevel Mesh Partitioning for Heterogeneous Communication Networks

**C. Walshaw and M. Cross**

### Abstract:

Multilevel algorithms are a successful class of optimisation techniques which address the mesh partitioning problem for distributing unstructured meshes onto parallel computers.
They usually combine a graph contraction algorithm together with a local optimisation method which refines the partition at each graph level.
To date these algorithms have been used almost exclusively to minimise the cut-edge weight in the graph with the aim of minimising the parallel communication overhead, but recently there has been a perceived need to take into account the communications network of the parallel machine.
For example the increasing use of SMP clusters (systems of multiprocessor compute nodes with very fast intra-node communications but relatively slow inter-node networks) suggest the use of hierarchical network models.
Indeed this requirement is exacerbated in the early experiments with meta-computers (multiple supercomputers combined together, in extreme cases over inter-continental networks).
In this paper therefore, we modify a multilevel algorithm in order to minimise a cost function based on a model of the communications network.
Several network models & variants of the algorithm are tested and we establish that it is possible to successfully guide the optimisation to reflect the chosen architecture.

**Keywords:**
graph partitioning, mesh partitioning, multilevel optimisation, mapping, meta-computing, SMP clusters.

* *

Fri Aug 13 13:41:22 BST 2004