A Data Parallel Implementation of O(N) Hierarchical N–body Methods
Yu Charlie Hu, Lennart Johnsson · 1996
The O(N) hierarchical N--body algorithms and Massively Parallel Processors allow particle systems of 100 million particles or more to be simulated in acceptable time. We present a data--parallel implementation of Anderson's method and demonstrate both efficiency and scalability of the implementation on the Connection Machine CM--5/5E systems. The communication time for large particle systems amounts to about 10--25%, and the overall efficiency is about 35%. The evaluation of the potential field of a system of 100 million particles takes 3 minutes and 15 minutes on a 256 node CM--5E, giving expected four and seven digits of accuracy, respectively. The speed of the code scales linearly with the number of processors and number of particles. Keywords: N--body simulation, multipole algorithms, hierarchical N--body methods, data--parallel programming, massively parallel processors. 1 Introduction The problem of computing the force (or the potential) exerted on one another by a system of ele...