A Data Parallel Graph Partitioner using a Geometric Partitioning Algorithm

DP-GEO is a data parallel graph partitioner: an HPF implementation of the geometric partitioning algorithm originally conceived by Miller-Teng-Thurston-Vavasis and further developed by Teng and collaborators. The code uses HPF features supported by the HPF compiler pghpf from the Portland Groups, Inc, but not supported by some other commercial HPF compilers. The implemented geometric partitioning algorithm yields partitions with provably good properties. To our knowledge, our data-parallel implementation, first in Connection Machine Fortran in 1994, now in HPF is still the only data-parallel implementation of the algorithm. Our data-parallel formulation makes extensive use of segmented prefix sums and parallel selections.

Downloaded File Description Language Compressed Size Expanded Size README
geo.tar.gz geometric partitioning algo. HPF 26 KB 209 KB README.geo

For general information on the GEO partitioner, refer to

  • Y. Charlie Hu, S. Lennart Johnsson and Shang-Hua Teng. A Data Parallel Implementation of the Geometric Partitioning Algorithm. Proceedings of the 8th SIAM Conference on Parallel Processing for Scientific Computing, Minneapolis, MN, March 1997.
  • G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis. Automatic mesh partitioning. In A. George, J. Gilbert, and J. Liu, editors, Sparse Matrix Computations: Graph Theory Issues and Algorithms, IMA Volumes in Mathematics and its Applications. Springer-Verlag, 1993.

    Questions or comments? Please send email to Y. Charlie Hu at ychu@cs.rice.edu.