{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:16Z","timestamp":1750307716005,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,7,1]],"date-time":"2009-07-01T00:00:00Z","timestamp":1246406400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["702617"],"award-info":[{"award-number":["702617"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["643902"],"award-info":[{"award-number":["643902"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2009,7]]},"abstract":"<jats:p>Scan chains are widely used to improve the testability of integrated circuit (IC) designs and to facilitate fault diagnosis. For traditional 2D IC design, a number of design techniques have been proposed in the literature for scan-chain routing and scan-cell partitioning. However, these techniques are not effective for three-dimensional (3D) technologies, which have recently emerged as a promising means to continue technology scaling. In this article, we propose two techniques for designing scan chains in 3D ICs, with given constraints on the number of through-silicon-vias (TSVs). The first technique is based on a genetic algorithm (GA), and it addresses the ordering of cells in a single scan chain. The second optimization technique is based on integer linear programming (ILP); it addresses single-scan-chain ordering as well as the partitioning of scan flip-flops into multiple scan chains. We compare these two methods by conducting experiments on a set of ISCAS'89 benchmark circuits. The first conclusion obtained from the results is that 3D scan-chain optimization achieves significant wire-length reduction compared to 2D counterparts. The second conclusion is that the ILP-based technique provides lower bounds on the scan-chain interconnect length for 3D ICs, and it offers considerable reduction in wire-length compared to the GA-based heuristic method.<\/jats:p>","DOI":"10.1145\/1543438.1543442","type":"journal-article","created":{"date-parts":[[2009,7,15]],"date-time":"2009-07-15T13:51:27Z","timestamp":1247665887000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Scan-chain design and optimization for three-dimensional integrated circuits"],"prefix":"10.1145","volume":"5","author":[{"given":"Xiaoxia","family":"Wu","sequence":"first","affiliation":[{"name":"Pennsylvania State University, University Park, PA"}]},{"given":"Paul","family":"Falkenstern","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, University Park, PA"}]},{"given":"Krishnendu","family":"Chakrabarty","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC"}]},{"given":"Yuan","family":"Xie","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, University Park, PA"}]}],"member":"320","published-online":{"date-parts":[[2009,7,16]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aarts E. and Korst J. 1989. Simulated Annealing and Boltzmann Machines. Wiley Chichester U.K.   Aarts E. and Korst J. 1989. Simulated Annealing and Boltzmann Machines. Wiley Chichester U.K."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDT.2005.150"},{"volume-title":"Proceedings of Midwest Symposium on Circuits and Systems. 301--304","author":"Arora R.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","unstructured":"Bertsimas D. and Tsitsiklis J. 1997. Introduction to Linear Optimization. Athena Scientific.   Bertsimas D. and Tsitsiklis J. 1997. Introduction to Linear Optimization. Athena Scientific."},{"volume-title":"Proceedings of the IEEE International Conference on Computer Design. 316--318","author":"Black B.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems.","volume":"3","author":"Brglez F.","year":"1929"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2004.1382591"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1119772.1119783"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDT.2005.136"},{"key":"e_1_2_1_10_1","unstructured":"Dick R. P. 2002. Multi-objective synthesis of low-power real-time distributed embedded systems. Ph.D. thesis Princeton University.  Dick R. P. 2002. Multi-objective synthesis of low-power real-time distributed embedded systems. Ph.D. thesis Princeton University."},{"key":"e_1_2_1_11_1","unstructured":"Freuer M. and Koo C. 1983. Method for rechaining shift register latches which contain more than one physical book. IBM Tech. Disclo. Bull. 25. 4818--4820.  Freuer M. and Koo C. 1983. Method for rechaining shift register latches which contain more than one physical book. IBM Tech. Disclo. Bull. 25. 4818--4820."},{"key":"e_1_2_1_12_1","unstructured":"Gary M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman.   Gary M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman."},{"volume-title":"Proceedings of the International Symposium on Defect and Fault Tolerance in VLSI Systems. 191--198","author":"Ghosh D.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","unstructured":"Goldberg D. 1989. Genetic Algorithms in Search Optimization and Machine Learning. Addison-Wesley New York.   Goldberg D. 1989. Genetic Algorithms in Search Optimization and Machine Learning. Addison-Wesley New York."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1119772.1119961"},{"volume-title":"Proceedings of the International Test Conference. 348--355","author":"Hirech M.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1118299.1118453"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISQED.2006.77"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ATS.2004.85"},{"key":"e_1_2_1_20_1","unstructured":"Illman R. and Aldrich G. 2002. On the finish rests with multiple clock. http:\/\/www.us.design-reuse.com\/articles\/2820\/on-time-finish-rests-with-multiple-clocks.html.  Illman R. and Aldrich G. 2002. On the finish rests with multiple clock. http:\/\/www.us.design-reuse.com\/articles\/2820\/on-time-finish-rests-with-multiple-clocks.html."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2002.1004585"},{"volume-title":"Proceedings of the Interconnect Technology Conference. 148--150","author":"Joyner J. W.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250662.1250680"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774601"},{"volume-title":"Proceedings of the International Electron Devices Meeting. 165--168","author":"Lee K. W.","key":"e_1_2_1_25_1"},{"volume-title":"Proceedings of the International Test Conference.","author":"Lewis D. L.","key":"e_1_2_1_26_1"},{"volume-title":"IEE Prcedings-Comput. Digit. Tech.","author":"Lin K.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/648020.745613"},{"key":"e_1_2_1_29_1","first-page":"22","article-title":"Scan paths wire length minimization and its short path error correction","volume":"38","author":"Nakamura K.","year":"1997","journal-title":"NEC Res. Devel."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"volume-title":"Proceedings of the International Symposium on Quality Electronic Design. 33--37","author":"Reif R.","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2005.108"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/VLSID.2007.41"},{"key":"e_1_2_1_34_1","unstructured":"Vucurevich T. 2007. The long road to 3D integration: Are we there yet&quest; In Keynote Speech at the 3D Architecture Conference.  Vucurevich T. 2007. The long road to 3D integration: Are we there yet&quest; In Keynote Speech at the 3D Architecture Conference."},{"volume-title":"Proceedings of the International Conference on Computer Design.","author":"Wu X.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148015.1148016"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1543438.1543442","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1543438.1543442","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:20Z","timestamp":1750253420000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1543438.1543442"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["10.1145\/1543438.1543442"],"URL":"https:\/\/doi.org\/10.1145\/1543438.1543442","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"type":"print","value":"1550-4832"},{"type":"electronic","value":"1550-4840"}],"subject":[],"published":{"date-parts":[[2009,7]]},"assertion":[{"value":"2008-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}