Jean-Philippe Brunet
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.
- 1.Anderson, C.R. A method of local corrections for computing the velocity field due to a distribution of vortex blobs. SIAM J. Numer. AnM. 22, (1986), 413-440.Google Scholar
Cross Ref
- 2.Appel, A. An efficient program for many-body simulation. SIAM J. Sci. Star. Comput. 6, (1985), 85-103.Google ScholarCross Ref
- 3.Barnes, J. and Hut, P. A hierarchical O(N log N) force calculation algorithm. Nature 324, (1986), 446-449.Google ScholarCross Ref
- 4.Brunet, J-Ph., Edelman, A., and Mesirov, J.P. Two Hypercube Algorithms for Direct N-body Solvers, in preparation.Google Scholar
- 5.Barnes, J. and Hillis, W.D. Programming a highly parallel computer. Nature 326, (1987), 27-30.Google ScholarCross Ref
- 6.Bcrtsckas, D.P., Ozvcren, C., Stamoulis, G.D., Tscng, P., and Tsitsiklis, J.N. Optimal communication algorithms for hypcrcubcs. To appear.Google Scholar
- 7.Fox, G.C., Hipes, P., and Salmon, J. Practical parallel supercomputing: examples from chemistry and physics. Proceedings Supercompt~ting '89. ACM Press, Reno, NV, 1989, pp. 58-70. Google ScholarDigital Library
- 8.Greengard, L. and Rokhlin, V. A fast algorithm for partide simulation. J. Comp. Phys. 73, (1987), 325-348. Google ScholarDigital Library
- 9.Johnsson, S.L. and Ho, C.T. Optimum broadcasting and personalized communication in hypercubes. IEEF, Transactions on Computers 38, (1989), 1249-1268. Google ScholarDigital Library
- 10.Johnsson, S.L. and tto, C.T. Multiplication of arbitrarily shaped matrices on boolean cubes using the full communications bandwidth. Yale University Tech. Rep. YALEU/DCS/TR-721, Yale University, Dept. of Computer Science, New Haven, 1989.Google Scholar
- 11.Reingold, E.M.~ Nievergelt, J., and Deo, N. Combinatorial Algorithms, Prentice-Hall, Englewoods Cliffs, NJ, 1977. Google ScholarDigital Library
- 12.Sethian, J.A., Brunet, J-Ph., Greenberg, A., and Mesirov, J.P. Two-dimensional, viscous, incompressible flow in arbitrary geometries on a massively parallel processor. To appear.Google Scholar
- 13.Zhao, F. and Johnsson, S.L. The parallel multipole method on the Connection Machine. Thinking Machines Corporation Tech. Rep. CS89-6, Thinking Machines Corp., Cambridge, MA, 1989.Google Scholar
Index Terms
- An optional hypercube direct N-body solver on the connection machine
Recommendations
Vortex Methods for Direct Numerical Simulation of Three-Dimensional Bluff Body Flows
Recent contributions to the 3-D vortex methods are presented. Following Cottet, the particles strength exchange (PSE) scheme for diffusion is modified in the vicinity of solid boundaries to avoid a spurious vorticity flux and to enforce a zero-normal ...
Comments