并行快速傅里叶变换

维基百科，自由的百科全书

[编辑] 串行算法回顾

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

[编辑] 并行算法

二维网孔连接网络上的FFT：

将n个处理器排成 $\sqrt {n}\times\sqrt {n}$ 的二维网孔连接网络，假设输入序列 ${a 0, a 1,......, a n - 1}$ 已经存放在了各个处理器中。

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

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

同一列间隔一行的元素运算。
同一列间相邻行的元素运算。
同一行间隔一列的元素运算。
同一行间相邻列的元素运算。

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

超立方体连接网络上的FFT：

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

[编辑] 算法复杂度分析

[编辑] 可扩放性分析

首先，我们设消息传递并行计算机中通信模型使用的是Store-and-forward而不是cut-through模型（关于这两个模型的具体论述，请参见计算机网络）。下面令 $T o$ 表示通信开销， $T s$ 表示通信开使时间， $T w$ 表示传送一个字的通信时间， $T h$ 表示数据每一跳的延迟， $z l$ 表示第l次循环时的开销，而 $t c$ 表示进行一个单位运算的时间。p为处理器数，d=log(p)，n为待变换的序列大小。那么我们有公式：