《10 中國科技大學(xué) 并行計(jì)算 教案 第十一章 快速傅里葉變換》由會(huì)員分享，可在線閱讀，更多相關(guān)《10 中國科技大學(xué) 并行計(jì)算 教案 第十一章 快速傅里葉變換（30頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、并行計(jì)算,第一級(jí),第二級(jí),第三級(jí),第一級(jí),第二級(jí),第三級(jí),國家高性能計(jì)算中心（合肥）,*,*,并 行 計(jì) 算,中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,國家高性能計(jì)算中心,(,合肥,),2004,年,12,月,第三篇 并行數(shù)值算法,第八章 基本通訊操作,第九章 稠密矩陣運(yùn)算,第十章 線性方程組的求解,第十一章,快速傅里葉變換,第十一章 快速傅里葉變換,11.1,快速傅里葉變換,11.2,并行,FFT,算法,11.1,快速傅里葉變換,(FFT),11.1.1,離散傅里葉變換,(DFT),11.1.2,DFT,的順序代碼,11.1.3,串行,FFT,遞歸算法,11.1.4,串行,FFT,非遞歸算法,離散

2、傅里葉變換,(DFT),定義,給定向量,A=(a,0,a,1,a,n-1,),T,DFT,將,A,變換為,B=(b,0,b,1,b,n-1,),T,2024/10/12,5,國家高性能計(jì)算中心（合肥）,11.1,快速傅里葉變換,(FFT),11.1.1,離散傅里葉變換,(DFT),11.1.2,DFT,的順序代碼,11.1.3,串行,FFT,遞歸算法,11.1.4,串行,FFT,非遞歸算法,DFT,的順序代碼,代碼,1,for j=0 to n-1 do,bj,=0,for k=0 to n-1 do,bj,=,bj+,k,*,j,ak,end for,end for,注：,代碼,1,需要計(jì)算

3、,k,*j,代碼,2,的復(fù)雜度為,O(n,2,),代碼,2,w=,0,for 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 for,2024/10/12,7,國家高性能計(jì)算中心（合肥）,11.1,快速傅里葉變換,(FFT),11.1.1,離散傅里葉變換,(DFT),11.1.2,DFT,的順序代碼,11.1.3,串行,FFT,遞歸算法,11.1.4,串行,FFT,非遞歸算法,串行,FFT,遞歸算法,蝶式遞歸計(jì)算原理,令 為,n/2,次單位元根，則有,.,將,b,向量的偶數(shù)項(xiàng) 和奇

4、數(shù)項(xiàng) 分別記為,和,注意推導(dǎo)中反復(fù)使用,2024/10/12,9,國家高性能計(jì)算中心（合肥）,串行,FFT,遞歸算法,2024/10/12,10,國家高性能計(jì)算中心（合肥）,串行,FFT,遞歸算法,2024/10/12,11,國家高性能計(jì)算中心（合肥）,串行,FFT,遞歸算法,FFT,的蝶式遞歸計(jì)算圖,(,由計(jì)算原理推出,),2024/10/12,12,國家高性能計(jì)算中心（合肥）,串行,FFT,遞歸算法,特別地，,n=8,的,FFT,蝶式計(jì)算圖,(,展開的,),2024/10/12,13,國家高性能計(jì)算中心（合肥）,串行,FFT,遞歸算法,SISD,上的,FFT,分治遞歸算法,輸入,:a=(a

5、,0,a,1,a,n-1,);,輸出,:B=(b,0,b,1,b,n-1,),Procedure,RFFT(a,b,),begin,if n=1 then b,0,=a,0,else,(1)RFFT(a,0,a,2,a,n-2,u,0,u,1,u,n/2-1,),(2)RFFT(a,1,a,3,a,n-1,v,0,v,1,v,n/2-1,),(3)z=1,(4)for j=0 to n-1 do,(4.1)b,j,=,u,j,mod n/2,+zv,j mod n/2,(4.2)z=,z,endfor,注,:(1),算法時(shí)間復(fù)雜度,t(n,)=2t(n/2)+O(n),endif,解得,t(n

6、,)=,O(nlogn,),end,(2),算法原理？,2024/10/12,14,國家高性能計(jì)算中心（合肥）,11.1,快速傅里葉變換,(FFT),11.1.1,離散傅里葉變換,(DFT),11.1.2,DFT,的順序代碼,11.1.3,串行,FFT,遞歸算法,11.1.4,串行,FFT,非遞歸算法,串行,FFT,非遞歸算法,蝶式計(jì)算示例,2024/10/12,16,國家高性能計(jì)算中心（合肥）,串行,FFT,非遞歸算法,蝶式計(jì)算流圖,2024/10/12,17,國家高性能計(jì)算中心（合肥）,串行,FFT,非遞歸算法,行,0,行,1,行,2,行,3,行,4,行,5,行,6,行,7,如,:b,6,

