An Efficient Program for Many-Body Simulations (or, Cray Performance from a VAX).
Abstract
The simulation of N particles interacting in a gravitational force field is useful in astrophysics, but such simulations become costly for large N. Representing the universe as a tree structure with the particles at the leaves and internal nodes labelled with the centers of mass of their descendants allows several simultaneous attacks on the computation time required by the problem. These approaches range from algorithmic changes (replacing an O(N2) algorithm with an O(N log N) algorithm) to data structure modifications, code-tuning, and hardware modifications. The changes reduced the running time of a large problem (N = 10,000) by a factor of four hundred. This paper describes both the particular program and the methodology underlying such speedups.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1983
- Accession Number
- ADA129676
Entities
People
- Andrew Appel
Organizations
- Carnegie Mellon University