Faster Fourier Transforms via Automatic Program Specialization
Résumé
Because of its wide applicability, many efficient implementations of the Fast Fourier Transform have been developed. In this paper we propose that efficient implementations can be produced automatically and reliably by partial evaluation. Partial evaluation of an unoptimized implementation produces a speedup of over 7 times. The automatically generated result of partial evaluation has performance comparable to or exceeding that produced by a variety of hand optimizations. We analyze the benefits of partial evaluation at both compile time and run time, and survey related hand-optimization techniques.