7、=(a,0,+a,4,)-(a,2,+a,6,)-(a,1,+a,5,)-(a,3,+a,7,),2,注,:,下行線結(jié)點(diǎn)處的權(quán)因子的確定問題；,b,i,的下標(biāo)確定,:,取行號(hào)的位序反。如，行,3:3=(011),2,=,(110),2,=6,=,行,3,的輸出為,b,6,2024/10/12,18,國家高性能計(jì)算中心（合肥）,第十一章 快速傅里葉變換,11.1,快速傅里葉變換,11.2,并行,FFT,算法,11.2,并行,FFT,算法,11.2.1,SIMD-MC,2,上的,FFT,算法,11.2.2,SIMD-BF,上的,FFT,算法,SIMD-MC,2,上的,FFT,算法,算法描述,n,個(gè)

8、處理器組成,n,1/2,n,1/2,的方陣,處理器以行主序編號(hào),2024/10/12,21,國家高性能計(jì)算中心（合肥）,SIMD-MC,2,上的,FFT,算法,算法,11.3(P270):,輸入,:,a,k,處于,P,k,中,;,輸出,b,k,處于,P,k,中,Begin,(1)for k=0 to n-1 par-do c,k,=,a,k,endfor,(2)for h=logn-1 to 0 do,for k=0 to n-1 par-do,(2.1)p=2,h,(2.2)q=,n/p,(2.3)z=,p,/,先算出,n/2,以后每次,z=z,1/2,(2.4)if(k mod p=k m

9、od 2p)then par-do /,滿足條件的處理器同時(shí)做,(i)c,k,=,c,k,+c,k+p,z,r(k)modq,/(i),和,(ii),同時(shí)執(zhí)行,(,ii)c,k,p,=c,k,-,c,k+p,z,r(k)modq,endif,endfor,endfor,(3)for k=0 to n-1 par-do,b,k,=,c,r(k,),endfor,/,r(k,),為,k,的位序反,End,如：,n=16,h=3,p=8,q=2,z=,8,h=2,p=4,q=4,z=,4,h=1,p=2,q=8,z=,2,h=0,p=1,q=16,z=,1,2024/10/12,22,國家高性能計(jì)算

