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

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

表 2 根据上述设计方案,对典型一维双精度复数到复数 2 的幂次 FFT 的性能上限进行了估计.

Table 2 Comparison of ideal performance with actual performance at various scales
表 2 各规模理想性能与实际性能对比
Gflops
td 计算公式 N Gflops 理想 Gflops 实际 实际 (%)
Gflops 理想
65 536 27.5 18.0 65.5
131 072 29.2 22.2 76.0
×
55 log 2 N 262 144 30.9 25.0 80.9
4 Gflops = 524 288 32.7 25.8 78.9
理想
32
1 048 576 34.4 27.7 80.5
2 097 192 36.1 28.0 77.6
4 194 304 37.8 27.8 73.5
×
275 log 2 N
6 Gflops = 8 388 608 28.2 26.9 95.4
224
理想

从表 2 可知,本文算法获得了较好的性能,相比理想的 Gflops 性能,其实际性能占比平均为 78.5%,最高占比
可达 95.4%,最低占比为 65.5%.
6 总结和下一步工作
FFT 算法具有计算密集型和访存密集型的特点,其并行度有限、访存局部性低,在申威 26010 众核处理器上
很难充分利用众多的计算和访存资源.本文首先对 DFT、Cooley-Tukey FFT 算法和 Stockham FFT 计算框架以
及申威 26010 众核处理器等进行了较为详尽的介绍.然后根据申威 26010 众核处理器的结构特点和存储层次特
点,提出了基于两层分解的一维 FFT 众核并行算法.该算法采用迭代的 Stockham FFT 计算框架,将大规模 FFT
分解成一系列的小规模 FFT 来计算,而分解规则基于 Cooley-Tukey FFT 算法.该算法利用寄存器通信、访存计
算重叠以及 SIMD 向量化等优化手段来有效地提高整体性能.最后对本文算法的性能和带宽进行了测试并对其
性能进行了剖析,其性能相比于单主核上运行的 FFTW3.3.4 库,获得了平均 44.53x 的加速比,最高加速比可达
56.33x,且其带宽利用率最高可达 83.45%.本文虽然以申威 26010 平台来开展研究,但本文提出的算法对其他异
构众核系统架构,如 GPU 也具有很大的借鉴意义.
下一步工作可以从以下两方面展开:一方面,可以对本文的工作进行扩展,功能上实现支持非 2 的幂次一维
FFT 计算以及任意规模的多维 FFT;另一方面,将本文提出的算法移植到其他计算平台.

References:
[1] Cipra BA. The best of the 20th century: Editors name top 10 algorithms. SIAM News, 2000,33(4):1–2.
[2] Luszczek P, Dongarra JJ, Koester D, et al. Introduction to the HPC challenge benchmark suite. Office of Scientific & Technical
Information Technical Reports, 2005.
[3] Fu H, Liao J, Yang J, et al. The Sunway TaihuLight supercomputer: System and applications. Science China Information Sciences,
2016,59(7):072001.
[4] Frigo M, Johnson SG. The design and implementation of FFTW3. Proc. of the IEEE, 2005,93(2):216–231.
[5] Frigo M, Johnson SG. FFTW: An adaptive software architecture for the FFT. In: Proc. of the IEEE Int’l Conf. on Acoustics, Speech
and Signal Processing. 2002. 1381–1384.
[6] Ali A, Johnsson L, Subhlok J. Scheduling FFT computation on SMP and multicore systems. In: Proc. of the Int’l Conf. on
Supercomputing, ICS 2007. Seattle: DBLP, 2007. 293–301.
[7] Puschel M, Moura JMF, Johnson JR, et al. SPIRAL: Code generation for DSP transforms. Proc. of the IEEE, 2005,93(2):232–275.
[8] Pekurovsky D. P3DFFT: A framework for parallel computations of Fourier transforms in three dimensions. SIAM Journal on
Scientific Computing, 2012,34(4):C192–C209. [doi: 10.1137/11082748X]
[9] Ayala O, Wang LP. Parallel implementation and scalability analysis of 3D fast Fourier transform using 2D domain decomposition.
Parallel Computing, 2013,39(1):58–77. [doi: 10.1016/j.parco.2012.12.002]