{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T22:57:00Z","timestamp":1777676220284,"version":"3.51.4"},"reference-count":38,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2004,2,1]],"date-time":"2004-02-01T00:00:00Z","timestamp":1075593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2004,2]]},"abstract":"<jats:p>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 \u201cbest\u201d match to the given computing platform. We present empirical data that demonstrate the high performance of SPIRAL generated code.<\/jats:p>","DOI":"10.1177\/1094342004041291","type":"journal-article","created":{"date-parts":[[2004,4,21]],"date-time":"2004-04-21T21:27:18Z","timestamp":1082582838000},"page":"21-45","source":"Crossref","is-referenced-by-count":113,"title":["Spiral: A Generator for Platform-Adapted Libraries of Signal Processing Alogorithms"],"prefix":"10.1177","volume":"18","author":[{"given":"Markus","family":"P\u00fcschel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 M. F.","family":"Moura","sequence":"additional","affiliation":[{"name":"DEPARTMENT OF ELECTRICAL AND COMPUTER ENGINEERING CARNEGIE MELLON                        UNIVERSITY, PITTSBURGH, PA 15213-3890, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bryan","family":"Singer","sequence":"additional","affiliation":[{"name":"716 QUIET POND CT., ODENTON, MD 21113, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianxin","family":"Xiong","sequence":"additional","affiliation":[{"name":"33315 DIGITAL COMPUTER LABORATORY, 1304 W SPRINGFIELD AVE, URBANA, IL                        61801, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeremy","family":"Johnson","sequence":"additional","affiliation":[{"name":"DEPARTMENT OF COMPUTER SCIENCE, DREXEL UNIVERSITY PHILADELPHIA, PA                        19104-2875, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Padua","sequence":"additional","affiliation":[{"name":"DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITY OF ILLINOIS AT                        URBANA-CHAMPAIGN 3318 DIGITAL COMPUTER LABORATORY, URBANA, IL 61801, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuela","family":"Veloso","sequence":"additional","affiliation":[{"name":"SCHOOL OF COMPUTER SCIENCE, CARNEGIE MELLON UNIVERSITY, PITTSBURGH, PA                        15213-3890, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert W.","family":"Johnson","sequence":"additional","affiliation":[{"name":"3324 21ST AVE. SOUTH ST. CLOUD, MN 56301, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2004,2,1]]},"reference":[{"key":"atypb1","unstructured":"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."},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/263580.263662"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"atypb4","unstructured":"Egner, S. 1997. Zur algorithmischen Zerlegungstheorie linearer Transformationen mit symmetrie. Ph.D. Thesis, Institut f\u00fcr Informatik, Univ. Karlsruhe, Germany."},{"key":"atypb5","unstructured":"Egner, S. and P\u00fcschel, M. 1998. AREP \u2013 Constructive Representation Theory and Fast Signal Transforms, GAP share package. See http:\/\/www.ece.cmu.edu\/smart\/arep\/arep.html."},{"key":"atypb6","unstructured":"Elliott, D. F. and Rao, K. R. 1982. Fast Transforms: Algorithms, Analyses, Applications, Academic Press, New York ."},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"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\u20131112 .","DOI":"10.1109\/ICASSP.2001.941115"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"Franchetti, F. and P\u00fcschel, 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\u201326 .","DOI":"10.1109\/IPDPS.2002.1015494"},{"key":"atypb9","unstructured":"Franchetti, F. and P\u00fcschel, 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\u201367 ."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"Frigo, M. 1999. A fast Fourier transform compiler . In Proceedings of ACM SIGPLAN\u201999 Conference on Programming Language Design and Implementation (PLDI), Atlanta, GA, pp. 169\u2013180 .","DOI":"10.1145\/301631.301661"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"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\u20131384 . See http:\/\/www.fftw.org.","DOI":"10.1109\/ICASSP.1998.681704"},{"key":"atypb12","unstructured":"The GAP Team, University of St. Andrews, Scotland. 1997. GAP \u2013 Groups, Algorithms, and Programming. See http:\/\/www-gap.dcs.st-and.ac.uk\/gap\/."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"Gatlin, K. S. and Carter, L. 1999. Architecture-cognizant divide and conquer algorithms . In Proceedings of Supercomputing Portland, OR.","DOI":"10.1145\/331532.331557"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"Gacbi\\#263; A., P\u00fcschel, 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\u2013544 .","DOI":"10.1109\/ICASSP.2003.1202423"},{"key":"atypb15","unstructured":"Goldberg, D. E. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, MA ."},{"key":"atypb16","unstructured":"Haentjens, G. 2000. An investigation of recursive FFT implementations. Master\u2019s thesis, ECE Department, Carnegie Mellon University."},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"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\u2013136 .","DOI":"10.1007\/3-540-45545-0_22"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1983.1164071"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"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 Systems 9(4): 449\u2013500 .","DOI":"10.1007\/BF01189337"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"Johnson, J. and P\u00fcschel, M. 2000. Search for the optimal Walsh\u2013Hadamard transform . In Proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Istanbul, Turkey, Vol. IV, pp. 3347\u20133350 .","DOI":"10.1109\/ICASSP.2000.860117"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"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\u201380 .","DOI":"10.1007\/3-540-45545-0_17"},{"key":"atypb22","unstructured":"Moura, J. M. F., Johnson, J., Johnson, R. W., Padua, D., Prasanna, V., P\u00fcschel, M., and Veloso, M. M. 1998. SPIRAL: Portable Library of Optimized Signal Processing Algorithms. See http:\/\/www.spiral.net."},{"key":"atypb23","unstructured":"Moura, J. M. F. and P\u00fcschel, 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."},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"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\u2013701 .","DOI":"10.1109\/IPDPS.2000.846054"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"Park, N. and Prasanna, V. K. 2001. Cache conscious Walsh\u2013 Hadamard transform . In Proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP), San Francisco, CA, Vol. 2, pp. 1205\u20131208 .","DOI":"10.1109\/ICASSP.2001.941140"},{"key":"atypb26","unstructured":"Rao, K. R. and Hwang, J. J. 1996. Techniques and Standards for Image, Video and Audio Coding, Prentice-Hall PTR, Englewood Cliffs, NJ ."},{"key":"atypb27","unstructured":"R\u00e9v\u00e9sz, G. E. 1983. Introduction to Formal Languages, McGraw-Hill, New York ."},{"key":"atypb28","unstructured":"Sepiashvili, D. 2000. Performance models and search methods for optimal FFT implementations. Master\u2019s thesis, ECE Department, Carnegie Mellon University."},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"Singer, B. and Veloso, M. M. 2001. Stochastic search for signal processing algorithm optimization . In Proceedings of Supercomputing Denver, CO.","DOI":"10.1145\/582034.582056"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2002.800394"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"Tolimieri, R., An, M., and Lu, C. 1997. Algorithms for Discrete Fourier Transforms and Convolution, 2nd edition, Springer-Verlag, Berlin .","DOI":"10.1007\/978-1-4757-2767-8"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"Van Loan, C. 1992. Computational Framework of the Fast Fourier Transform, SIAM, Philadelphia .","DOI":"10.1137\/1.9781611970999"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1684(84)90059-8"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1984.1164399"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(85)90008-6"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"Whaley, R. C. and Dongarra, J. 1998. Automatically tuned linear algebra software (ATLAS) . In Proceedings of Supercomputing Orlando, FL, http:\/\/math-atlas.sourceforge.net\/.","DOI":"10.1109\/SC.1998.10004"},{"key":"atypb37","unstructured":"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."},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"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\u2013308 .","DOI":"10.1145\/381694.378860"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342004041291","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342004041291","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:18:02Z","timestamp":1777450682000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342004041291"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,2]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2004,2]]}},"alternative-id":["10.1177\/1094342004041291"],"URL":"https:\/\/doi.org\/10.1177\/1094342004041291","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"value":"1094-3420","type":"print"},{"value":"1741-2846","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,2]]}}}