A Data-Parallel Implementation of the Geometric Partitioning Algorithm
Hu, Yu Charlie
Johnsson, S. Lennart
MetadataShow full item record
CitationHu, 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.
AbstractWe 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.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:25620495
- FAS Scholarly Articles