Abstract | ||
---|---|---|
Algorithms for the N-body problem are compared and contrasted, particularly those where N is in the range for which direct methods outperform approximation methods. With fewer bodies than processors, the so-called "replicated orrery" on a three-dimensional grid has been used successfully on the Connection Machine CM-2 architecture. With more bodies, the "rotated and translated Gray codes" is an ideal direct algorithm for machines such as the CM-2 in that it takes optimal advantage of the communications bandwidth of the machine. A classical Latin square can be used to abstractly denote any direct N-body calculation. Computational windows superimposed on this square illustrate the granularity of the computation. This point of view naturally illustrates a sequence of algorithms ranging along a granularity scale in the following order: "massively parallel," "replicated orrery," "orrery," "rotated/translated Gray codes," and "serial." |
Year | DOI | Venue |
---|---|---|
1993 | 10.1137/0914068 | SIAM Journal on Scientific Computing |
Keywords | Field | DocType |
N-BODY,HYPERCUBE,CM-2,PARALLEL COMPUTING,LATIN SQUARE,GRAY CODE | Computer science,Massively parallel,Direct methods,Algorithm,Gray code,Bandwidth (signal processing),Granularity,Grid,Hypercube,Computation | Journal |
Volume | Issue | ISSN |
14 | 5 | 1064-8275 |
Citations | PageRank | References |
5 | 1.31 | 1 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jean-Philippe Brunet | 1 | 12 | 5.24 |
Jill P Mesirov | 2 | 704 | 95.88 |
Alan Edelman | 3 | 1819 | 164.58 |