A Parallelisable Algorithm for Partitioning Unstructured Meshes

C. Walshaw, M. Cross, M. Everett and S. Johnson


A new method is described for solving the graph-partitioning problem which arises in mapping unstructured mesh calculations to parallel computers. The method, encapsulated in a software tool, JOSTLE, employs a combination of techniques including the Greedy algorithm to give an initial partition together with some powerful optimisation heuristics. A clustering technique is additionally employed to speed up the whole process. The resulting partitioning method is designed to work efficiently in parallel as well as sequentially and can be applied to both static and dynamically refined meshes. Experiments, on graphs with up to a million nodes, indicate that the JOSTLE procedure 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:43 BST 2004