A Data-Parallel Implementation of the Geometric Partitioning Algorithm
Yu Charlie Hu, Shang‐Hua Teng, S. Lennart Johnsson · Digital Access to Scholarship at Harvard (DASH) (Harvard University) · 1997
We present a data-parallel, High Performance Fortran (HPF) implementation of the geometric partitioning algorithm. The geometric partitioning algorithm has provably good partitioning quality. To our knowledge, our implementation is the first data--parallel implementation of the algorithm. Our data--parallel formulation makes extensive use of segmented prefix sums and parallel selections, and provide a dataparallel procedure for geometric sampling. Experiments in partitioning particles for load--balance and data interactions as required in hierarchical N-body algorithms and iterative algorithms for the solution of equilibrium equations on unstructured meshes by the finite element method have shown that the geometric partitioning algorithm has an efficient data--parallel formulation. Moreover, the quality of the generated partitions is competitive with that offered by the spectral bisection technique and better than the quality offered by other partitioning heuristics.