Article

Relating FFTW and split-radix

Authors:

Oleg Kiselyov,

Walid TahaAuthors Info & Claims

ICESS'04: Proceedings of the First international conference on Embedded Software and Systems

Pages 488 - 493

https://doi.org/10.1007/11535409_71

Published: 09 December 2004 Publication History

Publisher Site

Abstract

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 2ⁿ. While the quality of the generated code was promising, it used more floating-point 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.

References

[1]

W. Boehm, J. Hammes, B. Draper, M. Chawathe, C. Ross, R. Rinker, and W. Najjar. Mapping a single assignment programming language to reconfigurable systems. In Supercomputing, number 21, pages 117-130, 2002.

Digital Library

Google Scholar

[2]

P. Cousot and R. Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In 4th ACM Symposium on Principles of Programming Languages, pages 238-252. ACM, 1977.

Digital Library

Google Scholar

[3]

Matteo Frigo. A fast Fourier transform compiler. In Proceedings of the Conference on Programming Language Design and Implementation, pages 169-180, 1999.

Digital Library

Google Scholar

[4]

C. S. Burrus I. W. Selesnick. Automatic generation of prime length FFT programs. In IEEE Transactions on Signal Processing, pages 14-24, Jan 1996.

Digital Library

Google Scholar

[5]

Oleg Kiselyov, Kedar Swadi, and Walid Taha. A methodology for generating verified combinatorial circuits. In the International Workshop on Embedded Software (EMSOFT 04), Lecture Notes in Computer Science, Pisa, Italy, 2004. Springer-Verlag. To appear.

Digital Library

Google Scholar

[6]

Xavier Leroy. Objective Caml, 2000. Available from http://caml.inria.fr/ocaml/.

Google Scholar

[7]

R. Lipsett, E. Marschner, and M. Shaded. VHDL - The Language. In IEEE Design and Test of Computers, pages 28-41, April 1986.

Digital Library

Google Scholar

[8]

Eugenio Moggi. Notions of computation and monads. Information and Computation, 93(1), 1991.

Digital Library

Google Scholar

[9]

M.T. Heideman and C.S. Burrus. On the number of multiplications necessary to compute a length-2ⁿ DFT. IEEE Trans. ASSP, ASSP-34(1):91-95, February 1986.

Google Scholar

[10]

Oregon Graduate Institute Technical Reports. P.O. Box 91000, Portland, OR 97291- 1000, USA. Available online from ftp://cse.ogi.edu/pub/tech-reports/README.html.

Google Scholar

[11]

Walid Taha. Multi-Stage Programming: Its Theory and Applications. PhD thesis, Oregon Graduate Institute of Science and Technology, 1999. Available from {10}.

Digital Library

Google Scholar

[12]

Walid Taha, Stephan Ellner, and Hongwei Xi. Generating Imperative, Heap-Bounded Programs in a Functional Setting. In Proceedings of the Third International Conference on Embedded Software, Philadelphia, PA, October 2003.

Google Scholar

[13]

