FFT_SERIAL
Fast Fourier Transform

FFT_SERIAL is a C 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 4.943500e-07 20.2

4 1.217550e-06 32.8

8 2.283850e-06 52.5

16 5.334400e-06 59.9

32 1.051800e-05 76.0

64 2.125550e-05 90.3

128 3.229850e-05 138.7

256 7.576800e-05 135.1

512 1.544650e-04 149.1

1024 3.537100e-04 144.7

2048 7.222600e-04 155.9

4096 1.636675e-03 150.1

8192 3.392550e-03 156.9

16384 7.518900e-03 152.5

32768 1.601240e-02 153.4

65536 3.534380e-02 148.3

131072 7.358900e-02 151.3

262144 1.712250e-01 137.78

524288 3.547840e-01 140.3

1048576 7.744890e-01 135.3

N	Time	MegaFLOPS
2	4.943500e-07	20.2
4	1.217550e-06	32.8
8	2.283850e-06	52.5
16	5.334400e-06	59.9
32	1.051800e-05	76.0
64	2.125550e-05	90.3
128	3.229850e-05	138.7
256	7.576800e-05	135.1
512	1.544650e-04	149.1
1024	3.537100e-04	144.7
2048	7.222600e-04	155.9
4096	1.636675e-03	150.1
8192	3.392550e-03	156.9
16384	7.518900e-03	152.5
32768	1.601240e-02	153.4
65536	3.534380e-02	148.3
131072	7.358900e-02	151.3
262144	1.712250e-01	137.78
524288	3.547840e-01	140.3
1048576	7.744890e-01	135.3

Related Data and Programs:

BT_SERIAL is a FORTRAN90 program which is a serial version of the NAS Parallel Benchmark BT (block tridiagonal solver for a 3D PDE).

CG_SERIAL is a FORTRAN77 program which is a serial version of the NAS Parallel Benchmark CG (conjugate gradient solver).

EP_SERIAL is a FORTRAN77 program which is a serial version of the NAS Parallel Benchmark EP (embarassingly parallel).

FFT_OPEN_MP is a C program which computes a Fast Fourier Transform 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 C 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.

IS_SERIAL is a C program which is a serial version of the NAS Parallel Benchmark IS (integer sort).

MD is a C 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 C 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.c, 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 C source codes.