查看“︁并行快速傅里叶变换”︁的源代码

{{NoteTA|G1=Math|G2=IT|1=zh:傅里叶; zh-hans:傅里叶; zh-hant:傅立葉;|2=zh-hans:并行;zh-hant:平行;}}
==串行算法回顾==
在[[快速傅里叶变换]]（FFT）的并行算法中使用了[[蝶形连接]]网络。
==并行算法==
*二维[[网孔连接]]网络上的FFT：
将n个处理器排成<math>\sqrt {n}\times\sqrt {n}</math>的二维[[网孔连接]]网络，假设输入序列<math>\{a_0,a_1,......,a_{n-1}\}</math>已经存放在了各个处理器中。

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

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

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

由上面的算法执行过程，我们发现，数据交换-{只}-在同一行或同一列之间的节点间进行。如果我们在第一，二步循环之后对网孔中的数据进行[[矩阵]]转置，那么就可以只在同一列节点之间进行运算。
*[[超立方体连接]]网络上的FFT：
如果我们按[[超立方体连接]]的[[格雷码]]将待变换点列填入，那么我们发现，数据交换将只在相邻节点间进行。因此数据通信花費恒为O(1)。

==算法复杂度分析==
==可扩放性分析==
{{see also|计算机网络}}
首先，我们设[[消息传递]]并行计算机中通信模型使用的是[[Store-and-forward]]而不是[[cut-through]]模型。下面令<math>T_o</math>表示通信开销，<math>T_s</math>表示通信开始时间，<math>T_w</math>表示传送一个[[字]]的通信时间，<math>T_h</math>表示数据每一跳的延迟，<math>z_l</math>表示第l次循环时的开销，而<math>t_c</math>表示进行一个单位运算的时间。p为处理器数，d=log(p)，n为待变换的序列大小。
那么我们有公式：

<math>T_o = \sum _{l=0}^{d-1}(T_s+(T_h + T_w\frac{n}{p})z_l)</math>

有这个公式，我们可以得出：
#在二维网孔上的[[等效率标准]]函数为：<math>W = 2Kt_w\sqrt {p}\times 2^{2K\frac{t_w}{t_c}\sqrt{p}}</math>
#在超立方体上的[[等效率标准]]函数为：<math>W = Kt_w\times p^{K\frac{t_w}{t_c}}\times \log p</math>；

* 参考文献：The Scability of FFT on Parallel Computers, Anshul Gupta and Vipim Kummar。

==参阅==
*[[并行计算]]

[[Category:并发计算|B]]
[[Category:傅里叶变换|B]]