Are we there yet?

[Martin Siegert]

On Tue, 18 Jul 2000, Tom Moline wrote:

> Martin Siegert mentions using "fast FFTs to integrate PDEs using spectral
> methods". He further delineates a classic example of MPI becoming part of
> the problem rather than part of the solution.
<snip>
> We have quite a distance to cover in understanding the algorithmic
> implications of the "Beowulf" effect.  No one has the same HW and SW setup,
> and no one is handling the same sets of computational problems. (Please
> correct me if I am wrong.)  Part of the beauty of this beast is the diversity
> of usage and solutions.  Perhaps some of the better funded university
> entities on this list would consider a competition based on the same physical
> and logical setups with a common problem to solve.  The resulting products
> could provide some algorithmic stability to the ongoing discussions.

Actually, FFTs (in more than one dimension) are not complicated with respect
to MPI: the MPI_Alltoall call is all that is needed. Unfortunaltely, 
it requires communication between all pairs of processors, which doesn't
seem to be feasable with fast ethernet - not even for a small number of
processors. Hence, it is probably not too difficult to come up with a
rule for good and bad algorithms for PDEs on a beowulf: all algorithms
that require pairwise communications (e.g., implicit and spectral methods)
are "bad", all that require communication only with "neighbouring"
processors (finite differences in combination with Euler, Predictor-Corrector,
etc.) are "good". We don't really need a competition to figure this out -
we just have to recognize that the classification into good and bad that
we learned in numerical math classes (for serial programs) don't apply
to beowulfs.

Martin

========================================================================
Martin Siegert
Academic Computing Services                        phone: (604) 291-4691
Simon Fraser University                            fax:   (604) 291-4242
Burnaby, British Columbia                          email: siegert at sfu.ca
Canada  V5A 1S6
========================================================================