Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (5): 41-44.

• 学术探讨 • Previous Articles     Next Articles

An Optimal 2D FFT Algorithm Based on Intel SIMD Instructions

  

  • Received:2006-03-10 Revised:1900-01-01 Online:2007-02-11 Published:2007-02-11

基于Intel SIMD指令的二维FFT优化算法

李成军 周卫峰 朱重光   

  1. 中国科学院遥感应用研究所图像室
  • 通讯作者: 李成军

Abstract: In the large-scale image processing algorithms based on frequency domain method, the most time-consuming part is playing 2D FFT on the image data. In this paper an optimal 2D FFT algorithm based on Intel SIMD technology is presented to solve this problem. Very high performance has been achieved by arranging data layout to benefit from SIMD instructions, using SSE3 instructions to accelerate complex number multiplications and optimizing the cache usage in the 2D case, etc. The result of the experiment demonstrates that the presented algorithm is about 30% faster than the abroad used public domain FFT package FFTW. The algorithm has reached the demand of fast large-scale image processing.

Key words: Large-scale image processing, 2D FFT, SIMD, SSE/SSE3

摘要: 在基于频域的大数据量图像处理算法中,最为耗时的步骤就是对图像数据进行二维FFT变换的过程。本文针对这一问题,提出一种基于Intel SIMD指令的二维FFT优化算法。通过将数据按照便于SIMD指令计算的方式进行组织,利用SSE3指令加速复数乘法,在二维处理中针对处理器缓存进行优化等方法,实现了很高的性能。实验结果表明: 本文描述的算法比目前使用最广泛的公共域FFT程序包FFTW快30%左右。达到了对大数据量图像进行快速处理的要求,具有较大的工程实用价值。

关键词: 大数据量图像处理, 二维FFT, SIMD, SSE/SSE3