University:
Boston University
Course:
ENG EC 410 | Introduction to Electronics
Academic year:

2023
Views:

127

Pages:

14
Author:

szkafut4kac

GPU Computing with CUDA CUDA Libraries - CUFFT, PyCUDA Outline of lecture ‣ Overview: - Discrete Fourier Transform (DFT) - Fast Fourier Transform (FFT) ‣ Algorithm ‣ Motivation, examples ‣ CUFFT: A CUDA based FFT library ‣ PyCUDA: GPU computing using scripting languages 2 CUDA Libraries Bell, Dalton, Olson. Towards AMG on GPU 3 Fourier Transform ‣ Fourier Transform û(k) = ! ∞ e−ikx u(x)dx Real Wave Wave Real −∞ ‣ Inverse Fourier Transform u(x) = ! ∞ −∞ ikx e û(k)dk 4 Discrete Fourier Transform (DFT) ‣ The case of discrete u(x) we have aliasing Real Discrete, bounded Wave Bounded, discrete sin(x) sin(5x) Values at sample points repeat at k2 = k1+N sin(3x) sin(7x) 5 Discrete Fourier Transform (DFT) ‣ DFT ûk = N −1 ! − 2πi N kj uj e j=0 k = 0, 1, ..., N − 1 ‣ Inverse DFT uj = N −1 ! k=0 ûk e 2πi N kj j = 0, 1, ..., N − 1 6 Fast Fourier Transform (FFT) ‣ Fast method to calculate the DFT ‣ Computations drop from O(N 2 ) to O(N log(N )) - N = 104: ‣ Naive: 108 computations ‣ FFT: 4*104 computations Huge reduction! ‣ Many algorithms, let’s look at Cooley-Tukey radix-2 7 Fast Fourier Transform (FFT) ‣ Cooley-Tukey radix 2 - Assume N being a power of 2 ûk = N −1 ! − 2πi N kj uj e j=0 Divide sum into even and odd parts N/2−1 ûk = ! j=0 − 2πi N k(2j) u2j e N/2−1 + ! − 2πi N k(2j+1) u2j+1 e j=0 8 Fast Fourier Transform (FFT) ‣ Cooley-Tukey radix 2 - Assume N being a power of 2 ûk = N −1 ! − 2πi N kj uj e j=0 Divide sum into even and odd parts N/2−1 ûk = ! − 2πi N k(2j) u2j e N/2−1 + ! − 2πi N k(2j+1) u2j+1 e j=0 j=0 Even Odd 8 Fast Fourier Transform (FFT) N/2−1 ûk = ! 2πi − N/2 kj u2j e − 2πi N k +e N/2−1 ! 2πi − N/2 kj u2j+1 e j=0 j=0 ‣ By doing this recursively until there is no sum, you get log(N) levels ‣ Sum is decomposed and redundant operations appear ‣ 4 point transform − 2π 4 ik ûk = u0 + u1 e + u2 e − 2π 4 i2k ûk = u0 + u2 e ûk = u0 + u2 e −πik − 2π 4 i2k − 2π 4 ik +e −π 2 ik +e − 2π 4 i3k + u3 e − 2π 4 i2k (u1 + u3 e ) (u1 + u3 e−πik ) k = 0, 1, 2, 3 9 Fast Fourier Transform (FFT) û0 = u0 + u2 e0 + e0 (u1 + u3 e0 ) −πi −π û1 = u0 + u2 e + e 2 i (u1 + u3 e−πi ) û2 = u0 + u2 e + e (u1 + u3 e ) −3πi −3 π û3 = u0 + u2 e + e 2 i (u1 + u3 e−3πi ) −2πi periodicity ⇒ e = e 0 u0 −2πi = 1, û0 u2 û1 u1 û2 u3 û3 −πi −πi e −2πi =e −3πi = −1 10 FFT - Motivation ‣ Signal processing - Signal comes in time domain, but want the frequency spectrum ‣ Convolution, filters - Signals can be filtered with convolutions ! 0 t f (s)g(t − s) ds, 0≤t<∞ F{f ∗ g} = F{f } · F{g} 11 FFT - Motivation ‣ Partial Differential Equations (PDEs) - Spectral methods - Use DFTs to calculate derivatives uj = N −1 ! ûk e 2πi N kj 2π j = xj N For evenly spaced grid k=0 uj = N −1 ! ûk eikxj k=0 ∂uj = ∂x 2 ∂ uj = 2 ∂x N −1 ! ikxj ikûk e k=0 N −1 ! k=0 ! ∂u = ikû ∂x −k 2 ûk eikxj 12 FFT - Motivation ‣ Advantages - Spectral accuracy O(cN ) 0