{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:12:43Z","timestamp":1774631563953,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,4,1]],"date-time":"2012-04-01T00:00:00Z","timestamp":1333238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000141110112102191808"],"award-info":[{"award-number":["N000141110112102191808"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF0710416"],"award-info":[{"award-number":["W911NF0710416"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["702386"],"award-info":[{"award-number":["702386"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2012,4]]},"abstract":"<jats:p>Linear signal transforms such as the discrete Fourier transform (DFT) are very widely used in digital signal processing and other domains. Due to high performance or efficiency requirements, these transforms are often implemented in hardware. This implementation is challenging due to the large number of algorithmic options (e.g., fast Fourier transform algorithms or FFTs), the variety of ways that a fixed algorithm can be mapped to a sequential datapath, and the design of the components of this datapath. The best choices depend heavily on the resource budget and the performance goals of the target application. Thus, it is difficult for a designer to determine which set of options will best meet a given set of requirements.<\/jats:p>\n          <jats:p>In this article we introduce the Spiral hardware generation framework and system for linear transforms. The system takes a problem specification as input as well as directives that define characteristics of the desired datapath. Using a mathematical language to represent and explore transform algorithms and datapath characteristics, the system automatically generates an algorithm, maps it to a datapath, and outputs a synthesizable register transfer level Verilog description suitable for FPGA or ASIC implementation. The quality of the generated designs rivals the best available handwritten IP cores.<\/jats:p>","DOI":"10.1145\/2159542.2159547","type":"journal-article","created":{"date-parts":[[2012,4,24]],"date-time":"2012-04-24T18:41:10Z","timestamp":1335292870000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":109,"title":["Computer Generation of Hardware for Linear Digital Signal Processing Transforms"],"prefix":"10.1145","volume":"17","author":[{"given":"Peter","family":"Milder","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Franz","family":"Franchetti","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James C.","family":"Hoe","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"P\u00fcschel","sequence":"additional","affiliation":[{"name":"ETH Zurich"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"4DSP LLC. 2007. 4DSP floating point fast Fourier transform V2.6. 4DSP LLC. 4DSP LLC . 2007. 4DSP floating point fast Fourier transform V2.6. 4DSP LLC."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.752608"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAU.1970.1162132"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1976.1162854"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2009.2016276"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MEMCOD.2006.1695901"},{"key":"e_1_2_1_8_1","volume-title":"Rewriting. In Handbook of Automated Reasoning","volume":"1","author":"Dershowitz N.","unstructured":"Dershowitz , N. and Plaisted , D. A . 2001 . Rewriting. In Handbook of Automated Reasoning , Vol. 1 , A. Robinson and A. Voronkov Eds., Elsevier, 535--610. Dershowitz, N. and Plaisted, D. A. 2001. Rewriting. In Handbook of Automated Reasoning, Vol. 1, A. Robinson and A. Voronkov Eds., Elsevier, 535--610."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1188455.1188575"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1761728.1761759"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/82.392316"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the International Parallel Processing Symposium. 766--770","author":"He S.","unstructured":"He , S. and Torkelson , M . 1996. A new approach to pipeline FFT processor . In Proceedings of the International Parallel Processing Symposium. 766--770 . He, S. and Torkelson, M. 1996. A new approach to pipeline FFT processor. In Proceedings of the International Parallel Processing Symposium. 766--770."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors. 51--71","author":"J\u00e4rvinen T. S.","unstructured":"J\u00e4rvinen , T. S. , Salmela , P. , Sorokin , H. , and Takala , J. H . 2004. Stride permutation networks for array processors . In Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors. 51--71 . J\u00e4rvinen, T. S., Salmela, P., Sorokin, H., and Takala, J. H. 2004. Stride permutation networks for array processors. In Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors. 51--71."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189337"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Conference on Acoustics, Speech, and Signal Processing. 1413--1416","author":"Kee H.","unstructured":"Kee , H. , Petersen , N. , Kornerup , J. , and Bhattacharyya , S. S . 2008. Systematic generation of FPGA-based FFT implementations . In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing. 1413--1416 . Kee, H., Petersen, N., Kornerup, J., and Bhattacharyya, S. S. 2008. Systematic generation of FPGA-based FFT implementations. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing. 1413--1416."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 13th IEEE ASIC\/SOC Conference. 182--186","author":"Kumhom P.","unstructured":"Kumhom , P. , Johnson , J. , and Nagvajara , P . 2000. Design, optimization, and implementation of a universal FFT processor . In Proceedings of the 13th IEEE ASIC\/SOC Conference. 182--186 . Kumhom, P., Johnson, J., and Nagvajara, P. 2000. Design, optimization, and implementation of a universal FFT processor. In Proceedings of the 13th IEEE ASIC\/SOC Conference. 182--186."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1117201.1117232"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391572"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe. 1118--1123","author":"Milder P. A.","unstructured":"Milder , P. A. , Hoe , J. C. , and P\u00fcschel , M . 2009. Automatic generation of streaming datapaths for arbitrary fixed permutations . In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe. 1118--1123 . Milder, P. A., Hoe, J. C., and P\u00fcschel, M. 2009. Automatic generation of streaming datapaths for arbitrary fixed permutations. In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe. 1118--1123."},{"key":"e_1_2_1_21_1","unstructured":"Muralimanohar N. Balasubramonian R. and Jouppi N. P. 2009. CACTI 6.0: A tool to model large caches. Tech. rep. HPL-2009-85 Hewlett-Packard Laboratories. Muralimanohar N. Balasubramonian R. and Jouppi N. P. 2009. CACTI 6.0: A tool to model large caches. Tech. rep. HPL-2009-85 Hewlett-Packard Laboratories."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2005.05.014"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321450.321457"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840306"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502799"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the IEEE Symposium on VLSI. 229--232","author":"Sukhsawas S.","unstructured":"Sukhsawas , S. and Benkrid , K . 2004. A high-level implementation of a high performance pipeline FFT on Virtex-E FPGAs . In Proceedings of the IEEE Symposium on VLSI. 229--232 . Sukhsawas, S. and Benkrid, K. 2004. A high-level implementation of a high performance pipeline FFT on Virtex-E FPGAs. In Proceedings of the IEEE Symposium on VLSI. 229--232."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.845951"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Van Loan C. 1992. Computational Frameworks for the Fast Fourier Transform. SIAM. Van Loan C. 1992. Computational Frameworks for the Fast Fourier Transform . SIAM.","DOI":"10.1137\/1.9781611970999"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2008.2006152"},{"key":"e_1_2_1_30_1","unstructured":"Xilinx Inc. 2010. Xilinx LogiCore IP fast Fourier transform v7.1. Xilinx Inc. Xilinx Inc. 2010. Xilinx LogiCore IP fast Fourier transform v7.1. Xilinx Inc."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378860"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.113082"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2159542.2159547","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2159542.2159547","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:58Z","timestamp":1750244398000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2159542.2159547"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.1145\/2159542.2159547"],"URL":"https:\/\/doi.org\/10.1145\/2159542.2159547","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4]]},"assertion":[{"value":"2011-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}