SIMD Vectorization of Non-Two-Power Sized FFTs
SIMD Vectorization of Non-Two-Power Sized FFTs
复制标题
非二次幂大小的 FFT 的 SIMD 矢量化
DOI：
10.1109/icassp.2007.366161
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Markus Püschel
中科院分区：
文献类型：
--
作者：
F. Franchetti;Markus Püschel
SIMD（单指令多数据）矢量指令，如英特尔的SSE系列，在大多数体系结构上都是可用的，但很难利用它们来加速。在许多情况下，例如快速傅里叶变换（FFT），信号处理算法必须经过重大变换才能有效地映射。使用Kronecker积形式，我们严格推导了通用基Cooley-Tukey FFT的一个新变体，该变体的结构可以有效地映射任何向量长度v和基。然后，我们将新的FFT包含到程序生成器螺旋中以生成实际的C实现。英特尔SSE的基准测试表明，新算法在几乎所有规模上的性能都优于现有的最佳库——英特尔的MKL和FFTW。
SIMD (single instruction multiple data) vector instructions, such as Intel's SSE family, are available on most architectures, but are difficult to exploit for speed-up. In many cases, such as the fast Fourier transform (FFT), signal processing algorithms have to undergo major transformations to map efficiently. Using the Kronecker product formalism, we rigorously derive a novel variant of the general-radix Cooley-Tukey FFT that is structured to map efficiently for any vector length v and radix. Then, we include the new FFT into the program generator spiral to generate actual C implementations. Benchmarks on Intel's SSE show that the new algorithms perform better on practically all sizes than the best available libraries Intel's MKL and FFTW.