An optimal hypercube direct N-body solver on the Connection Machine

Publisher Website
Google Scholar
Abstract
The authors have designed and implemented a hypercube algorithm for direct N -body solvers on the Connection Machine CM-2. The algorithm is optimal in the sense that, as long as there is sufficient data, it uses the full communication bandwidth of a hypercube of any dimension. When the number of bodies per node is large enough, the communication time for the implementation is negligible, i.e., less than 2%. In particular, this means that one obtains close to optimal speedup in the regime. To obtain this performance, 'rotated and translated Gray codes' which result in time-wise edge disjoint Hamiltonian paths on the hypercube are used. Timings are presented for a collection of interacting point vortices in two dimensions. The computation of the velocities of 14,000 vortices in 32-bit precision takes 2 seconds on a 16K CM-2 Author(s) Brunet, J.-P. Thinking Machines Corp., Cambridge, MA, USA Mesirov, Jill P. ; Edelman, A.

This publication has 7 references indexed in Scilit: