Performance Analysis of Parallel Strategies for Localized N-body Solvers

Although there exist several approaches to rapidly solving the N-body problem, and a diversity of implementation strategies, the performance tradeoffs of the various strategies with respect to problem-specific data distributions is poorly understood on a parallel computer. We present a synthetic workload model and a simulator that enables us to evaluate the performance tradeoffs encountered in implementing particle methods on MIMD computers. These results can be used to evaluate designs early on in the implementation process. 1 Introduction We present a comparative performance analysis of various strategies for implementing localized N-body solvers on MIMD distributed memory parallel computers. In localized N-body solvers, particle interactions beyond a certain cutoff radius are either ignored or computed separately. Often the short range interactions predominate. We will consider only local interactions, i.e., each particle interacts over a small neighborhood only. Our results apply ..