并行快速傅里叶变换
并行快速傅里叶变换
串行算法回顾.
在快速傅里叶变换（FFT）的并行算法中使用了蝶形连接网络。
并行算法.
将n个处理器排成formula_1的二维网孔连接网络，假设输入序列formula_2已经存放在了各个处理器中。
下面以16点变换来解释这个问题，连成的网络及编号如下图所示：
根据快速傅里叶变换的算法，我们来研究这16个点计算时四次循环的具体执行情况。
由上面的算法执行过程，我们发现，数据交换-{只在同一行或同一列之间的节点间进行。如果我们在第一，二步循环之后对网孔中的数据进行矩阵转置，那么就可以只在同一列节点之间进行运算。
如果我们按超立方体连接的格雷码将待变换点列填入，那么我们发现，数据交换将只在相邻节点间进行。因此数据通信花费恒为O(1)。
可扩放性分析.
首先，我们设消息传递并行计算机中通信模型使用的是Store-and-forward而不是cut-through模型。下面令formula_3表示通信开销，formula_4表示通信开始时间，formula_5表示传送一个字的通信时间，formula_6表示数据每一跳的延迟，formula_7表示第l次循环时的开销，而formula_8表示进行一个单位运算的时间。p为处理器数，d=log(p)，n为待变换的序列大小。
那么我们有公式：
formula_9
有这个公式，我们可以得出：
本站由爱斯园团队开发维护，感谢那些提出宝贵意见和打赏的网友，没有你们的支持，网站不可能发展到今天，
继往开来，善终如始，我们将继续砥砺前行。
Copyright ©2014 iissy.com, All Rights Reserved.