计算机科学

首页 > 计算机科学

并行快速傅里叶变换

2018-09-03 09:32:24     所属分类:并发计算

目录

  • 1 串行算法回顾
  • 2 并行算法
  • 3 算法复杂度分析
  • 4 可扩放性分析
  • 5 参阅

串行算法回顾

在快速傅里叶变换(FFT)的并行算法中使用了蝶形连接网络。

并行算法

  • 二维网孔连接网络上的FFT:

将n个处理器排成的二维网孔连接网络,假设输入序列已经存放在了各个处理器中。

下面以16点变换来解释这个问题,连成的网络及编号如下图所示:

根据快速傅里叶变换的算法,我们来研究这16个点计算时四次循环的具体执行情况。

  1. 同一列间隔一行的元素运算。
  2. 同一列间相邻行的元素运算。
  3. 同一行间隔一列的元素运算。
  4. 同一行间相邻列的元素运算。

由上面的算法执行过程,我们发现,数据交换只在同一行或同一列之间的节点间进行。如果我们在第一,二步循环之后对网孔中的数据进行矩阵转置,那么就可以只在同一列节点之间进行运算。

  • 超立方体连接网络上的FFT:

如果我们按超立方体连接的格雷码将待变换点列填入,那么我们发现,数据交换将只在相邻节点间进行。因此数据通信花费恒为O(1)。

算法复杂度分析

可扩放性分析

首先,我们设消息传递并行计算机中通信模型使用的是Store-and-forward而不是cut-through模型。下面令表示通信开销,表示通信开始时间,表示传送一个字的通信时间,表示数据每一跳的延迟,表示第l次循环时的开销,而表示进行一个单位运算的时间。p为处理器数,d=log(p),n为待变换的序列大小。 那么我们有公式:

有这个公式,我们可以得出:

  1. 在二维网孔上的等效率标准函数为:
  2. 在超立方体上的等效率标准函数为:
  • 参考文献:The Scability of FFT on Parallel Computers, Anshul Gupta and Vipim Kummar。

参阅

  • 并行计算
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/340410.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


上一篇:AVX指令集
相关推荐