Beowulf & FFT

[Martin Siegert]

On Tue, 18 Jul 2000, Walter B. Ligon III wrote:

> > Since I'm in the process of expanding the beowulf, I'm wondering whether
> > switching to 133 MHz would improve the results (given that I can find
> > a motherboard that supports ECC - we had that discussion).
> 
> Generally, if the problem is that node-to-node communication is too slow,
> upping your system bus speed isn't going to do much in the way of improving
> your parallel system performance.

True. However, I'm not completely convinced that node-to-node communication
is the only limiting factor: The efficiency for np=2 is miserable as well.
And that should be shared-memory communication (at least in mpich-1.2.0).

> The first thing that strikes me is that a 400x400 operation is pretty small
> for a Beowulf.  Its going to be hard to get good efficiency on a small
> problem like that.

This is correct. The efficiency gets better, when I go to 1600x1600, but it's
still misreable: speedup=1.25 for np=2. Furthermore, in my problem time scales
with length to third or fourth power. Thus, I can't take advantage of the
larger system sizes, if don't go to much, much later times.

> I am not familliar with the FFT library you have, but it may be that it was
> not designed for a machine like a Beowulf, but rather for a finer grain
> machine like some of the MPPs.  Thus the best approach may be a different
> bit of software, or reworking that software.  All-to-All is probably NOT
> the best implementation on an MPI running over TCP/IP.

The authors of FFTW claim that this is the fastest FFT you can get. I can only
say that from all I know this statement is correct, i.e., all other FFTs 
that I tried were slower. Actually I wasted a month by writing my own FFT
only to find out that is was slower as well :-(
Furthermore, I can't really see how the necessary matrix transpose can be
done more efficiently without the Alltoall.

> Of course, you could always upgrade to a faster network if you have the $$$.

Yup. That would be nice.

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
========================================================================