Scalable Unstructured Mesh Decomposition

K. McManus, S. P. Johnson, C. Walshaw, M. Cross, P. Chow


As the effciency of parallel software increases it is becoming common to measure near linear speedup for many applications. For a problem size N on P processors then with software running at O(N/P) the performance restrictions due to file i/o systems and mesh decomposition running at O(N) become increasingly apparent especially for large P. For distributed memory parallel systems an additional limit to scalability results from the finite memory size available for i/o scatter/gather operations. Simple strategies developed to address the scalability of scatter/gather operations for unstructured mesh based applications have been extended to provide scalable mesh decomposi tion through the development of a parallel graph partitioning code, JOSTLE [2]. The focus of this work is directed towards the development of generic strategies that can be incorporated into the Computer Aided Parallelisation Tools (CAPTools) project [1].


C. S. Ierotheou, S. P. Johnson, M. Cross, and P. F. Leggett. Computer aided parallelisation tools (CAPTools) - conceptual overview and performance on the parallelisation of structured mesh codes. Parallel Comput., 22:163-195, 1996.

C. Walshaw, M. Cross, and M. G. Everett. Parallel Dynamic Graph Partitioning for Adaptive Unstructured Meshes J. Parallel Distrib. Comput., 47(2):102-108, 1997. (originally published as Univ. Greenwich Tech. Rep. 97/IM/20

Fri Aug 13 13:42:38 BST 2004