Parallel Implementation of 3D FMA using MPI

The simulation of N-body system has been used extensively in biophysics and chemistry to investigate the dynamics of biomolecules and in astrophysics to study the chaotic characteristics of the galactic system. However, the longrange force calculation has a time complexity of O(N 2 ) where N is the number of particles in the system. The fast multipole algorithm (FMA), proposed by Greengard and Rokhlin, reduces the time complexity to O(N). Our goal is to build a parallel FMA library which is portable, scalable, and efficient. We use Message Passing Interface as the communication back-end. Also, an effective communication scheme to reduce communication overhead and a partitioning technique to obtain good load balancingamong processors were implemented into the library. 1 Introduction We consider the simulation of N-body system using the fast multipole algorithm (FMA) on homogeneous and heterogeneous distributed parallel systems. The simulation of the N-body system has a wide range of..