按位交换的并行FFT.ppt

《按位交换的并行FFT.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、按位交换的并行FFT超立方体上的按位交换并行FFT二维网格上的按位交换并行FFT并行FFT中的额外计算2021/9/151超立方体上的按位交换并行FFT设要在p=2d个进程上并行计算n=2r个点的FFT，将这n个点平均分为p段，使得每段含有连续的n/p个点对0~n-1中的任何一个点l，记其二进制形式为(b0b1…br-1)，则将CT_FFT中的Rl与Sl分配到进程(b0b1…bd-1)上只有前d=logp次外迭代需要进行通信，而后r-d次外迭代无需任何通信2021/9/152超立方体上的按位交换并行F

2、FT(续)2021/9/153超立方体上的按位交换并行FFT(续)并行执行时间为当p固定不变，而n不断增大时，并行效率必然趋于1等效率函数，记k＝Ep/(1-Ep)，则当kb/c小于1时为W=(plogp)当kb/c大于1时为W=(pkb/clogp)2021/9/154二维网格上的按位交换并行FFT设n=2r，p=2d，r与d都是偶数，且处理器组织成物理上的2d/2×2d/2二维网格对任意一个l＝0~n-1，如果其二进制形式为(b0b1…br-1)，则将其分布到第(b0b1…bd/2-1,bd/

3、2bd/2+1…bd-1)个进程一次消息传递可能需要经过网格中多条物理链路；同一时候不同进程对之间的消息传递可能需要经过同一物理链路2021/9/155二维网格上的按位交换并行FFT(续)24252627161718198910110123456712131415202122232829303132333435363738394041424344454647484950515253545556575859606162632021/9/156二维网格上的按位交换并行FFT(续)第m

4、，通信只出现在同行进程间，通信所需要的时间为s+b(n/p)2logp/2-1-m之后的logp/2次外迭代的总通信时间与前logp/2次外迭代的总通信时间相同并行执行时间为Tp=cnlogn/p+slogp+2b(n/p)(p1/2–1)对应于通信起步时间s的等效率函数为W=(plogp)对应于数据传输b的等效率函数为2021/9/157并行FFT中的额外计算在串行FFT中，旋转因子一共只有n个，其计算复杂性为O(n)，对总计算复杂性影响不大由于计算一个旋转因子的时间远小于传输一个旋转因子的时间，

5、所以对有的旋转因子，可能需要在不同的进程上分别进行计算，引入了额外计算8点FFT的例子2021/9/158并行FFT中的额外计算(续)设n=2r，p=2d，对任何一个点(b0b1…br-1)，在数据分布时，将分布到进程(b0b1…bd-1)上从CT_FFT知，在第m次外迭代，点(b0b1…br-1)的值更新只需要用到幂次为(bmbm-1…b00…0)的旋转因子当m=0,…,d-1时，第m次外迭代上每个进程只用到一个旋转因子对m=d,…,r-1时，第m次外迭代上每个进程需要用到2m-d+1个旋转因子20

6、21/9/159并行FFT中的额外计算(续)每个进程最多需要用到一共logp+21+…+2r-d即2(n/p-1)+logp个旋转因子假设每个旋转因子的计算时间为c’，则在超立方体上的并行执行时间应该修改为等效率函数在量阶上并没有变化2021/9/1510