FFT
Fast Fourier Transform

FFT is a program which demonstrates the computation of a Fast Fourier Transform, and is intended as a starting point for developing a parallel version using OpenMP.

The program chooses a problem size N, sets up data, computes the FFT of the data, and then inverts the FFT to recover the original data. The program is able to estimate the number of floating point operations for this calculation. It measures the CPU time, and so is able to produce a MegaFLOPS rate. The value of N is varied, by doubling, from 2 all the way to 1,048,576.

By observing the pattern in the MegaFLOPS rate, it is possible to estimate the range of values of N for which the computer is performing at a peak rate, or within 50% of that peak rate.

Source Code:

• fft.c, the C source code.
• fft.cc, the C++ source code.
• fft.f, the FORTRAN77 source code.
• fft.f90, the FORTRAN90 source code.

Completed Source Code:

Here are "completed" versions of the programs.
(Access to these files may be restricted until everyone has had a chance to work on the problems!)

• fft_complete.c, the C source code.
• fft_complete.cc, the C++ source code.
• fft_complete.f, the FORTRAN77 source code.
• fft_complete.f90, the FORTRAN90 source code.

Batch Script:

Once you have made a fft executable, you need to copy this script file to the same directory that contains the executable, and issue the command qsub fft.sh. That submits a request to have the executable program run on 4 processors. You can type showq to see if the request has started yet.

• fft.sh, a script to run the program.
• fft_output.txt, the output file.

You can go up one level to the OpenMP page.