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

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

背景（1）串行算法

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

（2）并行算法

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

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

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

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

下面以16点变换来解释这个问题：

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

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

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

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

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

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

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

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

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

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

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

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

本词条内容贡献者为:

李宗秀 - 副教授 - 黑龙江财经学院