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

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

总体来说,本文算法获得了较好的性能,相比 FFTW 获得了平均 44.53x 的加速比,最高加速比可达 56.33x,
最低加速比可达 24.67x.另外,Basic 版获得了平均 13.76x 的加速比,Basic+Register 版获得了平均 24.94x 的加速
比,Basic+Register+Simd 版获得了平均 33.52 的加速比.

5.2 访存带宽
因本文算法在申威 26010 异构众核处理器上的访存时间和计算时间(计算已采用向量化等技术充分优化)
相当,访存时间略长,故采用带宽利用率作为评价指标.本节测试了基于两层分解的一维 FFT 众核并行算法的访
存带宽情况.假设对于双精度复数的一维 FFT 计算,DMA 传输的数据量为 td×N+tw(单位:双精度复数),其中,N 为
一维 FFT 的数据规模,td 为整个计算过程中需要对主存中数据遍历的次数,tw 表示旋转因子的传输量.td 和 tw
的结果均与本文算法中的分解结果有关,若有分解 N = N × 1 ... N× m , 则有
⎧ 2, m < 2
td = ⎨ , tw = N (6)
⎩ 2, mm≥ 2
对于第 2 层分解, N = r f × 1 f 2 [ f× 3 ](1≤≤ m ),tw = max{N N 2 ,..., N m }. 图 10 给出了各数据规模的访存带宽以
r
,
1
及与带宽利用率(总带宽按照实测带宽 27.5Gb/s 计算),最高可达 83.45%,最低为 48.41%,平均带宽利用率为
68.78%.

Fig.10 The memory bandwidth of two-layer decomposition 1-D FFT multi-core parallel algorithm
图 10 基于两层分解的一维 FFT 众核并行算法的访存带宽
5.3 性能分析

2
FFT 算法将 DFT 计算的时间复杂度由 O(N )降到了 O(N log 2 N),FFT 性能通常由如下公式计算获得:
510× − 9 × N × log N
Gflops = 2 (7)
runtime
其中,N 为一维 FFT 变换的规模;runtime 为计算花费的时间,以秒(s)为单位.在申威 26010 众核上,从核计算可以
与 DMA 传输异步进行.一般来说,运行时间由计算时间和 DMA 传输时间构成,但是,由于 FFT 是一种典型的带
宽密集型算法,好的算法设计方案可以将从核计算与 DMA 传输重叠起来,从而隐藏从核计算的开销.因而,我们
可以根据申威 26010 众核的 DMA 传输带宽参数来估计实现能达到的性能上限.
由第 5.2 节可知,DMA 传输的数据量为 td×N+tw,由于所需加载的旋转因子数组的规模与变换规模 N 以及
其分解方案存在很大的关系,因此只考虑第 1 层分解中的旋转因子传输部分,即取 td=N.
理想情况下,双精度复数到复数 FFT 的性能上限可由如下公式来计算:
510× − 9 × N × log N
Gflops = 2 (8)
×
9
(td × N + tw × ) 16/(27.5 10 )
理想