Efficient techniques for n-body simulation on distributed memory architectures

High Performance Fortran (HPF) provides a high-level model for expressing parallel programs. However, the efficiency of HPF as an implementation vehicle for irregular applications is still largely unproven. While recent work has shown that a highly irregular hierarchical n-body force calculation method can be implemented in HPF, we have found that the implementation contains inefficiencies which cause it to run up to a factor of three times slower than our hand-coded, explicitly parallel implementation. This thesis examines these inefficiencies, determines that most of the extra overhead is due to a single aspect of the communication strategy, and demonstrates that fixing the communication strategy can bring the overheads of the HPF application to within 25% of those of the hand-coded version