Short vector code generation for the discrete Fourier transform
Short vector code generation for the discrete Fourier transform
复制标题
离散傅里叶变换的短矢量代码生成
DOI：
10.1109/ipdps.2003.1213153
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Markus Püschel
中科院分区：
文献类型：
--
作者：
F. Franchetti;Markus Püschel
在本文中，我们使用的数学方法来自动生成高性能的离散傅立叶变换（DFT）的短矢量码。我们代表了著名的Cooley-Tukey快速傅立叶变换的数学符号，并正式推导出一个“短向量变量”。使用这种递归，我们生成一个给定的DFT的大量不同的算法，表示为公式，并将它们转换成短矢量代码。然后，我们提出了一个向量代码特定的动态规划方法，搜索在给定的架构上的最快的不同实现的空间。我们将此方法作为SPIRAL库生成器的一部分在奔腾III和奔腾4上实现，我们自动生成的SSE和SSE 2矢量代码与手动调整的英特尔供应商库相比毫不逊色。
In this paper we use a mathematical approach to automatically generate high performance short vector code for the discrete Fourier transform (DFT). We represent the well-known Cooley-Tukey fast Fourier transform in a mathematical notation and formally derive a "short vector variant". Using this recursion we generate for a given DFT a large number of different algorithms, represented as formulas, and translate them into short vector code. Then we present a vector code specific dynamic programming method that searches in the space of different implementations for the fastest on the given architecture. We implemented this approach as part of the SPIRAL library generator On Pentium III and 4, our automatically generated SSE and SSE2 vector code compares favorably with the hand-tuned Intel vendor library.