|
Remembering that first computations are performed at phase d-1, we see that one needs communication for the first few (P phases) as dependency lines cross boundaries. For the final phases all the information needed for FFT component is stored within processor.
|
So communication needed for phases d-1 through d-P
-
These are phases labeled by the digits used to label Processor and not position in the processor
|
|
No communication at all for phases d-P-1 through 0
|
Note end result -- the FFT GN(k,f) -- is bit reversed: we will discuss later the communication cost of undoing bit reversal but
-
In many cases, bit reversal is unimportant and FFT does not need to be reversed.
-
For instance in solving Poisson's equation, FFT is followed by inverse FFT and in final result, there is no bit reversal
|
