A Parallelisable Algorithm for Optimising Unstructured Mesh Partitions

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


A new method is described for optimising graph partitions which arise in mapping unstructured mesh calculations to parallel computers. The method employs a combination of iterative techniques to both evenly balance the workload and minimise the number and volume of interprocessor communications. It is designed to work efficiently in parallel as well as sequentially and can be applied directly to dynamically refined meshes. In addition, 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. A clustering technique can also be employed to speed up the whole process. Experiments, on graphs with up to a million nodes, indicate that the resulting code is up to an order of magnitude faster than existing state-of-the-art techniques such as Multilevel Recursive Spectral Bisection.

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

Fri Aug 13 13:40:40 BST 2004