The Impact of Data Ordering Strategies on a Distributed
Hierarchical Multipole Algorithm
William T. Rankin,
John A. Board, Jr.
and Valerie L. Henderson
Abstract
We present an analysis of the communications and performance
implications of different data mapping schemes for a distributed
multipole-based N-body algorithm. Hierarchical multipole-based
algorithms provide an $O(N)$ solution for the computation of N-body
interactions and are used extensively in a number of research fields.
In this paper, we will compare the use of Morton, Hilbert and
row/column ordering for the mapping of the hierarchical oct-tree
structures onto an arbitrary number of distributed processing
elements. The intent of these investigations is to determine the
optimal strategy to maximize spatial locality and minimize data
movement between processors. In most cases, Hilbert ordering proves
to be the best. Results are presented which describe both network
bandwidth requirements, as well as the overall performance impact of
the various orderings
Back to the Scientific Computions Group Home Page