{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T16:29:42Z","timestamp":1649003382676},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["NBCH-1050009"]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["3.26E+12"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,4]]},"abstract":"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 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 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 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","source":"Crossref","is-referenced-by-count":41,"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"}]},{"given":"Peter A.","family":"Milder","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania"}]},{"given":"James C.","family":"Hoe","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.752608"},{"key":"e_1_2_1_2_1","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","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","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."},{"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."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","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.","DOI":"10.1137\/1.9781611970999"},{"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\/pdf\/10.1145\/1502793.1502799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T14:29:22Z","timestamp":1613744962000},"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":"http:\/\/dx.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":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2009,4]]}}}