Walid Taha and Michael Florentin Nielsen. Environment classifiers. In The Symposium on Principles of Programming Languages (POPL '03), New Orleans, 2003.

Digital Library

Google Scholar

[14]

Donald E. Thomas and Philip R. Moorby. The Verilog Hardware Description Language. Kluwer Academic Publishers, 3rd edition, 1996.

Digital Library

Google Scholar

Cited By

View all

Kiselyov O(2024)MetaOCaml: Ten Years LaterFunctional and Logic Programming10.1007/978-981-97-2300-3_12(219-236)Online publication date: 15-May-2024
https://dl.acm.org/doi/10.1007/978-981-97-2300-3_12
Shahmohammadian MMainland GTilevich EDe Roover C(2021)Metaprogramming with combinatorsProceedings of the 20th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3486609.3487198(43-54)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1145/3486609.3487198
Masuda MKameyama Y(2021)FFT Program Generation for Ring LWE-Based CryptographyAdvances in Information and Computer Security10.1007/978-3-030-85987-9_9(151-171)Online publication date: 8-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-85987-9_9
Show More Cited By

Index Terms

Relating FFTW and split-radix
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computation of transforms

Recommendations

Split vector-radix fast Fourier transform

The split-radix approach for computing the discrete Fourier transform (DFT) is extended for the vector-radix fast Fourier transform (FFT) to two and higher dimensions. It is obtained by further splitting the ( N /2× N /2) transforms with twiddle factors ...
Low-Power Split-Radix FFT Processors Using Radix-2 Butterfly Units
Split-radix fast Fourier transform (SRFFT) is an ideal candidate for the implementation of a low-power FFT processor, because it has the lowest number of arithmetic operations among all the FFT algorithms. In the design of such processors, an efficient ...
A Modified Split-Radix FFT With Fewer Arithmetic Operations

Recent results by Van Buskirk have broken the record set by Yavne in 1968 for the lowest exact count of real additions and multiplications to compute a power-of-two discrete Fourier transform (DFT). Here, we present a simple recursive modification of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICESS'04: Proceedings of the First international conference on Embedded Software and Systems

December 2004

610 pages

ISBN:3540281282

Editors:
Zhaohui Wu
College of Computer Science, Zhejiang University, Hangzhou, Zhejiang, China
,
Chun Chen
College of Computer Science, Zhejiang University, 973 WSN Joint Lab, Hangzhou, Zhejiang, China
,
Minyi Guo
Department of Computer Science and Engineering, Shanghai Jiao Tong University, 973 WSN Joint Lab, Shanghai, Zhejiang, China
,
Jiajun Bu
College of Computer Science, Zhejiang University, 973 WSN Joint Lab, Hangzhou, Zhejiang, China

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 09 December 2004

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kiselyov O(2024)MetaOCaml: Ten Years LaterFunctional and Logic Programming10.1007/978-981-97-2300-3_12(219-236)Online publication date: 15-May-2024
https://dl.acm.org/doi/10.1007/978-981-97-2300-3_12
Shahmohammadian MMainland GTilevich EDe Roover C(2021)Metaprogramming with combinatorsProceedings of the 20th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3486609.3487198(43-54)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1145/3486609.3487198
Masuda MKameyama Y(2021)FFT Program Generation for Ring LWE-Based CryptographyAdvances in Information and Computer Security10.1007/978-3-030-85987-9_9(151-171)Online publication date: 8-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-85987-9_9
Mainland GJohnson J(2017)A Haskell compiler for signal transformsACM SIGPLAN Notices10.1145/3170492.313605652:12(219-232)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3170492.3136056
Mainland GJohnson JFlatt MErdweg S(2017)A Haskell compiler for signal transformsProceedings of the 16th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3136040.3136056(219-232)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3136040.3136056
Kameyama YKiselyov OShan CChin WHage J(2014)Combinators for impure yet hygienic code generationProceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation10.1145/2543728.2543740(3-14)Online publication date: 11-Jan-2014
https://dl.acm.org/doi/10.1145/2543728.2543740
Ofenbeck GRompf TStojanov AOdersky MPüschel M(2013)Spiral in scalaACM SIGPLAN Notices10.1145/2637365.251722849:3(125-134)Online publication date: 27-Oct-2013
https://dl.acm.org/doi/10.1145/2637365.2517228
Ofenbeck GRompf TStojanov AOdersky MPüschel MJärvi JKästner C(2013)Spiral in scalaProceedings of the 12th international conference on Generative programming: concepts & experiences10.1145/2517208.2517228(125-134)Online publication date: 27-Oct-2013
https://dl.acm.org/doi/10.1145/2517208.2517228
Mainland G(2012)Explicitly heterogeneous metaprogramming with MetaHaskellACM SIGPLAN Notices10.1145/2398856.236457247:9(311-322)Online publication date: 9-Sep-2012
https://dl.acm.org/doi/10.1145/2398856.2364572
Mainland GThiemann PFindler R(2012)Explicitly heterogeneous metaprogramming with MetaHaskellProceedings of the 17th ACM SIGPLAN international conference on Functional programming10.1145/2364527.2364572(311-322)Online publication date: 9-Sep-2012
https://dl.acm.org/doi/10.1145/2364527.2364572
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Split vector-radix fast Fourier transform

Low-Power Split-Radix FFT Processors Using Radix-2 Butterfly Units

A Modified Split-Radix FFT With Fewer Arithmetic Operations

Comments

Information

Published In

Sponsors

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations