Dynamic mesh partitioning: a unified optimisation and load-balancing algorithm

C. Walshaw, M. Cross and M. G. Everett
Mathematics Research Report 95/IM/06

December '95


A parallel method for dynamic partitioning of unstructured meshes is described. The method employs a new unified iterative optimisation technique which both balances the workload and attempts to minimise the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent quality to static partitioners (which do not reuse the existing partition) and much more quickly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.

Key words. graph-partitioning, unstructured meshes, dynamic load-balancing.

Fri Aug 13 13:40:19 BST 2004