FFT_SERIAL
Fast Fourier Transform

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

On an Apple PowerPC G5 with two processors, the following results were observed:

N Time MegaFLOPS

2 0.1134E-05 8.822

4 0.2358E-05 16.96

8 0.3859E-05 31.10

16 0.5845E-05 54.74

32 0.8674E-05 92.23

64 0.1886E-04 101.8

128 0.3590E-04 124.8

256 0.8220E-04 124.6

512 0.1629E-03 141.4

1024 0.3740E-03 136.9

2048 0.7607E-03 148.1

4096 0.1722E-02 142.7

8192 0.3535E-02 150.6

16384 0.8448E-02 135.8

32768 0.1898E-01 129.5

65536 0.4216E-01 124.3

131072 0.8598E-01 129.6

N	Time	MegaFLOPS
2	0.1134E-05	8.822
4	0.2358E-05	16.96
8	0.3859E-05	31.10
16	0.5845E-05	54.74
32	0.8674E-05	92.23
64	0.1886E-04	101.8
128	0.3590E-04	124.8
256	0.8220E-04	124.6
512	0.1629E-03	141.4
1024	0.3740E-03	136.9
2048	0.7607E-03	148.1
4096	0.1722E-02	142.7
8192	0.3535E-02	150.6
16384	0.8448E-02	135.8
32768	0.1898E-01	129.5
65536	0.4216E-01	124.3
131072	0.8598E-01	129.6

Related Data and Programs:

FFT_OPEN_MP is a FORTRAN77 program which demonstrates the computation of a Fast Fourier Transform in parallel, using OpenMP.

FFT_SERIAL is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

HEATED_PLATE is a FORTRAN77 program which solves the steady state heat equation in a 2D rectangular region, and is intended as a starting point for implementing an OpenMP parallel version.

MD is a FORTRAN77 program which carries out a molecular dynamics simulation, and is intended as a starting point for developing a parallel version using OpenMP.

OPEN_MP is a directory of FORTRAN77 examples which illustrate the use of the OpenMP application program interface for carrying out parallel computations in a shared memory environment.

Reference:

Wesley Petersen, Peter Arbenz,
Introduction to Parallel Computing - A practical guide with examples in C,
Oxford University Press,
ISBN: 0-19-851576-6,
LC: QA76.58.P47.
Rohit Chandra, Leonardo Dagum, Dave Kohr, Dror Maydan, Jeff McDonald, Ramesh Menon,
Parallel Programming in OpenMP,
Morgan Kaufmann, 2001,
ISBN: 1-55860-671-8,
LC: QA76.642.P32.
Barbara Chapman, Gabriele Jost, Ruud vanderPas, David Kuck,
Using OpenMP: Portable Shared Memory Parallel Processing,
MIT Press, 2007,
ISBN13: 978-0262533027,
LC: QA76.642.C49.

Source Code:

fft_serial.f, the source code.
fft_serial.sh, commands to compile, link and load the program.

Examples and Tests:

fft_serial_output.txt, the output file.

List of Routines:

MAIN is the main program for FFT_SERIAL.
CCOPY copies a complex vector.
CFFT2 performs a complex Fast Fourier Transform.
CFFTI sets up sine and cosine tables needed for the FFT calculation.
GGL generates u(0,1) distributed random numbers.
STEP carries out one step of the workspace version of CFFT2.

You can go up one level to the FORTRAN77 source codes.