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

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

N 2 的方向进行分块,每个任务块大小为 V*N 1 ,任务块个数为 TN=N 2 /V=4,分别为 T0、T1、T2 和 T3,每个任务块
由一行/列从核完成.将 N 1 分解为 N 1 =f 1 ×f 2 ,首先计算 f 1 点一维 FFT,对每个任务块从 f 2 的方向进行划分得到 4 个
小任务块,并将每个小任务块分配给一个从核;然后计算 f 2 点一维 FFT,其任务划分方式与计算 f 1 点 FFT 过程类
似,但其任务划分沿 f 1 方向.从核中 f 1 和 f 2 的计算直接调用 Codelets FFT 来完成.

Fig.4 The diagram of two-layer decomposition 1-D FFT multi-core parallel algorithm (N 1 =f 1 ×f 2 )
图 4 基于两层分解的一维 FFT 众核并行算法图(N 1 =f 1 ×f 2 )
图 5 中,N 2 ≤M,N 2 =f 1 ×f 2 ,其中,f 1 的取值一般与一行/列从核的个数相同,红框部分表示一行/列从核的计算任
务.首先计算 f 1 点一维 FFT,将计算任务沿 N 1 的方向进行分块,其任务的个数为 TN=16,任务大小为 V*N 2 .每个任
务按行优先方式读取数据到单个从核 LDM 中;然后计算 f 2 点一维 FFT,因计算结果需转置后存回,计算前需要对
数据进行重排和转置,以达到 DMA 数据传输中 f 1 *V 的连续度.

Fig.5 The diagram of two-layer decomposition 1-D FFT multi-core parallel algorithm (N 2 =f 1 ×f 2 )
图 5 基于两层分解的一维 FFT 众核并行算法图(N 2 =f 1 ×f 2 )
4.2 规模决策

对于规模为 N 的一维 FFT,按照基于两层分解的一维 FFT 众核并行算法原理,其存在多种分解策略,但是并
非所有的分解策略都能得到较好的计算性能.本文算法虽然具有很好的并行度,但其带来的是访存量的大幅增
加.对于分解 N = N × 1 N × 2 ... N× m (m≥ 2), 当总数据规模大于 LDM 空间时,至少需要对主存数组读写 m 次,其访
存量为 2mN.对于第 2 层分解 N = r f × 1 f 2 [ f× 3 ](1≤≤ m ), 因递归地应用 Cooley-Tukey FFT,每一个分解又至少增
r
加 2N 访存量,因此在数据规模允许的情况下,m 的取值应尽量小,第 2 层分解类似.
对于分解规模的选取,本算法采用 down-up 型两层策略树的方式进行选取,其特点是首先考虑第 2 层分解
中 N r (1≤ r≤ m)的分解(down 方向),然后再考虑第 1 层中 N 的分解(up 方向).算法中 N r 的取值一般为 64、128、
256、512 和 1024 等,目前可通过分析和实验的方式确定性能最优的 N r 分解结果.已知第 2 层的分解结果后,根