{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T09:51:02Z","timestamp":1764841862492,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,5,16]],"date-time":"2016-05-16T00:00:00Z","timestamp":1463356800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"The Chinese University of Hong Kong (CUHK) Direct Grant for Research"},{"name":"National Science Foundation, Semiconductor Research Corporation"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2016,7,26]]},"abstract":"<jats:p>Pin access has become one of the most difficult challenges for detailed routing in advanced technology nodes, for example, in 14nm and below, for which double-patterning lithography has to be used for manufacturing lower metal routing layers with tight pitches, such as M2 and M3. Self-aligned double patterning (SADP) provides better control on line edge roughness and overlay, but it has very restrictive design constraints and prefers regular layout patterns. This article presents a comprehensive pin-access planning and regular routing framework (PARR) for SADP friendliness. Our key techniques include precomputation of both intracell and intercell pin accessibility, as well as local and global pin-access planning to enable handshaking between standard cell-level pin access and detailed routing under SADP constraints. A pin access\u2013driven rip-up and reroute scheme is proposed to improve the ultimate routability. Our experimental results demonstrate that PARR can achieve much better routability and overlay control compared with previous approaches.<\/jats:p>","DOI":"10.1145\/2842612","type":"journal-article","created":{"date-parts":[[2016,5,17]],"date-time":"2016-05-17T15:58:00Z","timestamp":1463500680000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["PARR"],"prefix":"10.1145","volume":"21","author":[{"given":"Xiaoqing","family":"Xu","sequence":"first","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bei","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, NT, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jhih-Rong","family":"Gao","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Che-Lun","family":"Hsu","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David Z.","family":"Pan","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,5,16]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"C. J. Alpert Z. Li C. N. Sze and Y. Wei. 2013. Consideration of local routing and pin access during VLSI global routing. Retrieved April 2 2016 from http:\/\/www.google.com\/patents\/US20130086544 US Patent App. 13\/252 067.  C. J. Alpert Z. Li C. N. Sze and Y. Wei. 2013. Consideration of local routing and pin access during VLSI global routing. Retrieved April 2 2016 from http:\/\/www.google.com\/patents\/US20130086544 US Patent App. 13\/252 067."},{"key":"e_1_2_1_2_1","unstructured":"Cadence. 2009. LEF\/DEF Language Reference. Retrieved April 2 2016 from ftp:\/\/ftp.sitsemi.ru\/pub\/Cadence\/lefdefref.pdf.  Cadence. 2009. LEF\/DEF Language Reference. Retrieved April 2 2016 from ftp:\/\/ftp.sitsemi.ru\/pub\/Cadence\/lefdefref.pdf."},{"volume-title":"Cadence SOC Encounter. Retrieved","year":"2016","key":"e_1_2_1_3_1","unstructured":"Cadence. 2012. Cadence SOC Encounter. Retrieved April 2, 2016 from http:\/\/www.cadence.com\/. Cadence. 2012. Cadence SOC Encounter. Retrieved April 2, 2016 from http:\/\/www.cadence.com\/."},{"key":"e_1_2_1_4_1","volume-title":"Dees Jr and Patrick G","author":"William","year":"1982","unstructured":"William A. Dees Jr and Patrick G . Karger . 1982 . Automated rip-up and reroute techniques. In ACM\/IEEE Design Automation Conference (DAC\u201982). 432--439. William A. Dees Jr and Patrick G. Karger. 1982. Automated rip-up and reroute techniques. In ACM\/IEEE Design Automation Conference (DAC\u201982). 432--439."},{"volume-title":"ACM\/IEEE Design Automation Conference (DAC\u201981)","author":"William","key":"e_1_2_1_5_1","unstructured":"William A. Dees Jr and Robert J. Smith II. 1981. Performance of interconnection rip-up and reroute strategies . In ACM\/IEEE Design Automation Conference (DAC\u201981) . 382--390. William A. Dees Jr and Robert J. Smith II. 1981. Performance of interconnection rip-up and reroute strategies. In ACM\/IEEE Design Automation Conference (DAC\u201981). 382--390."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2744769.2744821"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488848"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2160916.2160923"},{"key":"e_1_2_1_9_1","unstructured":"Gurobi. 2014. GUROBI. Retrieved April 2 2016 from http:\/\/www.gurobi.com\/html\/academic.html.  Gurobi. 2014. GUROBI. Retrieved April 2 2016 from http:\/\/www.gurobi.com\/html\/academic.html."},{"volume-title":"R-Trees: A Dynamic Index Structure for Spatial Searching","author":"Guttman Antonin","key":"e_1_2_1_10_1","unstructured":"Antonin Guttman . 1984. R-Trees: A Dynamic Index Structure for Spatial Searching . Vol. 14 . ACM , New York, NY . Antonin Guttman. 1984. R-Trees: A Dynamic Index Structure for Spatial Searching. Vol. 14. ACM, New York, NY."},{"key":"e_1_2_1_11_1","volume-title":"IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201914)","author":"Hsu Meng-Kai","year":"2014","unstructured":"Meng-Kai Hsu , Nitesh Katta , Homer Yen-Hung Lin , Keny Tzu-Hen Lin , King Ho Tam , and Ken Chung-Hsing Wang . 2014 . Design and manufacturing process co-optimization in nano-technology . In IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201914) . 574--581. Meng-Kai Hsu, Nitesh Katta, Homer Yen-Hung Lin, Keny Tzu-Hen Lin, King Ho Tam, and Ken Chung-Hsing Wang. 2014. Design and manufacturing process co-optimization in nano-technology. In IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201914). 574--581."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2013.6509607"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593176"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.917986"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.2011539"},{"key":"e_1_2_1_16_1","volume-title":"Levinson","author":"Ma Yuangsheng","year":"2012","unstructured":"Yuangsheng Ma , Jason Sweis , Hidekazu Yoshida , Yan Wang , Jongwook Kye , and Harry J . Levinson . 2012 . Self-aligned double patterning (SADP) compliant design flow. In Proceedings of SPIE. 832706--832706. Yuangsheng Ma, Jason Sweis, Hidekazu Yoshida, Yan Wang, Jongwook Kye, and Harry J. Levinson. 2012. Self-aligned double patterning (SADP) compliant design flow. In Proceedings of SPIE. 832706--832706."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.877601"},{"volume-title":"NanGate FreePDK45 Generic Open Cell Library. Retrieved","year":"2016","key":"e_1_2_1_18_1","unstructured":"NanGate. 2012. NanGate FreePDK45 Generic Open Cell Library. Retrieved April 2, 2016 from http:\/\/www.si2.org\/openeda.si2.org\/projects\/nangatelib. NanGate. 2012. NanGate FreePDK45 Generic Open Cell Library. Retrieved April 2, 2016 from http:\/\/www.si2.org\/openeda.si2.org\/projects\/nangatelib."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2024724.2024763"},{"key":"e_1_2_1_20_1","volume-title":"The OpenMP API Specification for Parallel Programming. Retrieved","author":"MP.","year":"2016","unstructured":"Open MP. 2011. The OpenMP API Specification for Parallel Programming. Retrieved April 2, 2016 from http:\/\/openmp.org\/wp\/. (2011). OpenMP. 2011. The OpenMP API Specification for Parallel Programming. Retrieved April 2, 2016 from http:\/\/openmp.org\/wp\/. (2011)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2013274"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2276751"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2014.6974668"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.2011329"},{"volume-title":"Synopsys Design Compiler. Retrieved","year":"2016","key":"e_1_2_1_25_1","unstructured":"Synopsys. 2012. Synopsys Design Compiler. Retrieved April 2, 2016 from http:\/\/www.synopsys.com. (2012). Synopsys. 2012. Synopsys Design Compiler. Retrieved April 2, 2016 from http:\/\/www.synopsys.com. (2012)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133429.2133560"},{"volume-title":"IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201913)","author":"Xiao Zigang","key":"e_1_2_1_27_1","unstructured":"Zigang Xiao , Yuelin Du , Haitong Tian , and Martin D. F. Wong . 2013. Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time . In IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201913) . 32--39. Zigang Xiao, Yuelin Du, Haitong Tian, and Martin D. F. Wong. 2013. Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time. In IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201913). 32--39."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2560519.2560530"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2744769.2744890"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742060.2742084"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1960397.1960410"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2842612","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2842612","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:53:48Z","timestamp":1750222428000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2842612"}},"subtitle":["Pin-Access Planning and Regular Routing for Self-Aligned Double Patterning"],"short-title":[],"issued":{"date-parts":[[2016,5,16]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,7,26]]}},"alternative-id":["10.1145\/2842612"],"URL":"https:\/\/doi.org\/10.1145\/2842612","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2016,5,16]]},"assertion":[{"value":"2015-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}