Neutral Territory Methods for the Parallel Evaluation of Pairwise Particle Interactions

Kevin J Bowers, Ron O Dror, and David E Shaw
D.E. Shaw Research and Development LLC

Particle simulations in fields ranging from biochemistry to astrophysics require evaluation of the interactions between all pairs of particles separated by less than some interaction radius. Recently, Snir [1] and Shaw [2] independently introduced two distinct methods for parallelizing this computation. Both methods achieve asymptotic and practical advantages over traditional parallelization techniques. We describe Shaw's Neutral Territory and Snir's Hybrid Method and show that they represent special cases of a more general class of methods. We also describe new methods that can confer advantages over any previously described method in terms of communications bandwidth and latency. These generalizations include novel spatial decompositions, more advanced import region rounding and multiple zone communication scheduling.

Practically speaking, the best choice among the broad category of methods we describe depends on parameters including the interaction radius, the size of the simulated system and the number of processors available. We analyze the best choice of parallelization scheme for different values of these parameters, assuming a simple network cost model. While we do not prove optimality, we show that the communication bandwidth required by several of the schemes comes close to or achieves an approximate lower bound.

[1] Snir, M. Theory of Computing Systems. 37, 295-318. 2004
[2] Shaw, D. Journal of Computational Chemistry. Accepted for publication. 2005