The Welchel phase-rotation FFT is a new form of the fast Fourier transform (FFT) that replaces data movement at runtime with equivalent multiplications by precomputed constants. The result is an FFT that is easy to pipeline.
An F77 program that completely specifies the 1D algorithm is available as a compressed Unix tar file. The program is designed to be a tutorial on the systolic version of the phase-rotation FFT, and thus is written directly in terms of the stages in the systolic pipeline, which is described in the following companion paper:
D. O'Hallaron, P. Lieu, L. Withers, and J. Whelchel, Computing the pipelined phase rotation FFT, Scalable High Performance Computing Conference, Knoxville, TN, May, 1994, pp. 462-469. ( abstract, ps, pdf. )
After downloading the tar file, type "uncompress phase1.tar.Z" to uncompress it, followed by "tar -xvf phase1.tar" to expand it. The resulting directory, phase1, contains the following files:
| File | Description |
|---|---|
| README | Introduction and list of files |
| makefile | Type "make" to produce the executable "phase1" |
| phase1.h | Some constants |
| phase1.f | Main program |
| rotators.f | Routines that precompute rotators |
| shuffle.f | Routines that shuffle data |
| matrix.f | Various matrix utilities |
| shpcc94.ps | The companion paper |
Questions and comments can be directed to Dave O'Hallaron at droh@cs.cmu.edu.