Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2024, Vol. 58 Issue (1): 78-86    DOI: 10.3785/j.issn.1008-973X.2024.01.009
    
Parallel optimization of large-point FFT on Sunway 26010
Jun GUO1,2(),Peng LIU3,Xinyao YANG4,Lufei ZHANG5,Dong WU5
1. School of Information Engineering and Internet of Things, Huzhou Vocational and Technical College, Huzhou 313000, China
2. Huzhou Key Laboratory of IoT Intelligent System Integration Technology, Huzhou Vocational and Technical College, Huzhou 313000, China
3. College of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027, China
4. Ant Group Limited Company, Hangzhou 310013, China
5. State Key Laboratory of Mathematical Engineering and Advanced Computing, Wuxi 214125, China
Download: HTML     PDF(1231KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A many-core parallel optimization scheme for large-point FFT was proposed according to the structural characteristics and programming specifications of the domestic Sunway 26010 processor, which was used in the Sunway Taihu Light supercomputer. The scheme was derived from the classic Cooley-Tukey FFT algorithm, and was accelerated in parallel by iteratively decomposing the one-dimensional large-point data into two-dimensional small-scale matrices. The "column-sharing, row-continuity" strategy was specially proposed in order to solve the problem of reading, writing, transposing and calculating of the "column FFT" of the matrix. The computing resources and transmission bandwidth of the many-core processor were fully utilized by reasonable data allocation, rearrangement and exchange combined with other optimization methods such as SIMD vectorization, twiddle factor optimization, double-buffering, register communication and stride transmission. The experimental results prove that the single core-group of 64 slave cores running parallel program can achieve a maximum speed-up of 65x and an average speed-up of more than 48x compared with the main core running the FFTW library.

Key words： Sunway Taihu Light      Sunway 26010      fast Fourier transform      Cooley-Tukey algorithm      many-core parallelism     
Received: 30 December 2022      Published: 07 November 2023
CLC:  TP 338  
Fund:  数学工程与先进计算国家重点实验室开放基金资助项目（2019A10）
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Jun GUO
Peng LIU
Xinyao YANG
Lufei ZHANG
Dong WU
Cite this article:

Jun GUO,Peng LIU,Xinyao YANG,Lufei ZHANG,Dong WU. Parallel optimization of large-point FFT on Sunway 26010. Journal of ZheJiang University (Engineering Science), 2024, 58(1): 78-86.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2024.01.009     OR     https://www.zjujournals.com/eng/Y2024/V58/I1/78


大点数FFT在“申威26010”上的并行优化

根据“神威·太湖之光”超级计算机所用国产“申威26010”处理器的架构特点和编程规范，提出针对大点数FFT的众核并行优化方案. 该方案源自经典的Cooley-Tukey FFT算法，通过将一维大点数数据迭代分解为二维小规模矩阵进行并行加速. 为了解决矩阵“列FFT”的读写、转置和计算问题，提出“列均分-行连续”的读写策略，通过对数据进行合理的分配、重排、交换，结合SIMD向量化、旋转因子优化、双缓冲、寄存器通信、跨步传输等优化手段，充分利用了众核处理器的计算资源和传输带宽. 实验结果显示，单核组64从核并行程序较主核运行FFTW库，可以达到最高65x、平均48x以上的加速比.


关键词： 神威·太湖之光,  申威26010,  快速傅里叶变换,  Cooley-Tukey算法,  众核并行 
Fig.1 Schematic of Sunway 26010 processor
Fig.2 Calculation process of 1D to 2D FFT
Fig.3 Column-sharing, row-continuity strategy
Fig.4 Data distribution among slave cores
Fig.5 SIMD FFT data arrangement
Fig.6 Double buffering scheme
Fig.7 Calculation process of large matrix column FFT
Fig.8 Speedup using twiddle factor optimization, SIMD, stride transmission, double-buffering scheme
类型 三角函数调用次数 复数乘法和加法的计算次数
优化前 ${{10 N} / {64}}$ 0
优化后 $16+{{{N_1}} / {64}}$ ${{5 {N_1}} / {64}}+{{9 {N_2}} / {64}}+{N / {256}}$
Tab.1 Calculation times of twiddle factor before and after optimization
Fig.9 DMA transmission bandwidth and utilization
Fig.10 Proportion of time consumed by transmission and calculation
数据量 CS CP SP
32 768 8 063 390 589 862 13.67
65 536 32 225 901 1 004 552 32.08
131 072 83 236 162 1 930 484 43.12
262 144 190 366 763 3 690 079 51.59
524 288 418 159 392 7 138 959 58.57
1 048 576 855 418 759 13 790 789 62.03
2 097 152 1 801 385 481 27 709 105 65.01
4 194 304 3 717 210 028 63 708 120 58.35
Tab.2 Accelerated test results of parallel FFT
[21]   SUN Jiadong, SUN Qiao, DENG Pan, et al Research on the optimization of blas level 1 and 2 functions on shenwei many-core processor[J]. Computer Systems and Application, 2017, 26 (11): 101- 108
doi: 10.15888/j.cnki.csa.006045
[22]   徐燚. 基于新一代申威众核处理器的BLAS并行优化的研究[D]. 上海: 华东师范大学, 2022: 15.
XU Yi. Research on parallel optimization of BLAS based on the new generation of sunway many-core processor [D]. Shanghai: East China Normal University, 2022: 15.
[23]   赵玉文, 敖玉龙, 杨超, 等 申威26010众核处理器上一维FFT实现与优化[J]. 软件学报, 2020, 31 (10): 3184- 3196
doi: 10.13328/j.cnki.jos.005848
[1]   TOP500. Top500 lists june 2016 [EB/OL]. [2016-06-30]. https://www.top500.org/lists/top500/2016/06/.
[2]   COOLEY J W, TUKEY J W An algorithm for the machine calculation of complex Fourier series[J]. Mathematics of Computation, 1965, 19 (90): 297- 301
doi: 10.1090/S0025-5718-1965-0178586-1
[3]   PRIYANKA C, LAKSHMI S, SAMHITHA A, et al High speed FFT computation using optimized radix 8 algorithm[J]. International Journal of Advanced Science and Technology, 2020, 29 (4): 6307- 6312
[4]   ELSHAFIY A, EL-MOTAZ M A, FARAG M E, et al. On optimization of mixed-radix FFT: a signal processing approach [C]// Proceedings of the IEEE Wireless Communications and Networking Conference. Marrakesh: IEEE, 2019: 1-6.
[5]   STASINSKI R. Split multiple radix FFT [C]// 30th European Signal Processing Conference. Belgrade: IEEE, 2022: 2251-2255.
[6]   KULKARNI V, OZA S Design and implementation of 3d FFT[J]. International Journal of Scientific and Engineering Research, 2017, 8 (4): 186- 189
[7]   GARRIDO M, SÁNCHEZ M A, LÓPEZ-VALLEJO M L, et al A 4096-point radix-4 memory-based FFT using DSP slices[J]. IEEE Transactions on Very Large Scale Integration Systems, 2017, 25 (1): 375- 379
doi: 10.1109/TVLSI.2016.2567784
[8]   XIA K F, WU B, XIONG T, et al A memory-based FFT processor design with generalized efficient conflict-free address schemes[J]. IEEE Transactions on Very Large Scale Integration Systems, 2017, 25 (6): 1919- 1929
doi: 10.1109/TVLSI.2017.2666820
[9]   INGEMARSSON C, KÄLLSTRÖM P, QURESHI F, et al Efficient FPGA mapping of pipeline SDF FFT cores[J]. IEEE Transactions on Very Large Scale Integration Systems, 2017, 25 (9): 2486- 2497
doi: 10.1109/TVLSI.2017.2710479
[10]   SHIH X Y, CHOU H R, LIU Y Q VLSI design and implementation of reconfigurable 46-mode combined-radix-based FFT hardware architecture for 3GPP LTE applications[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2018, 65 (1): 118- 129
doi: 10.1109/TCSI.2017.2725338
[11]   FRIGO M, JOHNSON S G The design and implementation of fftw3[J]. Proceedings of the IEEE, 2005, 93 (2): 216- 231
doi: 10.1109/JPROC.2004.840301
[12]   INTEL. Intel oneapi math kernel library [EB/OL]. [2020-09-20]. https://www.intel.com/content/www/us/en/developer/tools/oneapi/onemkl.html.
[13]   NVIDIA. Fast Fourier transforms for nvidia GPUs [EB/OL]. [2021-03-30]. https://developer.nvidia.com/cufft.
[14]   AYALA A, TOMOV S, HAIDAR A, et al. Heffte: highly efficient FFT for exascale [C]// Proceedings of the International Conference on Computational Science. Amsterdam: Springer, 2020: 262-275.
[15]   张明. 龙芯平台上高性能计算的性能优化关键问题研究[D]. 合肥: 中国科学技术大学, 2017: 47.
ZHANG Ming. Research on key issues of performance optimization in high performance computing based on the Godson [D]. Hefei: University of Science and Technology of China, 2017: 47.
[16]   郭金鑫. 实数FFT算法在ARM V8处理器上的实现与性能优化研究[D]. 太原: 太原理工大学, 2021: 33.
GUO Jinxin. Real FFT implementation and performance optimization on ARM V8 processor [D]. Taiyuan: Taiyuan University of Technology, 2021: 33.
[17]   操庐宁. 基于X86-64计算平台的FFT实现与并行优化[D]. 长春: 吉林大学, 2019: 27.
CAO Luning. FFT implementation and parallel optimization based on X86-64 computing platform [D]. Changchun: Jilin University, 2019: 27.
[18]   YANG C, XUE W, FU H H, et al. 10m-core scalable fully-implicit solver for nonhydrostatic atmospheric dynamics [C]// Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. Salt Lake City: IEEE, 2016: 57-68.
[19]   FU H H, YIN W W, YANG G W, et al. 18.9-pflops nonlinear earthquake simulation on sunway taihulight: enabling depiction of 18-Hz and 8-meter scenarios [C]// Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. Denver: ACM, 2017: 13-24.
[20]   LIU Y, LIU X, LI F, et al. Closing the "quantum supremacy" gap: achieving real-time simulation of a random quantum circuit using a new sunway supercomputer [C]// Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. St. Louis Missouri: ACM, 2021: 25–36.
[21]   孙家栋, 孙乔, 邓攀, 等 基于申威众核处理器的1、2级BLAS函数优化研究[J]. 计算机系统应用, 2017, 26 (11): 101- 108
doi: 10.15888/j.cnki.csa.006045
[1] Cheng-jin QIN,Jun-zheng JIANG. Radar range super-resolution method based on deep neural network[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(6): 1215-1223.
[2] Yang LUO,Wei ZHANG. Hardware efficient FFT design based on improved rotation factor[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(6): 1199-1207.
[3] Shu-guang SUN,Peng TIAN,Tai-hang DU,Jing-qin WANG. Dense frequency harmonic/interharmonic detection based on apFFT-AMD[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(1): 178-188.
[4] ZHANG Xin-yi, YANG Jia-qiang, ZHANG Xiao-jun. Dynamic economic dispatch incorporating multiple wind farms based on FFT simplified chance constrained programming[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(5): 976-983.
[5] LOU Wen-juan, WANG Jia-wei, YANG Lun, CHEN Yong. Simulation of three-dimensional fluctuating wind velocity field #br# upon thunderstorm downburst[J]. Journal of ZheJiang University (Engineering Science), 2014, 48(7): 1162-1169.
[6] ZHANG Jin-gao, LU Qin-fen, WANG Li, YE Yun-yue, Hong Wei-ming. Measurement of power factor angle of linear metro’s traction
motor based on FFT[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(11): 1981-1984.