MPI程序设计ch14.ppt

《MPI程序设计ch14.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ParallelAlgorithmsChapter14FastFourierTransform2021/7/17Y.XuCopyrightUSTC主要内容14.1快速傅里叶变换(FFT)-离散傅里叶变换(DFT)-DFT的顺序代码-串行FFT递归算法-串行FFT非递归算法14.2DFT直接并行算法-SIMD-MT上的并行DFT算法14.3并行FFT算法-SIMD-MC2上的FFT算法-SIMD-BF上的FFT算法2021/7/17Y.XuCopyrightUSTC14.1快速傅里叶变换(FFT)1.离散傅里叶变换(DFT)-DFT定义给定向量A=(a0,a1,…,an-1)T,DFT将A变换

2、为B=(b0,b1,…,bn-1)T2021/7/17Y.XuCopyrightUSTC14.1快速傅里叶变换(FFT)2.DFT的顺序代码:直接计算DFT需要O(n2)时间(代码2)代码1forj=0ton-1dob[j]=0fork=0ton-1dob[j]=b[j]+ωk*ja[k]endforendfor代码2w=ω0forj=0ton-1dob[j]=0,s=ω0fork=0ton-1dob[j]=b[j]+s*a[k]s=s*wendforw=w*ωendfor2021/7/17Y.XuCopyrightUSTC14.1快速傅里叶变换(FFT)2021/7/17Y.XuCopyr

3、ightUSTC14.1快速傅里叶变换(FFT)2021/7/17Y.XuCopyrightUSTC14.1快速傅里叶变换(FFT)2021/7/17Y.XuCopyrightUSTC14.1快速傅里叶变换(FFT)(2)FFT的蝶式递归计算图(由蝶式递归计算原理推出)2021/7/17Y.XuCopyrightUSTC14.1快速傅里叶变换(FFT)特别地，n=8的FFT蝶式计算图(展开的)2021/7/17Y.XuCopyrightUSTC14.1快速傅里叶变换(FFT)(3)SISD上的FFT分治递归算法输入:A=(a0,a1,…,an-1);输出:B=(b0,b1,…,bn-1)Pr

4、ocedureRFFT(a,b)beginifn=1thenb0=a0else(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)forj=0ton-1do(4.1)bj=ujmodn/2+zvjmodn/2(4.2)z=zωendfor注:(1)算法时间复杂度t(n)=2t(n/2)+O(n)endif解得t(n)=O(nlogn)end(2)算法原理？2021/7/17Y.XuCopyrightUSTC14.1快速傅里叶变换(FFT)4.串行FFT非递归算法(1)蝶式计算示例20

5、21/7/17Y.XuCopyrightUSTC14.1快速傅里叶变换(FFT)(2)蝶式计算流图2021/7/17Y.XuCopyrightUSTC行0行1行2行3行4行5行6行7如:b6=[(a0+a4)-(a2+a6)]-[(a1+a5)-(a3+a7)]ω2注:①下行线结点处的权因子的确定问题；②bi的下标确定:取行号的位序反。如，行3:3=(011)2==>(110)2=6,==>行3的输出为b614.1快速傅里叶变换(FFT)2021/7/17Y.XuCopyrightUSTC14.1快速傅里叶变换(FFT)(3)非递归串行FFT算法(算法14.1)begin//输入(a0,a1

6、,…,an-1),输出(b0,b1,…,bn-1)(1)fork=0ton-1ckakendfor//O(n)(2)forh=logn-1downto0do//迭代logn次(2.1)p2h(2.2)qn/p(2.3)zωq/2//(2.3)递归计算,O(logn)(2.4)fork=0ton-1do//O(n)ifkmodp=kmod2pthen//k=0,1,…,p-1(i)tck+ck+p(ii)ck+p(ck-ck+p)zkmodp如:n=8(iii)ckth=2,p=4,q=2,z=ωendifh=1,p=2,q=4,z=ω2endforh=0,p=1,q=8,z=ω

7、4endfor(3)fork=1ton-1dobr(k)ckendfor//r(k)为k的位序反end计算时间t(n)=O(nlogn)2021/7/17Y.XuCopyrightUSTC主要内容14.1快速傅里叶变换(FFT)-离散傅里叶变换(DFT)-DFT的顺序代码-串行FFT递归算法-串行FFT非递归算法14.2DFT直接并行算法-SIMD-MT上的并行DFT算法14.3并行FFT算法-SIMD-M