A fast Fourier transform compiler
A fast Fourier transform compiler
复制标题
DOI：
10.1145/989393.989457
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Matteo Frigo
中科院分区：
文献类型：
--
作者：
Matteo Frigo
用于计算离散傅立叶变换（DFT）的FFTW库在学术界和工业界都得到了广泛的认可，因为它在各种机器上都提供了出色的性能（甚至比供应商提供的等效库更快或更有竞争力）。在FFTW中，大多数性能关键代码是由一个名为genfft的专用编译器自动生成的，该编译器输出C代码。用Objective Caml语言编写的genfft可以生成任意输入长度的DFT程序，并且可以针对输入数据是真实的而不是复数的常见情况专门化DFT程序。出乎意料的是，genfft“发现”了以前未知的算法，并且能够降低其他一些现有算法的算术复杂度。本文详细介绍了这个专用编译器的内部结构，并认为专用编译器是一个有价值的工具。
The FFTW library for computing the discrete Fourier transform (DFT) has gained a wide acceptance in both academia and industry, because it provides excellent performance on a variety of machines (even competitive with or faster than equivalent libraries supplied by vendors). In FFTW, most of the performance-critical code was generated automatically by a special-purpose compiler, called genfft, that outputs C code. Written in Objective Caml, genfft can produce DFT programs for any input length, and it can specialize the DFT program for the common case where the input data are real instead of complex. Unexpectedly, genfft "discovered" algorithms that were previously unknown, and it was able to reduce the arithmetic complexity of some other existing algorithms. This paper describes the internals of this special-purpose compiler in some detail, and it argues that a specialized compiler is a valuable tool.