{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:02Z","timestamp":1750220462121,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T00:00:00Z","timestamp":1603411200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior-Brasil (CAPES)-Finance Code 001"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>Detailed routing is one of the most time-consuming steps of physical synthesis of integrated circuits. Also, it is very challenging due to the complexity of the design rules that the router must obey. In this article, we present SmartDR, a detailed routing system that focuses on good design rule handling and fast runtime. To attend these objectives, we propose a novel pin access approach and a fast design rule aware A*-interval-based path search algorithm. The pin access method uses resource sharing ghost pin access paths with dynamic legalization check. We also propose a design rule check algorithm to detect thick metal shapes that are widely created using the proposed pin access method. The path search algorithm integrates design rule check on its core, handling many design rules that would not be possible to be solved by postprocessing. It is aware of the minimum area rule, the cut spacing of via cuts within the same path, and the via library. We also present a new technique to improve A*-based path search in detailed routing. The technique makes the path search algorithm aware of the global routing guides, accelerating the search. Using ISPD 2018 Contest benchmarks, our experiments show that our router is superior to the state-of-the-art routers that were also tested using the same benchmarks. Our router has presented, on average, 77.6% less runtime, 73.5% less design rule violations, with respect to Dr. CU 2.0, which is the better of the compared routers.<\/jats:p>","DOI":"10.1145\/3417133","type":"journal-article","created":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T21:09:36Z","timestamp":1603487376000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["SmartDR"],"prefix":"10.1145","volume":"26","author":[{"given":"St\u00e8phano M. M.","family":"Gon\u00e7alves","sequence":"first","affiliation":[{"name":"Technology Development Center, Federal University of Pelotas, Pelotas, RS, Brazil"}]},{"given":"Leomar S. da","family":"Rosa Jr","sequence":"additional","affiliation":[{"name":"Technology Development Center, Federal University of Pelotas, Pelotas, RS, Brazil"}]},{"given":"Felipe S.","family":"Marques","sequence":"additional","affiliation":[{"name":"Technology Development Center, Federal University of Pelotas, Pelotas, RS, Brazil"}]}],"member":"320","published-online":{"date-parts":[[2020,10,23]]},"reference":[{"volume-title":"Proceedings of the 2018 International Symposium on Physical Design (ISPD\u201918)","year":"2018","author":"Posser Gracieli Stefanus Mantik","key":"e_1_2_1_1_1"},{"volume-title":"Amin and Posser Gracieli. ISPD 2019 Initial detailed routing contest and benchmark with advanced routing rules. In Proceedings of the International Symposium on Physical Design (ISPD\u201919)","author":"Wen-Hao Liu","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.920694"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.842803"},{"key":"e_1_2_1_5_1","article-title":"A gridless routing system with nonslicing floorplanning-based crosstalk reduction on gridless track assignment","volume":"16","author":"Yih-Lang Li","year":"2011","journal-title":"ACM Trans. Design Autom. Electron. Syst."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.891381"},{"volume-title":"Proceedings of the 2002 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201902)","year":"2002","author":"Shabbir Batterywala","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2012.2214491"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2013274"},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"A multi-commodity flow-based detailed router with efficient acceleration techniques","volume":"99","author":"Xiaotao Jia","year":"2017","journal-title":"IEEE Trans. Comput.-Aided Design Integr. Circ. Syst."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3240765.3240766"},{"volume-title":"Proceedings of the International Conference on Computer-Aided Design (ICCAD\u201918)","year":"2018","author":"Fan-Keng Sun","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the Design, Automation and Test in Europe (DAC\u201998)","year":"1998","author":"Asmus Hetzel","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2442087.2442103","article-title":"Bonnroute: Algorithms and data structures for fast and good","volume":"18","author":"Michael Gester","year":"2013","journal-title":"ACM Trans. Design Autom. Electron. Syst."},{"key":"e_1_2_1_15_1","first-page":"3","article-title":"Self-aligned double patterning-aware detailed routing with double via insertion and via manufacturability consideration","volume":"37","author":"Yixiao Ding","year":"2018","journal-title":"IEEE Trans. Comput.-Aided Design Integr. Circ. Syst."},{"volume-title":"Proceedings of the 55th ACM\/ESDA\/IEEE Design Automation Conference (DAC\u201918)","year":"2018","author":"Hai-Juan Yu","key":"e_1_2_1_16_1"},{"volume-title":"DAC '09 Proceedings of the 46th Annual Design Automation Conference (San Francisco","year":"2009","author":"Kun Yuan","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2010.5457003"},{"volume-title":"Proceedings of the Design for Manufacturability through Design-Process Integration V.","year":"2011","author":"Minoo Mirsaeedi","key":"e_1_2_1_19_1"},{"volume-title":"Proceedings of the 49th Annual Design Automation Conference (DAC\u201912)","author":"Qiang Ma","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2513670"},{"volume-title":"Proceedings of the 48th Design Automation Conference (DAC\u201911)","year":"2011","author":"Tim Nieberg","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","article-title":"PARR: Pin-access planning and regular routing for self-aligned double patterning","volume":"21","author":"Xiaoqing Xu","year":"2016","journal-title":"ACM Trans. Design Autom. Electron. Syst."},{"volume-title":"Proceedings of the 54th Annual Design Automation Conference (DAC\u201917)","author":"Xiaoqing Xu","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1961.5219222"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800260.809014"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2265878"},{"volume-title":"Proceedings of the 24th Asia and South Pacific Design Automation Conference (ASPDAC\u201919)","author":"Gengjie Chen","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2014.2385755"},{"volume-title":"Introduction to Algorithms","author":"Cormen Thomas","key":"e_1_2_1_31_1"},{"volume-title":"Proceedings of the IEEE\/ACM Inter. Conference on Computer-Aided Design (ICCAD\u201919)","author":"Haocheng Li","key":"e_1_2_1_32_1"},{"volume-title":"Marques","year":"2019","author":"Gon\u00e7alves Stephano M. M.","key":"e_1_2_1_33_1"},{"volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","key":"e_1_2_1_34_1"},{"volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS\u201919)","author":"Gon\u00e7alves Stephano M. M.","key":"e_1_2_1_35_1"},{"volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS\u201917)","author":"Gon\u00e7alves St\u00e8phano M. M.","key":"e_1_2_1_36_1"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417133","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3417133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:13Z","timestamp":1750193293000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417133"}},"subtitle":["Algorithms and Techniques for Fast Detailed Routing with Good Design Rule Handling"],"short-title":[],"issued":{"date-parts":[[2020,10,23]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3417133"],"URL":"https:\/\/doi.org\/10.1145\/3417133","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2020,10,23]]},"assertion":[{"value":"2019-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}