Jianxin Xiong
David Padua
Abstract
We discuss the design and implementation of a compiler that translates formulas representing signal processing transforms into efficient C or Fortran programs. The formulas are represented in a language that we call SPL, an acronym from Signal Processing Language. The compiler is a component of the SPIRAL system which makes use of formula transformations and intelligent search strategies to automatically generate optimized digital signal processing (DSP) libraries. After a discussion of the translation and optimization techniques implemented in the compiler, we use SPL formulations of the fast Fourier transform (FFT) to evaluate the compiler. Our results show that SPIRAL, which can be used to implement many classes of algorithms, produces programs that perform as well as “hard-wired” systems like FFTW.
- 1 L. Auslander, J. Johnson, and R. W. Johnson. Automatic implementation of FFT algorithms. Technical Report DU-MCS-96-01, Dept. of Math. and Computer Science, Drexel University, Philadelphia, PA, June 1996. Presented at the DARPA ACMP PI meeting.]]Google Scholar
- 2 J. Bilmes, K. Asanovic, C. Chin, and J. Demmel. Optimizing matrix multiply using phipac: a portable, high-performance, ansi c code methodology. In Proc. ICS1997, 1997. http://www.icsi.berkeley.edu/~bilmes/phipac/.]] Google ScholarDigital Library
- 3 D. L. Dai, S. K. S. Gupta, S. D. Kaushik, J. H. Lu, R. V. Singh, C.-H. Huang, P. Sadayappan, and R. W. Johnson. EXTENT: A portable programming environment for designing and implementing high-performance block recursive algorithms. In Supercomputing 1994, pages 49-58, 1994.]]Google Scholar
- 4 M. Frigo. BenchFFT. http://www.fftw.org/benchfft/.]]Google Scholar
- 5 M. Frigo. A fast fourier transform compiler. In PLDI '99, pages 169-180, 1999.]] Google ScholarDigital Library
- 6 M. Frigo and S. G. Johnson. FFTW: An adaptive software architecture for the FFT. In ICASSP '98, volume 3, pages 1381-1384, 1998. http://www.fftw.org.]]Google ScholarCross Ref
- 7 M. T. H. Henrik V. Sorenson, C. Sidney Burrus. Fast Fourier Transform Database. PWS Publishing Company, Boston, 1995.]]Google Scholar
- 8 J. Johnson, R. Johnson, D. Padua, and J. Xiong. TPL: Tensor Product Language, 1999. http://www.ece.cmu.edu/~spiral/tpl.html.]]Google Scholar
- 9 J. R. Johnson and R. W. Johnson. Challenges of computing the fast Fourier transform. In Proc. Optimized Portable Application Libraries (OPAL) Workshop, A DARPA/NSF sponsored workshop in Kansas City, June. 2-3, 1997.]]Google Scholar
- 10 J. R. Johnson, R. W. Johnson, D. Rodriguez, and R. Tolimieri. A methodology for designing, modifying, and implementing Fourier transform algorithms on various architectures. Circuits, Systems, and Signal Processing, 9(4):449-500, 1990.]] Google ScholarDigital Library
- 11 J. R. Johnson and M. Puschel. In search of the optimal Walsh-Hadamard transform. In Proc. ICASSP 2000, 2000.]] Google ScholarDigital Library
- 12 T. Kisuki, P.M.W.Knijnenberg, M.F.P.O'Boyle, and H.A.G.Wijshoff. Iterative compilation in program optimization. In Proc. CPC2000, pages 35-44, 2000.]]Google Scholar
- 13 J. M. F. Moura, J. Johnson, R. W. Johnson, D. Padua, V. Prasanna, M. P.uschel, and M. M. Veloso. SPIRAL: Portable Library of Optimized Signal Processing Algorithms, 1998. http://www.ece.cmu.edu/~spiral.]]Google Scholar
- 14 K. R. Rao and P. Yip. Discrete Cosine Transform. Academic Press, 1990.]]Google ScholarDigital Library
- 15 R. Tolimieri, M. An, and C. Lu. Algorithms for discrete Fourier transforms and convolution. Springer, 2nd edition, 1997.]]Google Scholar
- 16 C. Van Loan. Computational Framework of the Fast Fourier Transform. Siam, 1992.]] Google ScholarDigital Library
- 17 R. Vuduc and J. Demmel. Code generators for automatic tuning of numerical kernels: Experiences with fftw. In ICFP 2000, 2000.]] Google ScholarDigital Library
- 18 R. C. Whaley and J. Dongarra. Automatically tuned linear algebra software (ATLAS), 1998. http://www.netlib.org/atlas/.]]Google Scholar
Index Terms
- SPL: a language and compiler for DSP algorithms
Recommendations
SPL: a language and compiler for DSP algorithms
PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementationWe discuss the design and implementation of a compiler that translates formulas representing signal processing transforms into efficient C or Fortran programs. The formulas are represented in a language that we call SPL, an acronym from Signal ...
Pipeline architecture for 8/spl times/8 discrete cosine transform
ICASSP '00: Proceedings of the Acoustics, Speech, and Signal Processing, 2000. on IEEE International Conference - Volume 06An array processor architecture for the 2-D discrete cosine transform (DCT) based on the row-column decomposition of the 2-D DCT. The utilized 1-D DCT architectures are derived by applying the principles used to construct pipelined fast Fourier ...
Searching for the Best FFT Formulas with the SPL Compiler
LCPC '00: Proceedings of the 13th International Workshop on Languages and Compilers for Parallel Computing-Revised PapersThis paper discuss an approach to implementing and optimizing fast signal transforms based on a domain-specific computer language, called SPL. SPL programs, which are essentially mathematical formulas, represent matrix factorizations, which provide fast ...
Comments