Name
Abstract | ||
|---|---|---|
The direct method for solving N-body problems maps perfectly onto hypercube architectures. Unlike other hypercube implementations, we have implemented a direct N-body solver on the Connection Machine CM-2 which makes optimum use of the full bandwidth of the hypercube. When N ≫ P, where P is the number of floating-point processors, the communication time of the algorithm is negligible, and the execution time is that of the arithmetic time giving a P-fold speed-up for real problems. To obtain this performance, we use “rotated and translated Gray codes” which result in time-wise edge disjoint Hamiltonian paths on the hypercube. We further propose that this communication pattern has unexplored potential for other types of algorithms. 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. |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1109/SUPERC.1990.130096 | SC |
Keywords | Field | DocType |
n-body problems map,connection machine,execution time,communication time,arithmetic time,hypercube implementation,direct n-body solver,communication pattern,connection machine cm-2,direct method,hypercube direct n-body solver,hypercube architecture,astronomy,gray codes,kernel,two dimensions,floating point arithmetic,fluid dynamics,floating point,gray code,parallel algorithms,n body problem,bandwidth,broadcasting,hypercubes,hamiltonian path | Direct method,Disjoint sets,Computer science,Parallel algorithm,Parallel computing,Gray code,Bandwidth (signal processing),Solver,Hypercube,Distributed computing,Computation | Conference |
ISBN | Citations | PageRank |
0-89791-412-0 | 6 | 3.09 |
References | Authors | |
2 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jean-Philippe Brunet | 1 | 12 | 5.24 |
| Alan Edelman | 2 | 6 | 3.09 |
| Jill P Mesirov | 3 | 704 | 95.88 |