DIMACS TR: 94-27

The Parallel Implementation of N-body Algorithms

Author: Pangfeng Liu


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