MARIOS D. DIKAIAKOS
Departments of Astronomy and Computer Science-Engineering,
University of Washington, ASTRONOMY, Box 351580, Seattle, WA 98195, U.S.A.
and
ANNE ROGERS
Department of Computer Science, Princeton University
Princeton, NJ 08544, U.S.A.
and
KENNETH STEIGLITZ
Department of Computer Science, Princeton University
Princeton, NJ 08544, U.S.A.
Functional Algorithm Simulation is a methodology for predicting the computation and communication characteristics of parallel algorithms for a class of scientific problems, without actually performing the expensive numerical computations involved. In this paper, we use Functional Algorithm Simulation to study the parallel Fast Multipole Method (FMM), which solves the N-body problem. Functional Algorithm Simulation provides us with useful information regarding communication patterns in the algorithm, the variation of available parallelism during different algorithmic phases, and upper bounds on available speedups for different problem sizes. Furthermore, it allows us to predict the performance of the FMM on message-passing multiprocessors with topologies such as cliques, hypercubes, rings, and multirings, over a wider range of problem sizes and numbers of processors than would be feasible by direct simulation. Our simulations show that an implementation of the FMM on low-cost, scalable ring or multiring architectures can attain satisfactory performance. Functional Algorithm Simulation. N-Body Problem. Performance Modeling.