Hu, Yu CharlieTeng, Shang-HuaJohnsson, S. Lennart2016-02-251996Hu, Yu Charlie, Shang-Hua Teng, and S. Lennart Johnsson. 1996. A Data-Parallel Implementation of the Geometric Partitioning Algorithm. Harvard Computer Science Group Technical Report TR-15-96.http://nrs.harvard.edu/urn-3:HUL.InstRepos:25620495We 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 data-parallel 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 infinite 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.en-USResearch Paper or Report2016-02-25