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.

For general information on the GEO partitioner, refer to