Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation

  author = {A. Caglar and M. Griebel and M. A. Schweitzer and G.
  title = {Dynamic Load-Balancing of Hierarchical Tree Algorithms on
		  a Cluster of Multiprocessor {PC}s and on the {C}ray
  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
  ps = { 1},
  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.}