Research On The Key Technology Of FFT Algorithm Implementation And Optimization For SIMD Computing Platform

Fast Fourier Transform(FFT)is one of the most important basic algorithms,and has been widely used in scientific computing,signal processing,image processing and other fields.With the further improvement of real-time requirements in these application areas,the Fast Fourier Transform algorithm is facing increasingly higher performance requirements.In the existing FFT algorithm library,the resolution speed and calculation accuracy of the FFT algorithm are limited to a certain extent,and few researchers have proposed high performance implementation of the even base CooleyTukey fast Fourier transform based on SIMD computing platform.Corresponding optimization strategies and in-depth study of technical methods.Based on this,a set of optimization strategy and method for Cooley-Tukey fast Fourier transform for evennumbered basis is proposed.Firstly,a SIMD-friendly butterfly network supporting mixed base is constructed,and then the minimum base rotation factor is minimized.The complexity of the butterfly calculation is then optimized by SIMD assembly optimization,assembly instruction rearrangement and selection,register allocation strategy formulation,high performance matrix transposition algorithm,etc.Finally,a high performance FFT algorithm library is implemented.Currently,the most popular and widely used FFTs are FFTW and Intel? MKL FFTW.The experimental results show that on the SIMD computing platform,ARM v8 architecture and X86 architecture,the newly proposed FFT algorithm library mainly for the even-based Cooley-Tukey FFT technology is better than the open source FFTW and Intel? MKL.FFTW.The newly proposed high-performance algorithm optimization and implementation technology method system can be extended to the implementation and optimization of other radix except the even base,which lays a foundation for further research and development work,and then breaks through the FFT algorithm on various hardware platforms.A performance bottleneck on the implementation of a set of platform-specific high-performance FFT algorithm library.