@inproceedings{Caglar.Griebel.Schweitzer.ea:1999,
author = {A. Caglar and M. Griebel and M. A. Schweitzer and G.
Zumbusch},
title = {Dynamic Load-Balancing of Hierarchical Tree Algorithms on
a Cluster of Multiprocessor {PC}s and on the {C}ray
{T}3{E}},
booktitle = {Proceedings 14th Supercomputer Conference, Mannheim},
year = {1999},
editor = {H. W. Meuer},
series = {ISBN 3-932178-08-4},
publisher = {Mateo},
address = {Mannheim, Germany},
note = {SuParCup '99 Award Winning Paper, also as SFB 256 report
27},
ps = {http://wissrech.ins.uni-bonn.de/research/pub/zumbusch/suparcup99.ps.gz 1},
pdf = {http://wissrech.ins.uni-bonn.de/research/pub/zumbusch/suparcup99.pdf 1},
annote = {refereed series,256D,parallel},
abstract = {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.}
}
