C. Walshaw, M. Cross, M. G. Everett and S. Johnson
We outline the philosophy behind a new method 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 JOSTLE is up to an order of magnitude faster than existing state-of-the-art techniques such as Multilevel Recursive Spectral Bisection, whilst providing partitions of equivalent quality.
Key words. graph-partitioning, unstructured meshes, load-balancing, parallel scientific computation.