Fast Fourier Transforms.pdf

(796 KB) Pobierz
Fast Fourier Transforms (FFTs)
and Graphical Processing Units
(GPUs)
Kate Despain
CMSC828e
– p. 1/3
Outline
•
•
•
•
Motivation
Introduction to FFTs
•
Discrete Fourier Transforms (DFTs)
•
Cooley-Tukey Algorithm
CUFFT Library
High Performance DFTs on GPUs by Microsoft
Corporation
•
Coalescing
•
Use of Shared Memory
•
Calculation-rich Kernels
– p. 2/3
Motivation: Uses of FFTs
•
Scientific Computing: Method to solve
differential equations
For example, in Quantum Mechanics (or Electricity &
Magnetism) we often assume solutions to Schrodinger’s
Equation (or Maxwell’s equations) to be plane waves,
which are built on a Fourier basis
∞
A
=
k=−∞
A
0
e
ikx
Then, in
k-space,
derivative operators become
multiplications
∂A
ikx
A
0
ke
=
i
∂x
k=−∞
∞
– p. 3/3
Motivation: Uses of FFTs
•
•
Digital Signal Processing & Image Processing
•
Receive signal in the time domain, but want
the frequency spectrum
Convolutions/Filters
•
Filter can be represented mathematically by a
convolution
•
Using the convolution theorem and FFTs,
filters can be implemented efficiently
Convolution Theorem: The Fourier transform of a
convolution is the product of the Fourier transforms of the
convoluted elements.
– p. 4/3
Introduciton: What is an FFT?
•
Algorithm to compute Discrete Fourier
Transform (DFT)
•
Straightforward implementation requires
O
N
2
MADD operations
2πi
x
n
exp
−
X
k
=
kn
N
n=0
N
−1
– p. 5/3

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin