A Parallel Adaptive Fast Multipole algorithm for N-body problems
International Conference on Parallel Processing (ICPP) 1995
Publication Type: Paper
We describe the design and implementation of a parallel adaptive fast multipole algorithm (AFMA) for N-body problems. Our AFMA algorithm can organize particles in cells of arbitrary shape. This simplifies its parallelization, so that good locality and load balance are both easily achieved. We describe a tighter well-separatedness criterion, and improved techniques for constructing the AFMA tree. We describe how to avoid redundant computation of pair-wise interactions while maintaining load balance, using a fast edge-partitioning algorithm. The AFMA algorithm is designed in an object oriented, message-driven manner, allowing latency tolerance by overlapping computation and communication easily. It also incorporates several optimizations for message prioritization and communication reduction. Preliminary performance results of our implementation using the Charm++ parallel programming system are presented.
Sanjeev Krishnan and L. V. Kale, "A Parallel Adaptive Fast Multipole Algorithm for N-Body Problems", Proceedings of the International Conference on Parallel Processing, August 1995, pp. III 46 - III 50.