A fast Fourier transform compiler
A fast Fourier transform compiler
复制标题
DOI：
10.1145/301631.301661
复制
发表时间：
1999-05-01
影响因子：
--
通讯作者：
Frigo, M
中科院分区：
文献类型：
--
作者：
Frigo, M
用于计算离散傅立叶变换 (DFT) 的 FFTW 库已在学术界和工业界获得广泛接受，因为它在各种机器上提供了出色的性能（甚至可以与供应商提供的同等库竞争或更快）。在 FFTW 中，大多数性能关键代码是由专用编译器（称为 genfft）自动生成的，该编译器输出 C 代码。 genfft 用 Objective Caml 编写，可以生成任何输入长度的 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.