QQ客服 官方微博 反馈留言

	Memory Efficient Two-Pass 3D FFT Algorithm for Intel~ Xeon Phi~(TM) Coprocessor
	Liu YQ(刘益群) ; Li Y(李焱) ; Zhang YQ(张云泉) ; Zhang XY(张先轶) ; Yi-Qun Liu ; Yan Li ; Yun-Quan Zhang ; Xian-Yi Zhang
	2016-03-30 ; 2016-03-30
关键词	3D-FFT memory efficient many-core Many Integrated Core Intel Xeon PhiTM TP332
其他题名	Memory Efficient Two-Pass 3D FFT Algorithm for Intel~ Xeon Phi~(TM) Coprocessor
中文摘要	Equipped with 512-bit wide SIMD instructions and large numbers of computing cores,the emerging x86-based Intel Many Integrated Core(MIC) Architecture provides not only high floating-point performance,but also substantial off-chip memory bandwidth. The 3D FFT(three-dimensional fast Fourier transform) is a widely-studied algorithm; however,the conventional algorithm needs to traverse the data array three times. In each pass,it computes multiple 1D FFTs along one of three dimensions,giving rise to plenty of non-unit strided memory accesses. In this paper,we propose a two-pass 3D FFT algorithm,which mainly aims to reduce the amount of explicit data transfer between the memory and the on-chip cache.The main idea is to split one dimension into two sub-dimensions,and then combine the transform along each sub-dimension with one of the rest dimensions respectively. The difference in amount of TLB misses resulting from decomposition along different dimensions is analyzed in detail. Multi-level parallelism is leveraged on the many-core system for a high degree of parallelism and better data reuse of local cache. On top of this,a number of optimization techniques,such as memory padding,loop transformation and vectorization,are employed in our implementation to further enhance the performance.We evaluate the algorithm on the Intel Xeon PhiTMcoprocessor 7110 P,and achieve a maximum performance of 136 Gflops with 240 threads in offload mode,which beats the vendor-specific Intel MKL library by a factor of up to 2.22 X.; Equipped with 512-bit wide SIMD instructions and large numbers of computing cores,the emerging x86-based Intel Many Integrated Core(MIC) Architecture provides not only high floating-point performance,but also substantial off-chip memory bandwidth. The 3D FFT(three-dimensional fast Fourier transform) is a widely-studied algorithm; however,the conventional algorithm needs to traverse the data array three times. In each pass,it computes multiple 1D FFTs along one of three dimensions,giving rise to plenty of non-unit strided memory accesses. In this paper,we propose a two-pass 3D FFT algorithm,which mainly aims to reduce the amount of explicit data transfer between the memory and the on-chip cache.The main idea is to split one dimension into two sub-dimensions,and then combine the transform along each sub-dimension with one of the rest dimensions respectively. The difference in amount of TLB misses resulting from decomposition along different dimensions is analyzed in detail. Multi-level parallelism is leveraged on the many-core system for a high degree of parallelism and better data reuse of local cache. On top of this,a number of optimization techniques,such as memory padding,loop transformation and vectorization,are employed in our implementation to further enhance the performance.We evaluate the algorithm on the Intel Xeon PhiTMcoprocessor 7110 P,and achieve a maximum performance of 136 Gflops with 240 threads in offload mode,which beats the vendor-specific Intel MKL library by a factor of up to 2.22 X.
语种	英语 ; 英语
内容类型	期刊论文
源URL	[http://ir.lib.tsinghua.edu.cn/ir/item.do?handle=123456789/146917]
专题	清华大学
推荐引用方式 GB/T 7714	Liu YQ,Li Y,Zhang YQ,et al. Memory Efficient Two-Pass 3D FFT Algorithm for Intel~ Xeon Phi~(TM) Coprocessor[J],2016, 2016.
APA	刘益群.,李焱.,张云泉.,张先轶.,Yi-Qun Liu.,...&Xian-Yi Zhang.(2016).Memory Efficient Two-Pass 3D FFT Algorithm for Intel~ Xeon Phi~(TM) Coprocessor..
MLA	刘益群,et al."Memory Efficient Two-Pass 3D FFT Algorithm for Intel~ Xeon Phi~(TM) Coprocessor".(2016).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。