A. Caglar, M. Griebel, M. A. Schweitzer, and G. Zumbusch.
Dynamic load-balancing of hierarchical tree algorithms on a cluster
of multiprocessor PCs and on the Cray T3E.
In H. W. Meuer, editor, Proceedings 14th Supercomputer
Conference, Mannheim, ISBN 3-932178-08-4, Mannheim, Germany, 1999. Mateo.
SuParCup '99 Award Winning Paper, also as SFB 256 report 27.
[ bib | .ps.gz 1 | .pdf 1 ]
The solution of many problems in science and engineering is based on computational kernels for the numerical treatment of partial differential equations (PDEs) or N-body problems. Traditional solution methods however reduce these to linear algebra or brute force algorithms on structured data sets. Larger and larger simulations require smarter algorithms to be tractable. Hierarchical tree algorithms represent such a class, both for PDEs and for N-body problems. However, their efficient parallelization is not straightforward. Some difficulties can be removed, if one can provide a fast dynamic load-balancing scheme to cope with the tree variations of the unstructured data sets. In this paper we propose a very cheap yet very efficient load-balancing scheme for tree algorithms based on space-filling curves. Furthermore we present the Parnass2 cluster, on which such parallel codes perform extremely well. The cluster consists of SMP PCs and a Myrinet network at Gigabit/s speed configured with full bisection bandwidth. It turns out that it does not only has the obvious price/performance advantage, but also an absolute performance, which is comparable to the latest commercial Cray T3E.