中國(guó)科技大學(xué)并行計(jì)算課件11快速傅里葉變換

1、并 行 計(jì) 算 中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系國(guó)家高性能計(jì)算中心(合肥)2004年12月2022/9/111現(xiàn)代密碼學(xué)理論與實(shí)踐之五第三篇 并行數(shù)值算法 第八章 基本通訊操作 第九章 稠密矩陣運(yùn)算 第十章 線性方程組的求解 第十一章 快速傅里葉變換 2022/9/112現(xiàn)代密碼學(xué)理論與實(shí)踐之五第十一章 快速傅里葉變換 11.1 快速傅里葉變換 11.2 并行FFT算法 2022/9/113現(xiàn)代密碼學(xué)理論與實(shí)踐之五11.1 快速傅里葉變換(FFT) 11.1.1 離散傅里葉變換(DFT) 11.1.2 DFT的順序代碼 11.1.3 串行FFT遞歸算法 11.1.4 串行FFT非遞歸算法20

2、22/9/114現(xiàn)代密碼學(xué)理論與實(shí)踐之五 離散傅里葉變換(DFT)定義 給定向量A=(a0,a1,an-1)T,DFT將A變換為B=(b0,b1,bn-1)T2022/9/115現(xiàn)代密碼學(xué)理論與實(shí)踐之五11.1 快速傅里葉變換(FFT) 11.1.1 離散傅里葉變換(DFT) 11.1.2 DFT的順序代碼 11.1.3 串行FFT遞歸算法 11.1.4 串行FFT非遞歸算法2022/9/116現(xiàn)代密碼學(xué)理論與實(shí)踐之五 DFT的順序代碼代碼1 for j=0 to n-1 do bj=0 for k=0 to n-1 do bj=bj+k*jak end for end for注：代碼1需要計(jì)

3、算k*j 代碼2的復(fù)雜度為O(n2) 代碼2w=0for j=0 to n-1 do bj=0, s=0 for k=0 to n-1 do bj=bj+s*ak s=s*w end for w=w*end for2022/9/117現(xiàn)代密碼學(xué)理論與實(shí)踐之五11.1 快速傅里葉變換(FFT) 11.1.1 離散傅里葉變換(DFT) 11.1.2 DFT的順序代碼 11.1.3 串行FFT遞歸算法 11.1.4 串行FFT非遞歸算法2022/9/118現(xiàn)代密碼學(xué)理論與實(shí)踐之五 串行FFT遞歸算法蝶式遞歸計(jì)算原理 令 為n/2次單位元根，則有 . 將b向量的偶數(shù)項(xiàng) 和奇數(shù)項(xiàng) 分別記為 和 注意推導(dǎo)

4、中反復(fù)使用2022/9/119現(xiàn)代密碼學(xué)理論與實(shí)踐之五 串行FFT遞歸算法2022/9/1110現(xiàn)代密碼學(xué)理論與實(shí)踐之五 串行FFT遞歸算法2022/9/1111現(xiàn)代密碼學(xué)理論與實(shí)踐之五 串行FFT遞歸算法FFT的蝶式遞歸計(jì)算圖(由計(jì)算原理推出) 2022/9/1112現(xiàn)代密碼學(xué)理論與實(shí)踐之五 串行FFT遞歸算法特別地，n=8的FFT蝶式計(jì)算圖(展開(kāi)的) 2022/9/1113現(xiàn)代密碼學(xué)理論與實(shí)踐之五 串行FFT遞歸算法SISD上的FFT分治遞歸算法 輸入: a=(a0,a1,an-1); 輸出: B=(b0,b1,bn-1) Procedure RFFT(a,b) begin if n=1

5、then b0=a0 else (1)RFFT(a0,a2,an-2, u0,u1,un/2-1) (2)RFFT(a1,a3,an-1, v0,v1,vn/2-1) (3)z=1 (4)for j=0 to n-1 do (4.1)bj=uj mod n/2+zvj mod n/2 (4.2)z=z endfor 注: (1)算法時(shí)間復(fù)雜度t(n)=2t(n/2)+O(n) endif 解得 t(n)=O(nlogn) end (2)算法原理？ 2022/9/1114現(xiàn)代密碼學(xué)理論與實(shí)踐之五11.1 快速傅里葉變換(FFT) 11.1.1 離散傅里葉變換(DFT) 11.1.2 DFT的順序

6、代碼 11.1.3 串行FFT遞歸算法 11.1.4 串行FFT非遞歸算法2022/9/1115現(xiàn)代密碼學(xué)理論與實(shí)踐之五 串行FFT非遞歸算法蝶式計(jì)算示例 2022/9/1116現(xiàn)代密碼學(xué)理論與實(shí)踐之五 串行FFT非遞歸算法蝶式計(jì)算流圖 2022/9/1117現(xiàn)代密碼學(xué)理論與實(shí)踐之五 串行FFT非遞歸算法行0行1行2行3行4行5行6行7如: b6=(a0+a4)-(a2+a6)-(a1+a5)-(a3+a7)2注: 下行線結(jié)點(diǎn)處的權(quán)因子的確定問(wèn)題； bi的下標(biāo)確定:取行號(hào)的位序反。如，行3: 3=(011)2 =(110)2=6, = 行3的輸出為b62022/9/1118現(xiàn)代密碼學(xué)理論與實(shí)踐

