Message-passing implementation of the data diffusion communication model in fast multipole methods: large scale...

Biomolecular simulations require increasingly efficient parallel codes. We present an efficient communication algorithm for irregular problems exhibiting an all-to-many communication pattern. The algorithm is developed using message passing on distributed memory machines and assumes explicit knowledge of the interconnection topology. The algorithm maximizes locality of interprocessor communication by adopting to an arbitrary interconnection topology and at the same time takes multiprocessor nodes into account. The solution is incorporated into our implementation of the fast multipole method with periodic boundary conditions used for molecular dynamics simulations, but we believe it generalizes to many algorithms demonstrating an all-to-many communication pattern. We show that an irregular algorithm can be forced to behave like a systolic algorithm.