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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2020,31(10):3184−3196 [doi: 10.13328/j.cnki.jos.005848] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
申威 26010 众核处理器上一维 FFT 实现与优化

5
2
1,2
5
1,4
赵玉文 , 敖玉龙 , 杨 超 , 刘芳芳 1,3,4 , 尹万旺 ， 林蓉芬
1
(中国科学院 软件研究所 并行软件与计算科学实验室,北京 100190)
2 (北京大学 数学科学学院,北京 100871)
3 (计算机科学国家重点实验室(中国科学院 软件研究所),北京 100190)
4
(中国科学院大学,北京 100049)
5
(国家并行计算机工程技术研究中心,北京 100190)
通讯作者: 杨超, E-mail: chao_yang@pku.edu.cn

摘 要: 根据申威 26010 众核处理器的特点提出了基于两层分解的一维 FFT 众核并行算法.该算法基于迭代的
Stockham FFT 计算框架和 Cooley-Tukey FFT 算法,将大规模 FFT 分解成一系列的小规模 FFT 来计算,并通过设计
合理的任务划分方式、寄存器通信、双缓冲以及 SIMD 向量化等与计算平台相关的优化方法来提高 FFT 的计算性
能.最后对所提出算法的性能进行了测试,相比于单主核上运行的 FFTW3.3.4 库,获得了平均 44.53x 的加速比,最高
加速比可达 56.33x,且其带宽利用率最高可达 83.45%.
关键词: 申威 26010 处理器;一维 FFT;两层分解;Cooley-Tukey;众核并行
中图法分类号: TP301

中文引用格式: 赵玉文,敖玉龙,杨超,刘芳芳,尹万旺,林蓉芬.申威 26010 众核处理器上一维 FFT 实现与优化.软件学报,
2020,31(10):3184–3196. http://www.jos.org.cn/1000-9825/5848.htm
英文引用格式: Zhao YW, Ao YL, Yang C, Liu FF, Yin WW, Lin RF. General implementation of 1-D FFT on the Sunway 26010
processor. Ruan Jian Xue Bao/Journal of Software, 2020,31(10):3184−3196 (in Chinese). http://www.jos.org.cn/1000-9825/5848.
htm

General Implementation of 1-D FFT on the Sunway 26010 Processor

2
1,4
5
5
1,2
ZHAO Yu-Wen , AO Yu-Long , YANG Chao , LIU Fang-Fang 1,3,4 , YIN Wan-Wang , LIN Rong-Fen
1
(Laboratory of Parallel Software and Computational Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190,
China)
2
(School of Mathematical Sciences, Peking University, Beijing 100871, China)
3
(State Key Laboratory of Computer Science (Institute of Software, Chinese Academy of Sciences), Beijing 100190, China)
4
(University of Chinese Academy of Sciences, Beijing 100049, China)
5
(National Research Center of Parallel Computer Engineering and Technology, Beijing 100190, China)
Abstract: A two-layer decomposition 1-D FFT multi-core parallel algorithm is proposed according to the characteristics of Sunway
26010 processor. It is based on the iterative Stockholm FFT framework and the Cooley-Tukey FFT algorithm. It decomposes large scale
FFT into a series of small scale FFTs. It improves the performance of the algorithm by means of designing reasonable task partitioning,
register communication, double-buffering, and SIMD vectorization. Finally, the performance of the two-layer decomposition 1-D FFT
multi-core parallel algorithm is tested. It achieves an average speedup of 44.53x, with a maximum speedup of up to 56.33x, and a
maximum bandwidth utilization of 83.45%, compared to FFTW3.3.4 library running on the single MPE.

∗ 基金项目: 国家重点研发计划(2016YFB0200603); 北京市自然科学基金(JQ18001)
Foundation item: National Key Research and Development Program of China (2016YFB0200603); Beijing Natural Science
Foundation, China (JQ18001)
收稿时间: 2018-01-22; 修改时间: 2018-09-20; 采用时间: 2019-03-29