7、之五第十一章 快速傅里葉變換 11.1 快速傅里葉變換 11.2 并行FFT算法 2022/9/1119現(xiàn)代密碼學(xué)理論與實(shí)踐之五11.2 并行FFT算法 11.2.1 SIMD-MC2上的FFT算法 11.2.2 SIMD-BF上的FFT算法 2022/9/1120現(xiàn)代密碼學(xué)理論與實(shí)踐之五 SIMD-MC2上的FFT算法算法描述n個(gè)處理器組成n1/2n1/2的方陣, 處理器以行主序編號(hào)2022/9/1121現(xiàn)代密碼學(xué)理論與實(shí)踐之五 SIMD-MC2上的FFT算法算法11.3(P270): 輸入: ak處于Pk中; 輸出bk處于Pk中 Begin (1)for k=0 to n-1 par-do

8、 ck=ak endfor (2)for h=logn-1 to 0 do for k=0 to n-1 par-do (2.1)p=2h (2.2)q=n/p (2.3)z=p /先算出n/2,以后每次z=z1/2 (2.4)if ( k mod p = k mod 2p) then par-do /滿足條件的處理器同時(shí)做 (i) ck=ck+ck+pzr(k)modq /(i)和(ii)同時(shí)執(zhí)行 (ii)ckp=ck-ck+pzr(k)modq endif endfor endfor (3)for k=0 to n-1 par-do bk=cr(k) endfor /r(k)為k的位序反

9、End 如：n=16h=3, p=8, q=2, z=8 h=2, p=4, q=4, z=4h=1, p=2, q=8, z=2h=0, p=1, q=16,z=12022/9/1122現(xiàn)代密碼學(xué)理論與實(shí)踐之五 SIMD-MC2上的FFT算法示例: P271例11.5, n=4 第(1)步：2022/9/1123現(xiàn)代密碼學(xué)理論與實(shí)踐之五 SIMD-MC2上的FFT算法第(2)步: 第1次迭代(h=1): p=2, q=2, z=2 滿足k mod 2 = k mod 4的處理器為P0和P1, 同時(shí)計(jì)算 P0: c0=c0+(2)0c2=a0+a2 P1: c1=c1+(2)0c3=a1+a3

10、 c2=c0-(2)0c2=a0-a2 c3=c1-(2)0c3=a1-a3 2022/9/1124現(xiàn)代密碼學(xué)理論與實(shí)踐之五 SIMD-MC2上的FFT算法第(2)步: 第2次迭代(h=0): p=1, q=4, z= 滿足k mod 1 = k mod 2的處理器為P0和P2, 同時(shí)計(jì)算 P0: c0=c0+0c1=(a0+a2)+(a1+a3) P2: c1=c1+1c3=(a0+a2)+(a1+a3) c1=c0-0c1=(a0+a2)-(a1+a3) c3=c1-1c3=(a0+a2)+(a1+a3)2022/9/1125現(xiàn)代密碼學(xué)理論與實(shí)踐之五 SIMD-MC2上的FFT算法第(3)

11、步: b0=c0, b1=c2, b2=c1, b3=c3算法分析計(jì)算時(shí)間: tcomp=O(logn)選路時(shí)間: trouting: 只涉及(2.4)和(3) (2.4): O(n1/2) (3): O(n1/2) 綜上, 當(dāng)n較大時(shí)t(n)=O(n1/2)2022/9/1126現(xiàn)代密碼學(xué)理論與實(shí)踐之五11.2 并行FFT算法 11.2.1 SIMD-MC2上的FFT算法 11.2.2 SIMD-BF上的FFT算法 2022/9/1127現(xiàn)代密碼學(xué)理論與實(shí)踐之五 SIMD-BF上的FFT算法蝶形網(wǎng)絡(luò)處理器布局 有k+1層, 每層有n=2k個(gè)處理器, 共有n(1+logn)個(gè)處理器 第r行第i

12、列的處理器記為Pr,i, i=(a1,a2,ak)2互連方式 Pr,i與上層Pr-1,i, Pr-1,j相連, 這里i的第r位為0 Pr,j與上層Pr-1,i, Pr-1,j相連, 這里j與i僅在第r位不同權(quán)因子在BF網(wǎng)絡(luò)中的計(jì)算方法 Pr,i中的指數(shù)為j=exp(r,i) 這里exp(r,i)=(ar,a1,0,0) /即i的前r位取位序反,再后補(bǔ)0 k-r2022/9/1128現(xiàn)代密碼學(xué)理論與實(shí)踐之五 SIMD-BF上的FFT算法示例: n=8的BF網(wǎng)絡(luò)表示 r,i與上層Pr-1,i, Pr-1,j相連, 這里i的第r位為0 Pr,j與上層Pr-1,i, Pr-1,j相連, 這里j與i僅在第r位不同2022/9/1129現(xiàn)代密碼學(xué)理論與實(shí)踐之五 SIMD-BF上的FFT算法算法描述: P272算法11.4算法分析算法的正確性可以用歸納法證明時(shí)間分析 第(1)步時(shí)間: O(1) (2.1)和(2.2)的計(jì)算時(shí)間為O(1), (假定exp(r,i)已計(jì)算好) (2.1)和(2.2)的選路時(shí)間為O(1) =第(2)步時(shí)間: O(logn) 所以 t(n)=O(logn), p(n)=n(1+l