{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:29:30Z","timestamp":1774369770451,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001868","name":"National Science Council Taiwan","doi-asserted-by":"publisher","award":["NSC 91-2218-E-011-002"],"award-info":[{"award-number":["NSC 91-2218-E-011-002"]}],"id":[{"id":"10.13039\/501100001868","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":[[2009,1]]},"abstract":"<jats:p>\n            Prefix computation is used in various areas and is considered as a primitive operation. Parallel prefix circuits are parallel prefix algorithms on the combinational circuit model. The depth of a prefix circuit is a measure of its processing time; smaller depth implies faster computation. The size of a prefix circuit is the number of operation nodes in it. Smaller size implies less power consumption, less VLSI area, and less cost. A prefix circuit with\n            <jats:italic>n<\/jats:italic>\n            inputs is depth-size optimal if its depth plus size equals 2\n            <jats:italic>n<\/jats:italic>\n            \u2212 2. A circuit with a smaller fan-out is in general faster and occupies less VLSI area. To be of practical use, the depth and fan-out of a prefix circuit should be small. In this paper, a family of depth-size optimal, parallel prefix circuits with fan-out 2 is presented. This family of prefix circuits is easier to construct and more amenable to automatic synthesis than two other families of the same type, although the three families have the same minimum depth among all depth-size optimal prefix circuits with fan-out 2. The balanced structure of the new family is also a merit.\n          <\/jats:p>","DOI":"10.1145\/1455229.1455244","type":"journal-article","created":{"date-parts":[[2009,1,29]],"date-time":"2009-01-29T13:48:36Z","timestamp":1233236916000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Straightforward construction of depth-size optimal, parallel prefix circuits with fan-out 2"],"prefix":"10.1145","volume":"14","author":[{"given":"Yen-Chun","family":"Lin","sequence":"first","affiliation":[{"name":"National Taiwan University of Science and Technology, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Li-Ling","family":"Hung","sequence":"additional","affiliation":[{"name":"National Taiwan University of Science and Technology, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,1,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Parallel Computation: Models and Methods","author":"Akl S. G.","year":"1997","unstructured":"Akl , S. G. 1997 . Parallel Computation: Models and Methods . Prentice-Hall , Upper Saddle River, NJ. Akl, S. G. 1997. Parallel Computation: Models and Methods. Prentice-Hall, Upper Saddle River, NJ."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-7315(03)00010-8"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676655"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.42122"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675982"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00127876"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:SUPE.0000032783.66123.63"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.60"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808738"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2000.1678"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27764-4_11"},{"key":"e_1_2_1_12_1","first-page":"229","article-title":"Parallel prefix algorithms on the multicomputer","volume":"3","author":"Hung L.-L.","year":"2008","unstructured":"Hung , L.-L. and Lin , Y.-C. 2008 . Parallel prefix algorithms on the multicomputer . WSEAS Trans. Comput. Resear. 3 , 229 -- 239 . Hung, L.-L. and Lin, Y.-C. 2008. Parallel prefix algorithms on the multicomputer. WSEAS Trans. Comput. Resear. 3, 229--239.","journal-title":"WSEAS Trans. Comput. Resear."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.6312202"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Lakshmivarahan S. and Dhall S. K. 1994. Parallel Computing Using the Prefix Problem. Oxford University Press Oxford UK.   Lakshmivarahan S. and Dhall S. K. 1994. Parallel Computing Using the Prefix Problem. Oxford University Press Oxford UK.","DOI":"10.1093\/oso\/9780195088496.001.0001"},{"key":"e_1_2_1_16_1","first-page":"58","article-title":"On a new class of optimal parallel prefix circuits with (size + depth) &equals; 2 n &minus; 2 and &lceillog n &rceil;&rceil; \u2264 depth \u2264 (2 &lceil;log n&rceil; &minus; 3). In Proceedings of the International Conference on Parallel Processing","author":"Lakshmivarahan S.","year":"1987","unstructured":"Lakshmivarahan , S. , Yang , C. M. , and Dhall , S. K. 1987 . On a new class of optimal parallel prefix circuits with (size + depth) &equals; 2 n &minus; 2 and &lceillog n &rceil;&rceil; \u2264 depth \u2264 (2 &lceil;log n&rceil; &minus; 3). In Proceedings of the International Conference on Parallel Processing , St. Charles , IL , 58 -- 65 . Lakshmivarahan, S., Yang, C. M., and Dhall, S. K. 1987. On a new class of optimal parallel prefix circuits with (size + depth) &equals; 2 n &minus; 2 and &lceillog n &rceil;&rceil; \u2264 depth \u2264 (2 &lceil;log n&rceil; &minus; 3). In Proceedings of the International Conference on Parallel Processing, St. Charles, IL, 58--65.","journal-title":"St. Charles"},{"key":"e_1_2_1_17_1","volume-title":"Trees, Hypercubes. Morgan Kaufmann","author":"Leighton F. T.","unstructured":"Leighton , F. T. 1992. Introduction to Parallel Algorithms and Architectures: Arrays , Trees, Hypercubes. Morgan Kaufmann , San Mateo, CA . Leighton, F. T. 1992. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo, CA."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.877941"},{"key":"e_1_2_1_19_1","first-page":"33","article-title":"Optimal parallel prefix circuits with fan-out 2 and corresponding parallel algorithms","volume":"7","author":"Lin Y.-C.","year":"1999","unstructured":"Lin , Y.-C. 1999 . Optimal parallel prefix circuits with fan-out 2 and corresponding parallel algorithms . Neural, Parall. Scientifi. Computat. 7 , 33 -- 42 . Lin, Y.-C. 1999. Optimal parallel prefix circuits with fan-out 2 and corresponding parallel algorithms. Neural, Parall. Scientifi. Computat. 7, 33--42.","journal-title":"Neural, Parall. Scientifi. Computat."},{"key":"e_1_2_1_20_1","first-page":"3060","article-title":"A family of computation-efficient parallel prefix algorithms. WSEAS Transsa","volume":"5","author":"Lin Y.-C.","year":"2006","unstructured":"Lin , Y.-C. 2006 . A family of computation-efficient parallel prefix algorithms. WSEAS Transsa . Comput. 5 , 3060 -- 3066 . Lin, Y.-C. 2006. A family of computation-efficient parallel prefix algorithms. WSEAS Transsa. Comput. 5, 3060--3066.","journal-title":"Comput."},{"key":"e_1_2_1_21_1","first-page":"221","article-title":"Z4: A new depth-size optimal parallel prefix circuit with small depth","volume":"11","author":"Lin Y.-C.","year":"2003","unstructured":"Lin , Y.-C. and Chen , J.-N. 2003 . Z4: A new depth-size optimal parallel prefix circuit with small depth . Neural, Paral. Scient. Computat. 11 , 221 -- 235 . Lin, Y.-C. and Chen, J.-N. 2003. Z4: A new depth-size optimal parallel prefix circuit with small depth. Neural, Paral. Scient. Computat. 11, 221--235.","journal-title":"Neural, Paral. Scient. Computat."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2003.09.004"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022084814175"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2008.12.003"},{"key":"e_1_2_1_25_1","first-page":"41","article-title":"Efficient parallel prefix algorithms on multicomputers","volume":"16","author":"Lin Y.-C.","year":"2000","unstructured":"Lin , Y.-C. and Lin , C. M. 2000 . Efficient parallel prefix algorithms on multicomputers . J. Inform. Sci. Engin. 16 , 41 -- 64 . Lin, Y.-C. and Lin, C. M. 2000. Efficient parallel prefix algorithms on multicomputers. J. Inform. Sci. Engin. 16, 41--64.","journal-title":"J. Inform. Sci. Engin."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00058-7"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008147229964"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2005.05.017"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00087-3"},{"key":"e_1_2_1_30_1","first-page":"75","article-title":"Optimal parallel prefix on the postal model","volume":"19","author":"Lin Y.-C.","year":"2003","unstructured":"Lin , Y.-C. and Yeh , C.-S. 2003 . Optimal parallel prefix on the postal model . J. Informa. Sci. Engin. 19 , 75 -- 83 . Lin, Y.-C. and Yeh, C.-S. 2003. Optimal parallel prefix on the postal model. J. Informa. Sci. Engin. 19, 75--83.","journal-title":"J. Informa. Sci. Engin."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.736437"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2000.1698"},{"key":"e_1_2_1_33_1","unstructured":"Sheeran M. and Parberry I. 2006. A new approach to the design of optimal parallel prefix circuits Tech. rep. 2006:1 Department of Computer Science and Engineering Chalmers University of Technology Goteborg Sweden.  Sheeran M. and Parberry I. 2006. A new approach to the design of optimal parallel prefix circuits Tech. rep. 2006:1 Department of Computer Science and Engineering Chalmers University of Technology Goteborg Sweden."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90003-9"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.544482"},{"key":"e_1_2_1_36_1","unstructured":"Weste N. H. E. and Eshraghian K. 1993. Principles of CMOS VLSI Design: A System Perspective 2nd Ed. Addison-Wesley Reading MA.   Weste N. H. E. and Eshraghian K. 1993. Principles of CMOS VLSI Design: A System Perspective 2nd Ed. Addison-Wesley Reading MA."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142155.1142162"},{"key":"e_1_2_1_38_1","volume-title":"Binary Adder Architectures for Cell-Based VLSI and Their Synthesis","author":"Zimmermann R.","unstructured":"Zimmermann , R. , 1997. Binary Adder Architectures for Cell-Based VLSI and Their Synthesis . Zurich : Swiss Federal Institute of Technology (ETH) . Zimmermann, R., 1997. Binary Adder Architectures for Cell-Based VLSI and Their Synthesis. Zurich: Swiss Federal Institute of Technology (ETH)."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1455229.1455244","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1455229.1455244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:00Z","timestamp":1750253400000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1455229.1455244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1145\/1455229.1455244"],"URL":"https:\/\/doi.org\/10.1145\/1455229.1455244","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}