Michael T. Prinkey
mprinkey at aeolusresearch.com
Thu Dec 14 05:23:56 PST 2000
> If the ODE's are long range, and the step of the ith node depends on the
> state of all N-1 other nodes, well, you may have a problem that just
> doesn't parallelize very well, at least on the less expensive beowulf
> architectures. In that case, your alternatives are to spend a lot more
> money on communications than on computation -- buy a truly high speed
> network like e.g. Myrinet and use it with relatively cheap and slow
> processors, and you might be able to scale up to some decent limit.
> Greg Lindahl has presented studies of alpha/myrinet clusters that scaled
> well for e.g. gravitation problems (another long range interaction) that
> might be relevant at Linux Expo (the one in Raleigh a year and a half
> ago) that are probably in the proceedings.
Well put, Dr. Brown. Just to expand on this point a bit, the presence
of long distance interactions do not automatically preclude efficient
parallelization, even over fast ethernet. The LANL folks hve a nice
code that (I think) uses multipole expansions for long range
interactions. (http://loki-www.lanl.gov/papers/) Effectively, this
lumps distant effects into a few terms in an perturbative expansion.
There is a truncation error that typically scales as some power of 1/r
so for distant particles, you get good results with a few terms. For
nearby particles, you need to do the full potential/force calculation
particle by particle. They also typically use quad-tree or oct-tree
storage structures as part of the decomposition/multipole expansion
strategy. Those keywords and the LANL papers should probably get you
started. Note too that the multipole approach is very useful even for
serial code. For N particles, the full (naive) interaction algorithm
scales as O(N^2). With multipole approaches, I believe that this can
drop to O(N ln N) or lower. Those are important when N ~ 10^6 and
Aeolus Research, Inc.
More information about the Beowulf