Memory Efficient Two-Pass 3D FFT Algorithm for Intel~ Xeon Phi^(TM) Coprocessor

作     者：刘益群 李焱 张云泉 张先轶 Yi-Qun Liu;Yan Li;Yun-Quan Zhang;Xian-Yi Zhang

作者机构：Institute of SoftwareChinese Academy of Sciences University of Chinese Academy of Sciences Department of Computer Science and TechnologyTsinghua University CCF ACM IEEE State Key Laboratory of Computer ArchitectureInstitute of Computing TechnologyChinese Academy of Sciences 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2014年第29卷第6期

页      面：989-1002页

核心收录：

学科分类：0711[理学-系统科学] 07[理学] 08[工学] 080401[工学-精密仪器及机械] 0804[工学-仪器科学与技术] 080402[工学-测试计量技术及仪器] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the National Natural Science Foundation of China under Grant Nos.61133005,61272136,61221062,61402441,61432018 the National High Technology Research and Development 863 Program of China under Grant No.2012AA010903 the Chinese Academy of Sciences Special Grant for Postgraduate Research,Innovation and Practice under Grant No.11000GBF01 

主　　题：3D-FFT memory efficie many-core Many Integrated Core Intel(R) Xeon PhiTM 

摘      要：Equipped with 512-bit wide SIMD inst d large numbers of computing cores, the emerging x86-based Intel（R） Many Integrated Core （MIC） Architecture ot only high floating-point performance, but also substantial off-chip memory bandwidth. The 3D FFT （three-di fast Fourier transform） is a widely-studied algorithm; however, the conventional algorithm needs to traverse the three times. In each pass, it computes multiple 1D FFTs along one of three dimensions, giving rise to plenty of rided memory accesses. In this paper, we propose a two-pass 3D FFT algorithm, which mainly aims to reduce of explicit data transfer between the memory and the on-chip cache. The main idea is to split one dimension into ensions, and then combine the transform along each sub-dimension with one of the rest dimensions respectively erence in amount of TLB misses resulting from decomposition along different dimensions is analyzed in detail. el parallelism is leveraged on the many-core system for a high degree of parallelism and better data reuse of loc On top of this, a number of optimization techniques, such as memory padding, loop transformation and vectoriz employed in our implementation to further enhance the performance. We evaluate the algorithm on the Intel（R） PhiTM coprocessor 7110P, and achieve a maximum performance of 136 Gflops with 240 threads in offload mode, which ts the vendor-specific Intel（R）MKL library by a factor of up to 2.22X.