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

赵玉文 等:申威 26010 众核处理器上一维 FFT 实现与优化 3189

遍历 1 遍,3 次遍历数组中数据维度的变化过程为
⎯
⎯
⎯
N × N × N ⎯ N 点 ⎯ 1 FFT ⎯ → N × N × N ⎯ ⎯ N 点 2 FFT ⎯ → N × N × N ⎯ ⎯ N 点 3 FFT ⎯ → N × N × N .
1 2 3 1 2 3 2 1 3 3 2 1
4 基于两层分解的一维 FFT 众核并行算法的设计与实现
FFT 算法具有计算密集型和访存密集型的特点,其并行度有限、访存局部性低,在 26010 众核平台上很难充
分利用众多的计算资源.依据计算平台的结构特性和存储层次特点,本文提出了基于两层分解的一维 FFT 众核
并行算法.该算法基于迭代的 Stockham FFT 计算框架,将大规模 FFT 分解成一系列的小规模 FFT 来计算,分解
规则基于 Cooley-Tukey FFT 算法.通过设计合理的任务划分方案、数据重用机制和计算与访存重叠的双缓冲优
化来有效地解决并行度和访存量等问题.本文主要致力于双精度复数到复数的 2 的幂次一维 FFT 计算,其他情
况不作为本文研究的重点.
4.1 并行方案设计和任务划分
n
基于两层分解的一维 FFT 众核并行算法首先利用 Cooley-Tukey FFT 算法对输入数据规模为 N(N=2 ,n≥
9)的一维 FFT 进行第 1 层分解, N = N × 1 ... N× r × ... N× m (1≤≤ m ), 即将原 N 点的一维 FFT 转化成 m 个相互独
r
立的计算步骤,输入数据按行优先自然地映射成 m 维矩阵的形式,其中,第 N m 维度的数据连续存储,其他维度非
连续存储.所有的分解因子 N r (1≤r≤m)满足其规模的相应数据可以完全加载到从核整个核组的 LDM 中.如果
N r 的规模足够小,则不对 N r 进行第 2 次分解,直接计算 N r 点 FFT;如果 N r 的规模较大,从高效的 LDM 空间利用、
DMA 传输方式和负载均衡 3 个方面考虑,一般需要多个从核共同完成 N r 点一维 FFT 计算,此时利用 Cooley-
Tukey FFT 算法递归地对 N r 进行第 2 层分解 N r =f 1 ×f 2 [×f 3 ](f 3 可选),将数据平均分布到 8 个或者 64 个从核上.算
法中,不进行第 2 层分解的 N r 点和 f k (k=1,2,3)点一维 FFT 直接调用底层高效的计算小因子 FFT 的 Codelets 库
完成.Codelets FFT 直接使用平台特有的向量化指令编写,并进行循环展开、仔细规划寄存器资源和指令流水等
优化,使代码更高效且具有更少的浮点运算量.另外,算法利用 Stockham FFT 计算框架的自动排序功能来优化
Cooley-Tukey FFT 算法中将结果转置存回的问题.
对于算法中 m 个相互独立的计算步骤,每一步都需要利用 DMA 将相应数据传输到核组 LDM 中,并在核组
内完成 N r (1≤r≤m)点一维 FFT 的计算.根据数据存储是否连续,可将 m 个计算步骤分成两类.
(1) 数据非连续存储 N r (1≤r≤m),其分解可简写成 P×N r ×T(1<r<m),P 为已经完成 FFT 计算的部分(对于第
N 1 维度,P=1),T 为未计算的部分,此时将计算任务沿 T 的方向进行分块,每个任务块的大小为 V*N r ,任务块个数
为(P*T)/V,其可以满足 DMA 传输数据的连续度要求,从而使 DMA 传输更高效.但是由于单个从核的 LDM 空间
有限,能够独立处理的任务块一般较小,需要利用多个从核协作以完成一个任务块,此时需要对 N r 进行第 2 层分
解 N r =f 1 ×f 2 [×f 3 ].如果 N r 分解成 N r =f 1 ×f 2 ,则每个任务块由一行/列从核完成;如果 N r 分解成 N r =f 1 ×f 2 ×f 3 ,则每个任
务块由整个核组共同完成.
(2) 数据连续存储 N m (r=m),分解可以简写成 P×N m ,计算任务沿 P 的方向进行分块.当 N m ≤M(M 为每个从核
所能计算的最大数据量)时,按行优先方式读取数据,将 N m 点一维 FFT 计算所需的数据可以直接加载到一个从
核的 LDM 上,每个从核的计算量为 V=M/N m 个 N m 点 FFT.但当 V 较小时,由于结果需要以转置的形式存回到不
连续的主存中,单个从核直接存回只能保证 V 个数的连续度,为了满足高效的 DMA 传输对传输数据的连续度要
求,可以通过对一行/列中的 8 个从核的数据进行重排和转置,从而保证存回的数据块有 8*V 的连续度,此时需要
将 N m 进一步分解成 N m =f 1 ×f 2 ,由一行/列从核共同完成.但当 N m >M 时,单个从核不能容纳 N m 规模的数据,需要多
个从核协作完成计算任务.一般由一行/列从核完成 V=(8*M)/N m 个 N m 点一维 FFT 计算,此时需要将 N m 进一步
分解成 N m =f 1 ×f 2 ×f 3 ,其计算方式与 N m ≤M 类似.对于以上两种情况中的数据重排操作一般借助寄存器通信机制
完成,以进一步减少访存量.
下面以 4×4 的从核阵列来展示 N=N 1 ×N 2 的任务划分方式,其中图 4 展示第 N 1 维度,图 5 展示第 N 2 维度,图
中×表示分解操作,*表示任务划分中的乘法操作,Z 方向表示数据连续存储,Y 和 X 分别次之.图 4 中,计算任务沿