An optional hypercube direct N-body solver on the connection machine

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.

REFERENCES

• 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.
• 2: Appel, A. An efficient program for many-body simulation. SIAM J. Sci. Star. Comput. 6, (1985), 85-103.
• 3: Barnes, J. and Hut, P. A hierarchical O(N log N) force calculation algorithm. Nature 324, (1986), 446-449.
• 4: Brunet, J-Ph., Edelman, A., and Mesirov, J.P. Two Hypercube Algorithms for Direct N-body Solvers, in preparation.
• 5: Barnes, J. and Hillis, W.D. Programming a highly parallel computer. Nature 326, (1987), 27-30.
• 6: Bcrtsckas, D.P., Ozvcren, C., Stamoulis, G.D., Tscng, P., and Tsitsiklis, J.N. Optimal communication algorithms for hypcrcubcs. To appear.
• 7: G. C. Fox , P. Hipes , J. Salmon, Practical parallel supercomputing: examples from chemistry and physics, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.58-69, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76270]
• 8: L. Greengard , V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, v.73 n.2, p.325-348, December 1, 1987 [doi>10.1016/0021-9991(87)90140-9]
• 9: S. Lennart Johnsson , Ching-Tien Ho, Optimum Broadcasting and Personalized Communication in Hypercubes, IEEE Transactions on Computers, v.38 n.9, p.1249-1268, September 1989 [doi>10.1109/12.29465]
• 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.
• 11: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• 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.
• 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.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Physics

General Terms:
Algorithms, Design