Are we there yet?

Martin Siegert siegert at
Tue Jul 18 16:56:03 PDT 2000

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.
> 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 Siegert
Academic Computing Services                        phone: (604) 291-4691
Simon Fraser University                            fax:   (604) 291-4242
Burnaby, British Columbia                          email: siegert at
Canada  V5A 1S6

More information about the Beowulf mailing list