DIMACS TR: 94-27
The Parallel Implementation of N-body Algorithms
Author: Pangfeng Liu
ABSTRACT
This dissertation studies issues critical to efficient N-body
simulations on parallel computers. The N-body problem poses several
challenges for distributed-memory implementation: adaptive distributed
data structures, irregular data access patterns, and irregular and
adaptive communication patterns. We introduce new techniques to
maintain dynamic irregular data structures, to vectorize irregular
computational structures, and for efficient communication. We report
results from experiments on the Connection Machine CM-5. The results
demonstrate the performance advantages of design simplicity; the code
provides generality of use on various message-passing architectures.
Our methods have been used as the basis of a C++ library that provides
abstractions for tree computations to ease the development of
different N-body codes.
This dissertation also presents the {\em atomic message model} to
capture the important factors of efficient communication in
message-passing systems. The atomic model was motivated by the
problem of transferring large messages in a system with limited
communication resources and bandwidth at each node. Although the
atomic model imposes strict constraints, we show that simple
randomized protocols nonetheless provide high communication
throughput.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-27.ps
DIMACS Home Page