Page 212 - 《软件学报》2020年第10期

3188 Journal of Software 软件学报 Vol.31, No.10, October 2020

计算或者 N 2 点 FFT 计算中,使访存量减少到 4N.而 N 1 点和 N 2 点一维 FFT 的计算通常递归地应用 Cooley-Tukey
FFT 继续分解,直到规模足够小可以直接计算为止.

Fig.2 Flowchart of the Cooley-Tukey FFT algorithm
图 2 Cooley-Tukey FFT 算法流程图

对于 Cooley-tukey FFT 算法中最后一步的转置存回操作(对应于基-2 Cooley-Tukey FFT 算法中的位倒序
bit-reversal),其涉及到对输入数据的全局转置过程,虽然这个操作只需要 O(n)时间,但仍然不可忽略,特别是对于
变换规模较大的情况.我们利用 Stockham FFT 框架进行优化,避免了转置操作.
Stockham FFT 计算框架.基于分解 N = N ×× r ... N m (1≤≤ m ) 使用迭代的方法将规模为 N 的一维
... N ××
r
1
FFT 转化成一系列规模为 N r 的一维 FFT 计算.其算法流程如图 3 所示.
Stockham FFT 计算框架.
1: for r = → m step 1 do
1

2: P = 1 N × N × 2 ... N − 1 //当 r=1 时,P=1
×
r

3: T = r N + 1 N + × r 2 ... N× × m //当 r=m 时,T=1
4: S = N / N
r
5: for s = → 0 P − 1 step 1 do
0
6: for t =→ T − 1 step 1 do
7: for k = → 0 r N − 1 step 1 do
N r − 1
(
8: ys T⋅+ k S⋅ )( = ∑ x ( ) t + (s ⋅ ) t + j T ω⋅ ) r N T ⋅+ ⋅ jk //N r 点 FFT
N r
j= 0
9: end for
10: end for
11: end for
12: end for
Fig.3 The flow chart of Stockham FFT algorithm
图 3 Stockham FFT 算法流程图
其通过在每步分解计算中穿插多维转置,避免了一个显式的全局转置的过程.具体地,N r 点一维 FFT 计算前
后,数据在主存中的组织和维度为
... N ⎯⎯⎯⎯→
... N ×
N ×× N × N ×× N r点 FFT N × N × ... N× × N × ... N× .
r− 1 1 r r+ 1 m r r− 1 1 r+ 1 m
P T P T
其中,N r 表示当前需要计算的 FFT 规模,P 表示已经完成的 FFT 计算部分,T 表示未计算的部分.举例来说,
若 N 可以分解为 3 个因子的乘积,即 N=N 1 ×N 2 ×N 3 ,在计算每个 N i (1≤i≤3)点一维 FFT 时,需要对整个数据读写