SPIRAL is a generator for libraries of fast software implementations of linear signal processing transforms. These libraries are adapted to the computing platform and can be re-optimized as the hardware is upgraded or replaced. This paper describes the main components of SPIRAL: the mathematical framework that concisely describes signal transforms and their fast algorithms; the formula generator that captures at the algorithmic level the degrees of freedom in expressing a particular signal processing transform; the formula translator that encapsulates the compilation degrees of freedom when translating a specific algorithm into an actual code implementation; and, finally, an intelligent search engine that finds within the large space of alternative formulas and implementations the “best” match to the given computing platform. We present empirical data that demonstrate the high performance of SPIRAL generated code.
Get full access to this article
View all access options for this article.
References
1.
Auslander, L., Johnson, J., and Johnson, R. W. 1996. Automatic implementation of FFT algorithms . Technical Report DUMCS-96-01, Deparrtment of Mathematics and Computer Science, Drexel University, Philadelphia, PA. Presented at the DARPA ACMP PI meeting.
2.
Bilmes, J., Asanovi\#263;, K., Chin, C. W., and Demmel, J. 1997. Optimizing matrix multiply using PHiPAC: a portable, highperformance, ANSI C coding methodology . In Proceedings of Supercomputing San Jose, CA, ACM SIGARC. See http://www.icsi.berkeley.edu/bilmes/phipac.
3.
Cooley, J. W. and Tukey, J. W. 1965. An algorithm for the machine calculation of complex Fourier series . Mathematics of Computation19: 297–301 .
4.
Egner, S. 1997. Zur algorithmischen Zerlegungstheorie linearer Transformationen mit symmetrie. Ph.D. Thesis, Institut für Informatik, Univ. Karlsruhe, Germany.
Elliott, D. F. and Rao, K. R. 1982. Fast Transforms: Algorithms, Analyses, Applications, Academic Press, New York .
7.
Franchetti, F., Karner, H., Kral, S., and Ueberhuber, C. W. 2001. Architecture independent short vector FFTs . In Proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Salt Lake City, UT, Vol. 2, pp. 1109–1112 .
8.
Franchetti, F. and Püschel, M. 2002. A SIMD vectorizing compiler for digital signal processing algorithms . In Proceedings of International Parallel and Distributed Processing Symposium (IPDPS), Fort Lauderdale, FC, pp. 20–26 .
9.
Franchetti, F. and Püschel, M. 2003. Short-vector code generation for the discrete Fourier transform . In Proceedings of International Parallel and Distributed Processing Symposium (IPDPS), Nice, France, pp. 58–67 .
10.
Frigo, M. 1999. A fast Fourier transform compiler . In Proceedings of ACM SIGPLAN’99 Conference on Programming Language Design and Implementation (PLDI), Atlanta, GA, pp. 169–180 .
11.
Frigo, M. and Johnson, S. G. 1998. FFTW: an adaptive software architecture for the FFT . In Proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Seattle, WA, Vol. 3, pp. 1381–1384 . See http://www.fftw.org.
Gatlin, K. S. and Carter, L. 1999. Architecture-cognizant divide and conquer algorithms . In Proceedings of Supercomputing Portland, OR.
14.
Gacbi\#263;, A., Püschel, M., and Moura, J. M. F. 2003. Fast automatic implementations of FIR filters . In Proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Hong Kong, Vol. 2, pp. 541–544 .
15.
Goldberg, D. E. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, MA .
16.
Haentjens, G. 2000. An investigation of recursive FFT implementations. Master’s thesis, ECE Department, Carnegie Mellon University.
17.
Im, E.-J. and Yelick, K. 2001. Optimizing sparse matrix computations for register reuse in SPARSITY . In Proceedings of International Conference on Computational Science (ICCS), San Francisco, CA, pp. 127–136 .
18.
Johnson, H. W. and Burrus, C. S. 1983. The design of optimal DFT algorithms using dynamic programming . IEEE Transactions on Acoustics, Speech, and Signal Processing31: 378–387 .
19.
Johnson, J., Johnson, R. W., Rodriguez, D., and Tolimieri, R. 1990. A methodology for designing, modifying, and implementing Fourier transform algorithms on various architectures . IEEE Transactions on Circuits and Systems9(4): 449–500 .
20.
Johnson, J. and Püschel, M. 2000. Search for the optimal Walsh–Hadamard transform . In Proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Istanbul, Turkey, Vol. IV, pp. 3347–3350 .
21.
Mirkovi&263;, D. and Johnsson, S. L. 2001. Automatic performance tuning in the UHFFT library . In Proceedings of International-Conference on Computational Science (ICCS), San Francisco, CA, Lecture Notes in Computer Science, Vol. 2073, Springer-Verlag, Berlin, pp. 71–80 .
22.
Moura, J. M. F., Johnson, J., Johnson, R. W., Padua, D., Prasanna, V., Püschel, M., and Veloso, M. M. 1998. SPIRAL: Portable Library of Optimized Signal Processing Algorithms. See http://www.spiral.net.
23.
Moura, J. M. F. and Püschel, M. 2003. SPIRAL: an overview . In Proceedings of the Workshop on Optimizations for DSP and Embedded Systems, held in conjunction with CGO San Francisco, CA.
24.
Park, N., Kang, D., Bondalapati, K., and Prasanna, V. K. 2000. Dynamic data layouts for cache-conscious factorization of DFT . In Proceedings of International Parallel and Distributed Processing Symposium (IPDPS), Cancun, Mexico, pp. 693–701 .
25.
Park, N. and Prasanna, V. K. 2001. Cache conscious Walsh– Hadamard transform . In Proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP), San Francisco, CA, Vol. 2, pp. 1205–1208 .
26.
Rao, K. R. and Hwang, J. J. 1996. Techniques and Standards for Image, Video and Audio Coding, Prentice-Hall PTR, Englewood Cliffs, NJ .
27.
Révész, G. E. 1983. Introduction to Formal Languages, McGraw-Hill, New York .
28.
Sepiashvili, D. 2000. Performance models and search methods for optimal FFT implementations. Master’s thesis, ECE Department, Carnegie Mellon University.
29.
Singer, B. and Veloso, M. M. 2001. Stochastic search for signal processing algorithm optimization . In Proceedings of Supercomputing Denver, CO.
30.
Singer, B. and Veloso, M. M. 2002. Automating the modeling and optimization of the performance of signal transforms . IEEE Transactions on Signal Processing50(8): 2003–2014 .
31.
Tolimieri, R., An, M., and Lu, C. 1997. Algorithms for Discrete Fourier Transforms and Convolution, 2nd edition, Springer-Verlag, Berlin .
32.
Van Loan, C. 1992. Computational Framework of the Fast Fourier Transform, SIAM, Philadelphia .
33.
Vetterli, M. and Nussbaumer, H. J. 1984. Simple FFT and DCT algorithms with reduced number of operations . Signal Processing6: 267–278 .
34.
Wang, Z. 1984. Fast algorithms for the discrete W transform and for the discrete Fourier transform . IEEE Transactions on Acoustics, Speech, and Signal Processing32(4): 803–816 .
35.
Wang, Z. and Hunt, B. R. 1985. The discrete W transform . Applied Mathematics and Computation16: 19–48 .
36.
Whaley, R. C. and Dongarra, J. 1998. Automatically tuned linear algebra software (ATLAS) . In Proceedings of Supercomputing Orlando, FL, http://math-atlas.sourceforge.net/.
37.
Xiong, J. 2001. Automatic optimization of DSP algorithms. Ph.D. Thesis, Computer Science, University of Illinois at Urbana-Champaign. Also as Technical Report UIUCDCSR-2001-224, University of Illinois.
38.
Xiong, J., Johnson, J., Johnson, R., and Padua, D. 2001. SPL: a language and compiler for DSP algorithms . In Proceedings of PLDI, Snowbird, UT, pp. 298–308 .
