Embedding a "Tree-Code" on a MIMD Parallel Computer
Using a Domain Decomposition Paradigm

Gavin J. Pringle
Napier University
Edinburgh
EH14 1DJ
SCOTLAND

Abstract

"Tree-codes" and "Multigrid" methods are both hierarchical, recursive algorithms for solving vector field equations, faster than traditional methods. If the methods are non-adaptive, then both Tree-codes and Multigrid methods require identical parallel communication strategies since they share the same internal structure.

This paper contains a description of Tree-codes followed by an overview of one Tree-code in particular, namely the Greengard-Rokhlin Fast Multipole Method in 2 dimensions. The parallel version of this method is then discussed at length with the presentation of two communication strategies; An "All-to-all" broadcast and a routine which enables neighbouring transputers to swap information in a predetermined sequence.

The computer used is the Meiko Computing Surface, a MIMD parallel computer employing T800 transputers running the CSTools communication harness using a SPMD (Single Program, Multiple Data), domain decomposition paradigm.

The 3D versions of the communication algorithms have also been implemented and are simple extensions of the 2D routines.

Keywords: Fast Multipole Method, Multigrid, message passing.


Contributed March 31, 1993.