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 |

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.