HEAP

A software package for potential and force field evaluation for large scale gravitational and electrostatic field particle systems using nonadaptive and adaptive O(N) Poisson formula based hierarchical methods

HEAP is a software package implementing nonadaptive and adaptive O(N) hierarchical N-body methods in 3-D for gravitational and electrostatic fields. The codes use computational elements based on Poisson's Formula as derived by Anderson to approximate the effect of clusters of particles, instead of multipole expansions as used in Greengard-Rokhlin's Fast Multipole Methods. A data parallel, geometric, graph partitioner based on the algorithm by Miller-Teng-Thurston-Vavasis is included in the package.

The entire package is implemented in High Performance Fortran (HPF) and in Fortran 90. The data parallel version of the package has been benchmarked with the HPF compiler from the Portland Group Inc. It makes use of gather/scatter and parallel prefix operations which are not currently supported by some commercial compilers. The adaptive HPF code is the first adaptive implementation of a Poisson's Formula based hierarchical method for gravitational and electrostatic fields. Moreover, in 1997 it was the only distributed memory implementation of any 3-D, adaptive, O(N) hierarchical methods for such fields. Furthermore, it was implemented entirely in HPF, a high-level, implicit parallel programming language. With efficient runtime support for gather/scatter operations, the efficiency of the code is demonstrated to be within 20% of a newly developed MPI counterpart. This research demonstrates that HPF is highly viable for highly irregular applications with proper language/compiler support. In addition to being production quality, the code also provides a valuable benchmark for HPF language/compiler research on irregular problems.

Downloaded File Description Language Compressed Size Expanded Size README
heap.a.hpf.tar.gz Adaptive 3-D N-body code HPF 28 MB 70 MB README.adap
heap.na.hpf.tar.gz * NonAdaptive 3-D N-body code HPF ... ... ...
heap.na.f90.tar.gz * NonAdaptive 3-D N-body code Fortran 90 ... ... ...
geo.tar.gz geometric partitioning algo. HPF 26 KB 209 KB README.geo
*: forthcoming

For general information on the adaptive HPF code, refer to our PPoPP'97 paper: Y. Charlie Hu, S. Lennart Johnsson and Shang-Hua Teng. High Performance Fortran for Highly Irregular Problems . Proceedings of the 6th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Las Vegas, Nevada, June 1997.

For general information on the nonadaptive HPF code, refer to our IJSA paper: Yu Hu and S. Lennart Johnsson. A Data-Parallel Implementation of Hierarchical N-body Methods. International Journal of Supercomputer Applications and High Performance Computing, 10(1): 3-40, 1996, or our SC96 paper: Yu Hu and S. Lennart Johnsson. A Data-Parallel Implementation of O(N) Hierarchical N-body Methods. Supercomputing '96, November, 1996.

For general information on the GEO partitioner, refer to our SIAM PPSC'97 paper: 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.


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