Statistics – Computation
Scientific paper
Aug 1994
adsabs.harvard.edu/cgi-bin/nph-data_query?bibcode=1994apjs...94..117o&link_type=abstract
The Astrophysical Journal Supplement Series (ISSN, 0067-0049), vol. 94, no. 1, September 1994, p. 117-125
Statistics
Computation
5
Algorithms, Computational Astrophysics, Computerized Simulation, Gravitation, Many Body Problem, Parallel Processing (Computers), Simd (Computers), Trees (Mathematics), Cost Analysis, Cray Computers, Disk Galaxies, Inflating, Interacting Galaxies, Mimd (Computers), Optimization, Universe
Scientific paper
We describe a fast tree algorithm for gravitational N-body simulation on SIMD parallel computers. The tree construction uses fast, parallel sorts. The sorted lists are recursively divided along their x, y and z coordinates. This data structure is a completely balanced tree (i.e., each particle is paired with exactly one other particle) and maintains good spatial locality. An implementation of this tree-building algorithm on a 16k processor Maspar MP-1 performs well and constitutes only a small fraction (approximately 15%) of the entire cycle of finding the accelerations. Each node in the tree is treated as a monopole. The tree search and the summation of accelerations also perform well. During the tree search, node data that is needed from another processor is simply fetched. Roughly 55% of the tree search time is spent in communications between processors. We apply the code to two problems of astrophysical interest. The first is a simulation of the close passage of two gravitationally, interacting, disk galaxies using 65,636 particles. We also simulate the formation of structure in an expanding, model universe using 1,048,576 particles. Our code attains speeds comparable to one head of a Cray Y-MP, so single instruction, multiple data (SIMD) type computers can be used for these simulations. The cost/performance ratio for SIMD machines like the Maspar MP-1 make them an extremely attractive alternative to either vector processors or large multiple instruction, multiple data (MIMD) type parallel computers. With further optimizations (e.g., more careful load balancing), speeds in excess of today's vector processing computers should be possible.
Dorband John E.
Olson Kevin M.
No associations
LandOfFree
An implementation of a tree code on a SIMD, parallel computer does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An implementation of a tree code on a SIMD, parallel computer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An implementation of a tree code on a SIMD, parallel computer will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-1494764