Overview of neutral territory methods for the parallel evaluation of pairwise particle interactions

Particle simulations in fields ranging from biochemistry to astrophysics require evaluation of the interactions between all pairs of particles separated by less than some fixed interaction radius. The extent to which such simulations can be parallelized has historically been limited by the time required for inter-processor communication. Recently, Snir and Shaw independently introduced two distinct methods for parallelization that achieve asymptotic and practical advantages over traditional techniques. We give an overview of these methods and show that they represent special cases of a more general class of methods. We describe other methods in this class that can confer advantages over any previously described method in terms of communication bandwidth and latency. Practically speaking, the best choice among the broad category of methods depends on such parameters as the interaction radius, the size of the simulated system, and the number of processors. We analyze the best choice among a subset of these methods across a broad range of parameters.