A Data–Parallel Implementation of the Geometric Partitioning Algorithm
1997 (English)Conference paper (Refereed)
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. 1 Introduction Th...
Place, publisher, year, edition, pages
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-64548OAI: oai:DiVA.org:kth-64548DiVA: diva2:483116
Eighth SIAM Conference on Parallel Processing for Scientific Computing
NR 201408052012-01-242012-01-24Bibliographically approved