In this paper the authors compare the performance and scalability of the SHMEM and corresponding MPI-3 routines for five different benchmark tests using a Cray XC30. The performance of the MPI-3 get and put operations was evaluated using fence synchronization and also using lock-unlock synchronization. The five tests used communication patterns ranging from light to heavy data traffic: accessing distant messages, circular right shift, gather, broadcast and all-to-all. Each implementation was run using message sizes of 8 bytes, 10 Kbytes and 1 Mbyte and up to 768 processes. For nearly all tests, the SHMEM get and put implementations outperformed the MPI-3 get and put implementations. The authors noticed significant performance increase using MPI-3 instead of MPI-2 when compared with performance results from previous studies.

The N-body problem is to simulate the motion of N particles under the influence of mutual force fields based on an inverse square law. Greengard's algorithm claims to compute the cumulative force on each particle in O(N) time for a fixed precision irrespective of the distribution of the particles. In this paper, we show that Greengard's algorithm is distribution dependent and has a lower bound of /spl Omega/(N log/sup 2/ N) in two dimensions and /spl Omega/(N log/sup 4/ N) in three dimensions. We analyze the Greengard and Barnes-Hut algorithms and show that they are unbounded for arbitrary distributions. We also present a truly distribution independent algorithm for solving the N-body problem in O(N log N) time in two dimensions and in O(N log/sup 2/ N) time in three dimensions.>