{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:44:07Z","timestamp":1761896647175,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,9,21]],"date-time":"2017-09-21T00:00:00Z","timestamp":1505952000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61376040","61674042, 61574046, 61574044 and 61628402"],"award-info":[{"award-number":["61376040","61674042, 61574046, 61574044 and 61628402"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1218906, CCF-1718570, CNS-1651695 and CNS-1441695"],"award-info":[{"award-number":["CCF-1218906, CCF-1718570, CNS-1651695 and CNS-1441695"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program","doi-asserted-by":"crossref","award":["2016YFB0201304"],"award-info":[{"award-number":["2016YFB0201304"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"name":"SRC","award":["2014-TS-2559"],"award-info":[{"award-number":["2014-TS-2559"]}]},{"DOI":"10.13039\/501100010871","name":"Recruitment Program of Global Experts","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100010871","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2018,1,31]]},"abstract":"<jats:p>Directed self-assembly (DSA) complemented with multiple patterning (MP) is an attractive next generation lithography (NGL) technique for contact-hole generation. Nevertheless, a high-quality DSA-aware layout decomposer is required to enable the technology. In this article, we introduce an efficient method which incorporates a set packing for generating DSA template candidates and a local search method. Besides, a multi-start strategy is integrated into the framework to prevent the local minima. Our framework encourages the reuse of existing coloring solvers. Hence, the development cost can significantly be reduced. In addition, for DSA multiple patterning where the number of masks is larger than two, we present an efficient iterative partition based method. Experimental results show that compared with the state-of-the-art work, our methods can achieve roughly 100\u00d7 speedup for double patterning, and 78.8% conflict reduction with 5\u00d7 speedup for triple patterning on the dense graphs.<\/jats:p>","DOI":"10.1145\/3131847","type":"journal-article","created":{"date-parts":[[2017,9,25]],"date-time":"2017-09-25T13:03:12Z","timestamp":1506344592000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["An Effective Layout Decomposition Method for DSA with Multiple Patterning in Contact-Hole Generation"],"prefix":"10.1145","volume":"23","author":[{"given":"Yunfeng","family":"Yang","sequence":"first","affiliation":[{"name":"Fudan University, Shanghai, China"}]},{"given":"Wai-Shing","family":"Luk","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}]},{"given":"Hai","family":"Zhou","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston"}]},{"given":"David Z.","family":"Pan","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, Texas"}]},{"given":"Dian","family":"Zhou","sequence":"additional","affiliation":[{"name":"University of Texas at Dallas, Richardson, Texas, USA"}]},{"given":"Changhao","family":"Yan","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}]},{"given":"Xuan","family":"Zeng","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}]}],"member":"320","published-online":{"date-parts":[[2017,9,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/196244.196603"},{"key":"e_1_2_1_2_1","unstructured":"G. Ausiello et al. 1999.Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer 423--424 pages.  G. Ausiello et al. 1999.Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer 423--424 pages."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2744769.2744868"},{"key":"e_1_2_1_4_1","volume-title":"Yuansheng Ma, Joydeep Mitra, and Puneet Gupta.","author":"Badr Yasmine","year":"2015","unstructured":"Yasmine Badr , Juan Andres Torres , Yuansheng Ma, Joydeep Mitra, and Puneet Gupta. 2015 b. Incorporating DSA in multipatterning semiconductor manufacturing technologies. In SPIE Advanced Lithography . International Society for Optics and Photonics, 94270P1--94270P8. Yasmine Badr, Juan Andres Torres, Yuansheng Ma, Joydeep Mitra, and Puneet Gupta. 2015b. Incorporating DSA in multipatterning semiconductor manufacturing technologies. In SPIE Advanced Lithography. International Society for Optics and Photonics, 94270P1--94270P8."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.828546"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(94)90065-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0920"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"W. J. Cook W. H. Cunningham W. R. Pulleyblank and A. Schrijver. 1998. Combinatorial Optimization. (1998).  W. J. Cook W. H. Cunningham W. R. Pulleyblank and A. Schrijver. 1998. Combinatorial Optimization. (1998).","DOI":"10.1002\/9781118033142"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2013.6691117"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2011.2179039"},{"volume-title":"Proceedings of the 19th Design Automation Conference (DAC\u201982)","author":"Charles","key":"e_1_2_1_11_1","unstructured":"Charles M. Fiduccia and Robert M. Mattheyses. 1982. A linear-time heuristic for improving network partitions . In Proceedings of the 19th Design Automation Conference (DAC\u201982) . IEEE, 175--181. Charles M. Fiduccia and Robert M. Mattheyses. 1982. A linear-time heuristic for improving network partitions. In Proceedings of the 19th Design Automation Conference (DAC\u201982). IEEE, 175--181."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321942"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-1665-5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204019"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.644032"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402008"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2008.4681616"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2016.7427992"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872334.2872350"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133429.2133451"},{"key":"e_1_2_1_22_1","volume-title":"Levinson","author":"Ma Yuansheng","year":"2017","unstructured":"Yuansheng Ma , Jongwook Kye , Gurdaman S. Khaira , Le Hong , James Word , Yuyang Sun , Joydeep Mitra , J. Andres Torres , Germain Fenger , and Harry J . Levinson . 2017 . Design technology co-optimization (DTCO) study on self-aligned-Via (SAV) with lamella DSA for sub-7 nm technology. In SPIE Advanced Lithography . International Society for Optics and Photonics, 101480B1--101480B12. Yuansheng Ma, Jongwook Kye, Gurdaman S. Khaira, Le Hong, James Word, Yuyang Sun, Joydeep Mitra, J. Andres Torres, Germain Fenger, and Harry J. Levinson. 2017. Design technology co-optimization (DTCO) study on self-aligned-Via (SAV) with lamella DSA for sub-7 nm technology. In SPIE Advanced Lithography. International Society for Optics and Photonics, 101480B1--101480B12."},{"key":"e_1_2_1_23_1","volume-title":"30th European Mask and Lithography Conference. International Society for Optics and Photonics, 92310T1--92310T10","author":"Ma Yuansheng","year":"2014","unstructured":"Yuansheng Ma , J. Andres Torres , Germain Fenger , Yuri Granik , Julien Ryckaert , Geert Vanderberghe , Joost Bekaert , and James Word . 2014 . Challenges and opportunities in applying grapho-epitaxy DSA lithography to metal cut and contact\/via applications . In 30th European Mask and Lithography Conference. International Society for Optics and Photonics, 92310T1--92310T10 . Yuansheng Ma, J. Andres Torres, Germain Fenger, Yuri Granik, Julien Ryckaert, Geert Vanderberghe, Joost Bekaert, and James Word. 2014. Challenges and opportunities in applying grapho-epitaxy DSA lithography to metal cut and contact\/via applications. In 30th European Mask and Lithography Conference. International Society for Optics and Photonics, 92310T1--92310T10."},{"key":"e_1_2_1_24_1","unstructured":"Bryon Moyer. 2016. Designing for Directed Self-Assembly. (2016). http:\/\/www.eejournal.com\/archives\/articles\/20160425-dsa\/.  Bryon Moyer. 2016. Designing for Directed Self-Assembly. (2016). http:\/\/www.eejournal.com\/archives\/articles\/20160425-dsa\/."},{"key":"e_1_2_1_25_1","unstructured":"Sunnyvale Nangate. 2008. Nangate 45nm Open Cell Library. (2008). http:\/\/www.nangate.com.  Sunnyvale Nangate. 2008. Nangate 45nm Open Cell Library. (2008). http:\/\/www.nangate.com."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872334.2872352"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.53581"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2966986.2967082"},{"key":"e_1_2_1_29_1","unstructured":"Synopsys. 2016. IC compiler. Retrieved from http:\/\/www.synopsys.com\/home.aspx.  Synopsys. 2016. IC compiler. Retrieved from http:\/\/www.synopsys.com\/home.aspx."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1060.0175"},{"key":"e_1_2_1_31_1","first-page":"89","article-title":"A fast algorithm for enumerating non-bipartite maximal matchings","volume":"3","author":"Uno Takeaki","year":"2001","unstructured":"Takeaki Uno . 2001 . A fast algorithm for enumerating non-bipartite maximal matchings . NII Journal 3 (2001), 89 -- 97 . Takeaki Uno. 2001. A fast algorithm for enumerating non-bipartite maximal matchings. NII Journal 3 (2001), 89--97.","journal-title":"NII Journal"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/368434.368865"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.2025688"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2016.7427995"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735023.1735054"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2011.6105297"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2013.6691115"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3131847","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3131847","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3131847","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:59Z","timestamp":1750212839000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3131847"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,21]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1,31]]}},"alternative-id":["10.1145\/3131847"],"URL":"https:\/\/doi.org\/10.1145\/3131847","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2017,9,21]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}