{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T14:42:56Z","timestamp":1769265776685,"version":"3.49.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,4,1]],"date-time":"2009-04-01T00:00:00Z","timestamp":1238544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["NBCH-1050009"],"award-info":[{"award-number":["NBCH-1050009"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["3.26E+12"],"award-info":[{"award-number":["3.26E+12"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p>This article presents a method for constructing hardware structures that perform a fixed permutation on streaming data. The method applies to permutations that can be represented as linear mappings on the bit-level representation of the data locations. This subclass includes many important permutations such as stride permutations (corner turn, perfect shuffle, etc.), the bit reversal, the Hadamard reordering, and the Gray code reordering.<\/jats:p>\n          <jats:p>The datapath for performing the streaming permutation consists of several independent banks of memory and two interconnection networks. These structures are built for a given streaming width (i.e., number of inputs and outputs per cycle) and operate at full throughput for this streaming width.<\/jats:p>\n          <jats:p>We provide an algorithm that completely specifies the datapath and control logic given the desired permutation and streaming width. Further, we provide lower bounds on the achievable cost of a solution and show that for an important subclass of permutations our solution is optimal.<\/jats:p>\n          <jats:p>We apply our algorithm to derive datapaths for several important permutations, including a detailed example that carefully illustrates each aspect of the design process. Lastly, we compare our permutation structures to those of J\u00e4rvinen et al. [2004], which are specialized for stride permutations.<\/jats:p>","DOI":"10.1145\/1502793.1502799","type":"journal-article","created":{"date-parts":[[2009,4,15]],"date-time":"2009-04-15T13:37:07Z","timestamp":1239802627000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["Permuting streaming data using RAMs"],"prefix":"10.1145","volume":"56","author":[{"given":"Markus","family":"P\u00fcschel","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter A.","family":"Milder","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James C.","family":"Hoe","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,4,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.752608"},{"key":"e_1_2_1_2_1","volume-title":"Applications of Walsh and Related Functions","author":"Beauchamp K. G.","unstructured":"Beauchamp , K. G. 1984. Applications of Walsh and Related Functions . Academic Press , Orlando, FL . Beauchamp, K. G. 1984. Applications of Walsh and Related Functions. Academic Press, Orlando, FL."},{"key":"e_1_2_1_3_1","volume-title":"Mathematical Theory of Connecting Networks and Telephone Traffic","author":"Benes V. E.","unstructured":"Benes , V. E. 1965. Mathematical Theory of Connecting Networks and Telephone Traffic . Academic Press , Orlando, FL . Benes, V. E. 1965. Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, Orlando, FL."},{"key":"e_1_2_1_4_1","volume-title":"Matrix Mathematics","author":"Bernstein D. S.","unstructured":"Bernstein , D. S. 2005. Matrix Mathematics . Princeton University Press , Princeton, NJ . Bernstein, D. S. 2005. Matrix Mathematics. Princeton University Press, Princeton, NJ."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.35835"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"B\u00fcrgisser P. Clausen M. and Shokrollahi M. A. 1997. Algebraic Complexity Theory. Springer-Verlag Berlin Germany.  B\u00fcrgisser P. Clausen M. and Shokrollahi M. A. 1997. Algebraic Complexity Theory. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/29.103090"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/82.392316"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1025114.1025191"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1976.1674637"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1975.224157"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.1676581"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391572"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of Design, Automation and Test in Europe.","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 Design, Automation and Test in Europe. Milder, P. A., Hoe, J. C., and P\u00fcschel, M. 2009. Automatic generation of streaming datapaths for arbitrary fixed permutations. In Proceedings of Design, Automation and Test in Europe."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065579.1065703"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/82.160168"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1980.1675553"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1977.1674863"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2007.907919"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 2003 International Symposium on Circuits and Systems.","author":"Takala J. H.","unstructured":"Takala , J. H. , J\u00e4rvinen , T. S. , and Sorokin , H. T . 2003. Conflict-free parallel memory access scheme for FFT processors . In Proceedings of the 2003 International Symposium on Circuits and Systems. Takala, J. H., J\u00e4rvinen, T. S., and Sorokin, H. T. 2003. Conflict-free parallel memory access scheme for FFT processors. In Proceedings of the 2003 International Symposium on Circuits and Systems."},{"key":"e_1_2_1_21_1","volume-title":"Computational Frameworks for the Fast Fourier Transform","author":"Van Loan C.","unstructured":"Van Loan , C. 1992. Computational Frameworks for the Fast Fourier Transform . SIAM , Philadelphia, PA . Van Loan, C. 1992. Computational Frameworks for the Fast Fourier Transform. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1967.1054010"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321439.321449"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1502793.1502799","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1502793.1502799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:37Z","timestamp":1750253377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1502793.1502799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1145\/1502793.1502799"],"URL":"https:\/\/doi.org\/10.1145\/1502793.1502799","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4]]},"assertion":[{"value":"2008-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}