An Efficient Program for Many-Body Simulations (or, Cray Performance from a VAX).
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 ON2 algorithm with an ON 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.
- Theoretical Mathematics
- Computer Programming and Software