Computational Structure of the N-Body Problem
Abstract
This work considers tree algorithms for the N body problem where the number of particles is on the order of a million. The main concern of this work is the organization and performance of these computations on parallel computers. The work introduces a formulation of the N-body problem as a set of recursive equations based on a few elementary functions. It is shown that both the algorithm of Barnes-Hut and that of Greengard-Rokhlin satisfy these equations using different elementary functions. The recursive formulation leads directly to a computational structure in the form of a pyramid-like graph, where each vertex is a process, and each arc a communication link. The pyramid is mapped to three different processor configurations: (1) A pyramid of processors corresponding to the processes pyramid graph; (2) An hypercube of processors, e. g., a connection-machine like architecture. (3) A rather small array, e.g., 2 x 2 x 2, of processors faster then the ones consider in (1) and (2) above. The main conclusion is that simulations of this size can be performed on any of the three architectures in reasonable time. 20 seconds per time step is the estimate for a million equally distributed particles using the Greengard-Rokhlin algorithm on the CM-2 connection machine. The smaller array of processors is quite competitive in performance. Keywords: N body problem; Particle simulation; Artificial intelligence; Tree algorithms; Parallel computing.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1988
- Accession Number
- ADA196422
Entities
People
- Jacob Katzenelson
Organizations
- Massachusetts Institute of Technology