并行计算,第一级,第二级,第三级,第一级,第二级,第三级,国家高性能计算中心（合肥）,*,*,并 行 计 算,中国科学技术大学计算机科学与技术系,国家高性能计算中心,(,合肥,),2004,年,12,月,第三篇 并行数值算法,第八章 基本通讯操作,第九章 稠密矩阵运算,第十章 线性方程组的求解,第十一章,快速傅里叶变换,第十一章 快速傅里叶变换,11.1,快速傅里叶变换,11.2,并行,FFT,算法,11.1,快速傅里叶变换,(FFT),11.1.1,离散傅里叶变换,(DFT),11.1.2,DFT,的顺序代码,11.1.3,串行,FFT,递归算法,11.1.4,串行,FFT,非递归算法,离散傅里叶变换,(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,国家高性能计算中心（合肥）,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,需要计算,k,*j,代码,2,的复杂度为,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,国家高性能计算中心（合肥）,11.1,快速傅里叶变换,(FFT),11.1.1,离散傅里叶变换,(DFT),11.1.2,DFT,的顺序代码,11.1.3,串行,FFT,递归算法,11.1.4,串行,FFT,非递归算法,串行,FFT,递归算法,蝶式递归计算原理,令 为,n/2,次单位元根，则有,.,将,b,向量的偶数项 和奇数项 分别记为,和,注意推导中反复使用,2024/10/12,9,国家高性能计算中心（合肥）,串行,FFT,递归算法,2024/10/12,10,国家高性能计算中心（合肥）,串行,FFT,递归算法,2024/10/12,11,国家高性能计算中心（合肥）,串行,FFT,递归算法,FFT,的蝶式递归计算图,(,由计算原理推出,),2024/10/12,12,国家高性能计算中心（合肥）,串行,FFT,递归算法,特别地，,n=8,的,FFT,蝶式计算图,(,展开的,),2024/10/12,13,国家高性能计算中心（合肥）,串行,FFT,递归算法,SISD,上的,FFT,分治递归算法,输入,:a=(a,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),算法时间复杂度,t(n,)=2t(n/2)+O(n),endif,解得,t(n,)=,O(nlogn,),end,(2),算法原理？,2024/10/12,14,国家高性能计算中心（合肥）,11.1,快速傅里叶变换,(FFT),11.1.1,离散傅里叶变换,(DFT),11.1.2,DFT,的顺序代码,11.1.3,串行,FFT,递归算法,11.1.4,串行,FFT,非递归算法,串行,FFT,非递归算法,蝶式计算示例,2024/10/12,16,国家高性能计算中心（合肥）,串行,FFT,非递归算法,蝶式计算流图,2024/10/12,17,国家高性能计算中心（合肥）,串行,FFT,非递归算法,行,0,行,1,行,2,行,3,行,4,行,5,行,6,行,7,如,:b,6,=(a,0,+a,4,)-(a,2,+a,6,)-(a,1,+a,5,)-(a,3,+a,7,),2,注,:,下行线结点处的权因子的确定问题；,b,i,的下标确定,:,取行号的位序反。
如，行,3:3=(011),2,=,(110),2,=6,=,行,3,的输出为,b,6,2024/10/12,18,国家高性能计算中心（合肥）,第十一章 快速傅里叶变换,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,个处理器组成,n,1/2,n,1/2,的方阵,处理器以行主序编号,2024/10/12,21,国家高性能计算中心（合肥）,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 mod 2p)then par-do /,满足条件的处理器同时做,(i)c,k,=,c,k,+c,k+p,z,r(k)modq,/(i),和,(ii),同时执行,(,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,国家高性能计算中心（合肥）,SIMD-MC,2,上的,FFT,算法,示例,:,P271,例,11.5,n=4,第,(1),步：,2024/10/12,23,国家高性能计算中心（合肥）,SIMD-MC,2,上的,FFT,算法,第,(2),步,:,第,1,次迭代,(h=1):p=2,q=2,z=,2,满足,k mod 2=k mod 4,的处理器为,P,0,和,P,1,同时计算,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,-(,2,),0,c,3,=a,1,-a,3,2024/10/12,24,国家高性能计算中心（合肥）,SIMD-MC,2,上的,FFT,算法,第,(2),步,:,第,2,次迭代,(h=0):p=1,q=4,z=,满足,k mod 1=k mod 2,的处理器为,P,0,和,P,2,同时计算,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,+a,2,)+(a,1,+a,3,),2024/10/12,25,国家高性能计算中心（合肥）,SIMD-MC,2,上的,FFT,算法,第,(3),步,:b,0,=c,0,b,1,=c,2,b,2,=c,1,b,3,=c,3,算法分析,计算时间,:,t,comp,=,O(logn,),选路时间,:,t,routing,:,只涉及,(2.4),和,(3),(2.4):O(n,1/2,),(3):O(n,1/2,),综上,当,n,较大时,t(n,)=O(n,1/2,),2024/10/12,26,国家高性能计算中心（合肥）,11.2,并行,FFT,算法,11.2.1,SIMD-MC,2,上的,FFT,算法,11.2.2,SIMD-BF,上的,FFT,算法,SIMD-BF,上的,FFT,算法,蝶形网络,处理器布局,有,k+1,层,每层有,n=2,k,个处理器,共有,n(1+logn),个处理器,第,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,位不同,权因子,在,BF,网络中的计算方法,P,r,i,中,的指数为,j=,exp(r,i,),这里,exp(r,i,)=(,a,r,a,1,0,0)/,即,i,的前,r,位取位序反,再后补,0,k-r,2024/10/12,28,国家高性能计算中心（合肥）,SIMD-BF,上的,FFT,算法,示例,:,n=8,的,BF,网络表示,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,国家高性能计算中心（合肥）,SIMD-BF,上的,FFT,算法,算法描述,:P272,算法,11.4,算法分析,算法的正确性可以用归纳法证明,时间分析,第,(1),步时间,:O(1),(2.1),和,(2.2),的计算时间为,O(1),(,假定,exp(r,i,),已计算好,),(2.1),和,(2.2),的选路时间为,O(1)=,第,(2),步时间,:,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)/,本算法的综合指标是较好的,exp(r,i,),的计算,初始时,:,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),所以,经过,logn,步就可以计算出每个,exp(r,i,),2024/10/12,30,国家高性能计算中心（合肥）,。