{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:40:11Z","timestamp":1750203611083,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T00:00:00Z","timestamp":1567987200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"World Class 300 R8D Project of MSS","award":["S2435123"],"award-info":[{"award-number":["S2435123"]}]},{"name":"National Research Foundation of Korea (NRF) of MSIP","award":["2019R1A2C2003402"],"award-info":[{"award-number":["2019R1A2C2003402"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2019,11,30]]},"abstract":"<jats:p>Redundant via (RV) insertion helps prevent via defects and hence leads to yield enhancement. However, RV insertion in self-aligned double patterning (SADP) processes is challenging since cut optimization has to be considered together. In SADP, parallel one-dimensional metal lines are divided into signal wires and dummy wires by line-end cuts. If an RV is inserted, signal wires need to be extended to connect to the RV. To this end, an additional cut, which we call RV cut, is introduced to make a space for the extension. Since RV cuts and line-end cuts are manufactured with the same mask set, design rules between those cuts have to be honored, which incurs proper distribution and mask assignment to individual cuts. In this article, we address a problem of integrated RV insertion and cut optimization. We show that the problem can be formulated as an integer linear programming (ILP). We also propose a heuristic algorithm is presented for practical application, in which potential locations of RVs are first identified and used to properly insert as many RVs as possible while minimizing the conflict between RV cuts. Our experimental results demonstrate that 75% of vias receive RVs with 8% increase in total wire length, which is only slightly worse than the optimal result obtained by ILP.<\/jats:p>","DOI":"10.1145\/3355391","type":"journal-article","created":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T12:10:26Z","timestamp":1568031026000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Cut Optimization for Redundant Via Insertion in Self-Aligned Double Patterning"],"prefix":"10.1145","volume":"24","author":[{"given":"Youngsoo","family":"Song","sequence":"first","affiliation":[{"name":"KAIST, Daejeon, Republic of Korea, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daijoon","family":"Hyun","sequence":"additional","affiliation":[{"name":"KAIST, Daejeon, Republic of Korea, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingon","family":"Lee","sequence":"additional","affiliation":[{"name":"KAIST, Daejeon, Republic of Korea, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinwook","family":"Jung","sequence":"additional","affiliation":[{"name":"KAIST, Daejeon, Republic of Korea, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Youngsoo","family":"Shin","sequence":"additional","affiliation":[{"name":"KAIST, Daejeon, Republic of Korea, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,9,9]]},"reference":[{"volume-title":"Retrieved on","year":"2019","key":"e_1_2_1_1_1","unstructured":"{n.d.}. Gurobi optimizer reference manual . Retrieved on August 05, 2019 from http:\/\/www.gurobi.com {n.d.}. Gurobi optimizer reference manual. Retrieved on August 05, 2019 from http:\/\/www.gurobi.com"},{"volume-title":"IWLS 2005 Benchmarks. Retrieved on","year":"2019","key":"e_1_2_1_2_1","unstructured":"{n.d.}. IWLS 2005 Benchmarks. Retrieved on August 05, 2019 from http:\/\/iwls.org\/iwls2005\/benchmarks.html. {n.d.}. IWLS 2005 Benchmarks. Retrieved on August 05, 2019 from http:\/\/iwls.org\/iwls2005\/benchmarks.html."},{"volume-title":"Retrieved on","year":"2019","key":"e_1_2_1_3_1","unstructured":"{n.d.}. OpenCores. Retrieved on August 05, 2019 from http:\/\/www.opencores.org\/. {n.d.}. OpenCores. Retrieved on August 05, 2019 from http:\/\/www.opencores.org\/."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/16.568036"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.2501760"},{"volume-title":"Complexity and approximation: Combinatorial optimization problems and their approximability properties","author":"Ausiello Giorgio","key":"e_1_2_1_6_1","unstructured":"Giorgio Ausiello , Pierluigi Crescenzi , Giorgio Gambosi , Viggo Kann , Alberto Marchetti-Spaccamela , and Marco Protasi . 2012. Complexity and approximation: Combinatorial optimization problems and their approximability properties . Springer . Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, and Marco Protasi. 2012. Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872334.2872355"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.05.010"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233501.1233599"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593233"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2017.2712660"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488848"},{"volume-title":"Proc. Asia South Pacific Des. Autom. Conf. 143--148","author":"Gao Jhih-Rong","key":"e_1_2_1_13_1","unstructured":"Jhih-Rong Gao , Bei Yu , and David Z. Pan . 2014. Self-aligned double patterning layout decomposition with complementary e-beam lithography . In Proc. Asia South Pacific Des. Autom. Conf. 143--148 . Jhih-Rong Gao, Bei Yu, and David Z. Pan. 2014. Self-aligned double patterning layout decomposition with complementary e-beam lithography. In Proc. Asia South Pacific Des. Autom. Conf. 143--148."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306494"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1088\/1674-4926\/31\/10\/106003"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2966986.2967048"},{"volume-title":"Proc. Custom Integr. Circuits Conf. 485--488","author":"Kurokawa A.","key":"e_1_2_1_17_1","unstructured":"A. Kurokawa , T. Kanamoto , A. Kasebe , Y. Inoue , and H. Masuda . 2004. Efficient capacitance extraction method for interconnects with dummy fills . In Proc. Custom Integr. Circuits Conf. 485--488 . A. Kurokawa, T. Kanamoto, A. Kasebe, Y. Inoue, and H. Masuda. 2004. Efficient capacitance extraction method for interconnects with dummy fills. In Proc. Custom Integr. Circuits Conf. 485--488."},{"volume-title":"Proc. CMP-MIC Conf. 255--258","author":"Lee Brian","key":"e_1_2_1_18_1","unstructured":"Brian Lee , Duane S. Boning , Dale L. Hetherington , and David J. Stein . 2000. Using smart dummy fill and selective reverse etchback for pattern density equalization . In Proc. CMP-MIC Conf. 255--258 . Brian Lee, Duane S. Boning, Dale L. Hetherington, and David J. Stein. 2000. Using smart dummy fill and selective reverse etchback for pattern density equalization. In Proc. CMP-MIC Conf. 255--258."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.458341"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.2006151"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1509633.1509746"},{"key":"e_1_2_1_22_1","volume-title":"Proc. SPIE Advanced Lithography. 10148N1--10148N13","author":"Mohyeldin Ahmed","year":"2017","unstructured":"Ahmed Mohyeldin , Uwe Paul Schroeder , Ramya Srinivasan , Hritez Narisetty , Shobhit Malik , and Sriram Madhavan . 2017 . Quantifying electrical impacts on redundant wire insertion in 7nm unidirectional designs . In Proc. SPIE Advanced Lithography. 10148N1--10148N13 . Ahmed Mohyeldin, Uwe Paul Schroeder, Ramya Srinivasan, Hritez Narisetty, Shobhit Malik, and Sriram Madhavan. 2017. Quantifying electrical impacts on redundant wire insertion in 7nm unidirectional designs. In Proc. SPIE Advanced Lithography. 10148N1--10148N13."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICECS.2006.379928"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355391","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355391","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:34Z","timestamp":1750202614000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355391"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,9]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,11,30]]}},"alternative-id":["10.1145\/3355391"],"URL":"https:\/\/doi.org\/10.1145\/3355391","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2019,9,9]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}