HYPERCUBE ALGORITHMS FOR DIRECT N-BODY SOLVERS FOR DIFFERENT GRANULARITIES

Algorithms for the N-body problem are compared and contrasted, particu larly those where N is in the range for which direct methods outperfor m approximation methods. With fewer bodies than processors, the so-cal led ''replicated orrery'' on a three-dimensional grid has been used su ccessfully on the Connection Machine CM-2 architecture. With more bodi es, the ''rotated and translated Gray codes'' is an ideal direct algor ithm for machines such as the CM-2 in that it takes optimal advantage of the communications bandwidth of the machine. A classical Latin squa re can be used to abstractly denote any direct N-body calculation. Com putational windows superimposed on this square illustrate the granular ity of the computation. This point of view naturally illustrates a seq uence of algorithms ranging along a granularity scale in the following order: ''massively parallel,'' ''replicated orrery,'' ''orrery,'' ''r otated/translated Gray codes,'' and ''serial.''