Relating FFTW and Split-Radix

摘要：

Recent work showed that staging and abstract interpretation can be used to derive correct families of combinatorial circuits, and illustrated this technique with an in-depth analysis of the Fast Fourier Transform (FFT) for sizes 2n.While the quality of the generated code was promising, it used more fioatingpoint operations than the well-known FFTW codelets and split-radix algorithm.This paper shows that staging and abstract interpretation can in fact be used to produce circuits with the same number of floating-point operations as each of split-radix and FFTW. In addition, choosing between two standard implementations of complex multiplication produces results that match each of the two algorithms. Thus, we provide a constructive method for deriving the two distinct algorithms.

作者: Oleg Kiselyov Walid Taha

作者单位: Monterey, CA 93943 Department of Computer Science, Rice University

会议类型: 国际会议

会议名称: 首届嵌入式软件与系统国际会议(Proceedings of the First International Conference on Embedded Software and System)

会议地点: 杭州

会议语种:英文

页码: 437-442

在线出版日期: 2004-12-09（万方平台首次上网日期，不代表论文的发表时间）