The Fast Multipole Method on Ram, the Altix 3700 at Oak Ridge National Laboratory

This paper describes experiments with two paral-lel implementations of the Fast Multipole Method { one using the shared memory programming model (OpenMP), the other the message passing model (MPI) { on the SGI Altix 3700 at Oak Ridge Na-tional Laboratory. The purpose of our experiments was to test our hypothesis that direct access to shared memory enabled by hardware-based cache coherence is a better match for the ne-grained communica-tion requirements of the tree-code computations of the algorithm, while the message passing version's gather/scatter approach is more ecient for the more coarse-grained interaction computation. After providing some context for the discussion with a description of the algorithm and our paral-lelizations, we begin the analysis of our experiments by describing the unexpected initial results on the Altix, and how we went about obtaining more repre-sentative data. Then, having addressed the problem, we turn our attention to the larger implications of our experiments. We nd that, as we expected, the tree-code is much better suited to shared memory, both from a commu-nication and an actual performance standpoint. On the other hand, contrary to our expectations, and though communication requirements appear to favor the gather/scatter approach to interaction computa-tion taken by the MPI version, the shared memory version consistently outperforms the message passing version