J Algorithm Comput Technol. 2008;2(4):557-579. doi: 10.1260/174830108786231722.

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

Journal of algorithms & computational technology

Jakub Kurzak, B Montgomery Pettitt

PMID: 19789722 PMCID: PMC2752898 DOI: 10.1260/174830108786231722

Abstract

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.

References

1. Science. 1994 Aug 12;265(5174):909-14 - PubMed
2. Mol Simul. 2006;32(10-11):775-790 - PubMed

Publication Types

• Journal Article

Grant support

• R01 GM037657/GM/NIGMS NIH HHS/United States
• R01 GM037657-15/GM/NIGMS NIH HHS/United States
• R01 GM066813/GM/NIGMS NIH HHS/United States
• R01 GM066813-04/GM/NIGMS NIH HHS/United States