10、中心（合肥）,SIMD-MC,2,上的,FFT,算法,示例,:,P271,例,11.5,n=4,第,(1),步：,2024/10/12,23,國家高性能計(jì)算中心（合肥）,SIMD-MC,2,上的,FFT,算法,第,(2),步,:,第,1,次迭代,(h=1):p=2,q=2,z=,2,滿足,k mod 2=k mod 4,的處理器為,P,0,和,P,1,同時(shí)計(jì)算,P,0,:c,0,=c,0,+(,2,),0,c,2,=a,0,+a,2,P,1,:c,1,=c,1,+(,2,),0,c,3,=a,1,+a,3,c,2,=c,0,-(,2,),0,c,2,=a,0,-a,2,c,3,=c,1,-(,

11、2,),0,c,3,=a,1,-a,3,2024/10/12,24,國家高性能計(jì)算中心（合肥）,SIMD-MC,2,上的,FFT,算法,第,(2),步,:,第,2,次迭代,(h=0):p=1,q=4,z=,滿足,k mod 1=k mod 2,的處理器為,P,0,和,P,2,同時(shí)計(jì)算,P,0,:c,0,=c,0,+,0,c,1,=(a,0,+a,2,)+(a,1,+a,3,)P,2,:c,1,=c,1,+,1,c,3,=(a,0,+a,2,)+(a,1,+a,3,),c,1,=c,0,-,0,c,1,=(a,0,+a,2,)-(a,1,+a,3,),c,3,=c,1,-,1,c,3,=(a,0

12、,+a,2,)+(a,1,+a,3,),2024/10/12,25,國家高性能計(jì)算中心（合肥）,SIMD-MC,2,上的,FFT,算法,第,(3),步,:b,0,=c,0,b,1,=c,2,b,2,=c,1,b,3,=c,3,算法分析,計(jì)算時(shí)間,:,t,comp,=,O(logn,),選路時(shí)間,:,t,routing,:,只涉及,(2.4),和,(3),(2.4):O(n,1/2,),(3):O(n,1/2,),綜上,當(dāng),n,較大時(shí),t(n,)=O(n,1/2,),2024/10/12,26,國家高性能計(jì)算中心（合肥）,11.2,并行,FFT,算法,11.2.1,SIMD-MC,2,上的,FF

13、T,算法,11.2.2,SIMD-BF,上的,FFT,算法,SIMD-BF,上的,FFT,算法,蝶形網(wǎng)絡(luò),處理器布局,有,k+1,層,每層有,n=2,k,個(gè)處理器,共有,n(1+logn),個(gè)處理器,第,r,行第,i,列的處理器記為,P,r,i,i=(a,1,a,2,a,k,),2,互連方式,P,r,i,與上層,P,r-1,i,P,r-1,j,相連,這里,i,的第,r,位為,0,P,r,j,與上層,P,r-1,i,P,r-1,j,相連,這里,j,與,i,僅在第,r,位不同,權(quán)因子,在,BF,網(wǎng)絡(luò)中的計(jì)算方法,P,r,i,中,的指數(shù)為,j=,exp(r,i,),這里,exp(r,i,)=(,a,

14、r,a,1,0,0)/,即,i,的前,r,位取位序反,再后補(bǔ),0,k-r,2024/10/12,28,國家高性能計(jì)算中心（合肥）,SIMD-BF,上的,FFT,算法,示例,:,n=8,的,BF,網(wǎng)絡(luò)表示,r,i,與上層,P,r-1,i,P,r-1,j,相連,這里,i,的第,r,位為,0,P,r,j,與上層,P,r-1,i,P,r-1,j,相連,這里,j,與,i,僅在第,r,位不同,2024/10/12,29,國家高性能計(jì)算中心（合肥）,SIMD-BF,上的,FFT,算法,算法描述,:P272,算法,11.4,算法分析,算法的正確性可以用歸納法證明,時(shí)間分析,第,(1),步時(shí)間,:O(1),(2

15、.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+logn),c(n,)=O(nlog,2,n),S,p,(n,)=,O(n,),E,p,(n,)=O(1/logn)/,本算法的綜合指標(biāo)是較好的,exp(r,i,),的計(jì)算,初始時(shí),:,P,k,i,讀入,exp(k,i,),，,k=,logn,若,P,r+1,i,已有,exp(r+1,i),則,P,r,i,中的,exp(r,i,),=,2exp(r+1,i),所以,經(jīng)過,logn,步就可以計(jì)算出每個(gè),exp(r,i,),2024/10/12,30,國家高性能計(jì)算中心（合肥）,