PARALLEL MANY-BODY SIMULATIONS WITHOUT ALL-TO-ALL COMMUNICATION

Simulations of interacting particles are common in science and enginee ring, appearing in such diverse disciplines as astrophysics, fluid dyn amics, molecular physics, and materials science. These simulations are often computationally intensive and so are natural candidates for mas sively parallel computing. Many-body simulations that directly compute interactions between pairs of particles, be they short-range or long- range interactions, have been parallelized in several standard ways. T he simplest approaches require all-to-all communication, an expensive communication step. The fastest methods assign a group of nearby parti cles to a processor, which can lead to load imbalance and be difficult to implement efficiently. We present a new approach, suitable for dir ect simulations, that avoids ah-to-all communication without requiring any geometric clustering. We demonstrate its utility in several paral lel molecular dynamics simulations and compare performance against oth er parallel approaches. The new algorithm proves to be fastest for sim ulations of up to several thousand particles. (C) 1995 Academic Press, Inc.