#
# DP-GEO

##
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.