Faster Fourier Transforms via Automatic Program Specialization

1. L.O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, Computer Science Department, University of Copenhagen, May 1994. DIKU Technical Report 94/19.

   Google Scholar 

2. J. Arndt. URL: http://www.jjj.de/fxt/fxt970929.tgz in the file http://www.hfloat/src/fxt/simplfft/fft.c.

3. E. Bach and J. Shallit. Algorithmic Number Theory. The MIT Press, 1996.

   Google Scholar 

4. G. J. Barzdins and M. A. Bulyonkov. Mixed computation and translation: Linearisation and decomposition of compilers. Preprint 791, Computing Centre of Siberian division of USSR Academy of Sciences, Novosibirsk, 1988.

   Google Scholar 

5. C. Consel, L. Hornof, F. Noël, J. Noyé, and E.N. Volanschi. A uniform approach for compile-time and run-time specialization. In O. Danvy, R. Glück, and P. Thiemann, editors, Partial Evaluation, International Seminar, Dagstuhl Castle, number 1110 in Lecture Notes in Computer Science, pages 54–72, February 1996.

   Chapter  Google Scholar 

6. C. Consel and F. Noël. A general approach for run-time specialization and its application to C. In POPL96 [20], pages 145–156.

   Google Scholar 

7. J. W. Cooley and J. W. Tukey. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90):297–301, April 1965.

   Article  MathSciNet  MATH  Google Scholar 

8. Standard Performance Evaluation Corporation. SPEC95. URL: http://www.specbench.org.

9. D.R. Engler, W.C. Hsieh, and M.F. Kaashoek. ‘C: A language for high-level, efficient, and machine-independent dynamic code generation. In POPL96 [20], pages 131–144.

   Google Scholar 

10. M. Frigo and S. Johnson. FFTW user’s manual, 1997. URL: http://theory.lcs.mit.edu/~fftw/.

11. R. Glück, R. Nakashige, and R. Zöchling. Binding-time analysis applied to mathematical algorithms. In J. Doležal and J. Fidler, editors, System Modelling and Optimization, pages 137–146. Chapman & Hall, 1995.

    Google Scholar 

12. B. Grant, M. Mock, M. Philipose, C. Chambers, and S.J. Eggers. Annotation-directed run-time specialization in C. In PEPM’97 [19], pages 163–178.

    Google Scholar 

13. L. Hornof and J. Noyé. Accurate binding-time analysis for imperative languages: Flow, context, and return sensitivity. In PEPM’97 [19], pages 63–73.

    Google Scholar 

14. N.D. Jones, C. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. International Series in Computer Science. Prentice-Hall, June 1993.

    Google Scholar 

15. T.B. Knoblock and E. Ruf. Data specialization. In Proceedings of the ACM SIGPLAN’ 96 Conference on Programming Language Design and Implementation, pages 215–225, Philadelphia, PA, May 1996. ACM SIGPLAN Notices, 31(5). Also TR MSR-TR-96-04, Microsoft Research, February 1996.

    Google Scholar 

16. J.L. Lawall. Faster Fourier transforms via automatic program specialization. Publication interne 1192, IRISA, Rennes, France, May 1998.

    Google Scholar 

17. K. Malmkjær. Program and data specialization: Principles, applications, and self-application. Master’s thesis, DIKU, University of Copenhagen, Denmark, August 1989.

    Google Scholar 

18. F. Noël, L. Hornof, C. Consel, and J. Lawall. Automatic, template-based runtime specialization: Implementation and experimental study. In International Conference on Computer Languages, pages 132–142, Chicago, IL, May 1998. IEEE Computer Society Press. Also available as IRISA report PI-1065.

    Google Scholar 

19. ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, Amsterdam, The Netherlands, June 1997. ACM Press.

    Google Scholar 

20. Conference Record of the 23^rd Annual ACM SIGPLAN-SIGACT Symposium on Principles Of Programming Languages, St. Petersburg Beach, FL, USA, January 1996. ACM Press.

    Google Scholar 

21. W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery. Numerical Recipes in C The Art of Scientific Computing. Cambridge University Press, Cambridge, 2nd edition, 1995.

    MATH  Google Scholar 

22. A. Schönhage, A.F.W. Grotefeld, and E. Vetter. Fast Algorithms: A Multitape Turing Machine Implementation. BI-Wissenschaftsverlag, 1994.

    Google Scholar 

Download references