[科普中国]-并行快速傅里叶变换

并行快速傅里叶变换不同于平常的FFT算法，其更便于组织向量运算，效率高且性能好。

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

并行算法并行计算（英语：parallel computing）一般是指许多指令得以同时进行的计算模式。在同时进行的前提下，可以将计算的过程分解成小部分，之后以并发方式来加以解决。1

电脑软件可以被分成数个运算步骤来运行。为了解决某个特定问题，软件采用某个算法，以一连串指令运行来完成。传统上，这些指令都被送至单一的中央处理器，以循序方式运行完成。在这种处理方式下，单一时间中，只有单一指令被运行(processor level: 比较微处理器，CISC, 和RISC，即流水线Pipeline的概念，以及后来在Pipeline基础上以提高指令处理效率为目的的硬件及软件发展，比如branch-prediction, 比如forwarding，比如在每个运算单元前的指令堆栈，汇编程序员对programm code的顺序改写)。并行运算采用了多个运算单元，同时运行，以解决问题。

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

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

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

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

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

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

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

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

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

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

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

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

有这个公式，我们可以得出：

在二维网孔上的等效率标准函数为：

在超立方体上的等效率标准函数为：

参阅并行计算

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学