{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T14:19:13Z","timestamp":1762784353877,"version":"build-2065373602"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["92473207 and 62204111"],"award-info":[{"award-number":["92473207 and 62204111"]}],"id":[{"id":"10.13039\/501100001809","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":[[2026,1,31]]},"abstract":"<jats:p>Routing is a crucial step in the VLSI design flow. With advancements in manufacturing technology, more constraints have emerged in design rules, particularly regarding obstacles during routing, leading to increased routing complexity. Unfortunately, many global routers struggle to generate efficient obstacle-free solutions due to the lack of scalable obstacle-avoiding tree generation methods and the capability to handle modern designs with complex obstacles and nets. In this work, we propose an efficient obstacle-aware global routing flow for VLSI designs with obstacles. The flow includes a rule-based obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) algorithm during the tree generation phase. This algorithm is both scalable and fast, providing tree topologies avoiding obstacles in the early stage globally. With its guidance, in the later stages, the OARSMT-guided and obstacle-aware sparse maze routing are proposed to further minimize obstacle violations and reduce overflow costs. Compared to previously advanced methods on the benchmark with obstacles, our approach successfully eliminates obstacle violations and reduces wirelength and overflow cost, while sacrificing only a limited number of via counts and runtime overhead.<\/jats:p>\n                  <jats:p\/>","DOI":"10.1145\/3769005","type":"journal-article","created":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T11:36:46Z","timestamp":1760355406000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A High Efficient and Scalable Obstacle-Avoiding VLSI Global Routing Flow"],"prefix":"10.1145","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-4986-2837","authenticated-orcid":false,"given":"Junhao","family":"Guo","sequence":"first","affiliation":[{"name":"School of Integrated Circuits, Sun Yat-Sen University","place":["Shenzhen, China"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-0970-1432","authenticated-orcid":false,"given":"Hongxin","family":"Kong","sequence":"additional","affiliation":[{"name":"Advanced Micro Devices Inc","place":["Round Rock, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9943-0550","authenticated-orcid":false,"given":"Lang","family":"Feng","sequence":"additional","affiliation":[{"name":"School of Integrated Circuits, Sun Yat-Sen University","place":["Shenzhen, China"]}]}],"member":"320","published-online":{"date-parts":[[2025,11,10]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2096571"},{"key":"e_1_3_1_3_2","first-page":"338","volume-title":"IEEE\/ACM International Conference on Computer-Aided Design (2008)","author":"Chang Yen-Jung","year":"2008","unstructured":"Yen-Jung Chang, Yu-Ting Lee, and Ting-Chi Wang. 2008. NTHU-route 2.0: A fast and stable global router. In IEEE\/ACM International Conference on Computer-Aided Design (2008). IEEE Press, New York, NY, USA, 338\u2013343."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3505170.3506721"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907068"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/41958.41985"},{"key":"e_1_3_1_7_2","unstructured":"DIMACS Implementation Challenge in Collaboration with ICERM: Steiner Tree Problems. 2016. Retrieved from https:\/\/dimacs11.zib.de\/downloads.html."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1123008.1123020"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/1356802.1356863"},{"key":"e_1_3_1_10_2","series-title":"Advances in Intelligent Systems and Computing","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1007\/978-3-642-31600-5_64","volume-title":"Advances in Computing and Information Technology (2013)","author":"Ghosal P.","year":"2013","unstructured":"P. Ghosal, A. Das, and S. Das. 2013. Obstacle aware RMST generation using non-manhattan routing for 3D ICs. In Advances in Computing and Information Technology (2013), N. Meghanathan, D. Nagamalai, and N. Chaki (Eds.). Advances in Intelligent Systems and Computing, Vol. 178. Springer, Berlin,, 657\u2013666."},{"key":"e_1_3_1_11_2","series-title":"Advances in Intelligent Systems and Computing","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1007\/978-3-642-31552-7_65","volume-title":"Advances in Computing and Information Technology (2013)","author":"Ghosal P.","year":"2013","unstructured":"P. Ghosal, S. Das, and A. Das. 2013. A novel algorithm for obstacle aware RMST construction during routing in 3D ICs. In Advances in Computing and Information Technology (2013). N. Meghanathan, D. Nagamalai, and N. Chaki (Eds.). Advances in Intelligent Systems and Computing, Vol. 177. Springer, Berlin, 649\u2013658."},{"key":"e_1_3_1_12_2","article-title":"cu-gr-2: An open-source global router","author":"Group CUHK-EDA","year":"2023","unstructured":"CUHK-EDA Group. 2023. cu-gr-2: An open-source global router. Retrieved from https:\/\/github.com\/cuhk-eda\/cu-gr-2.git.","journal-title":"https:\/\/github.com\/cuhk-eda\/cu-gr-2.git"},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1145\/3626184.3639693","volume-title":"International Symposium on Physical Design (2024)","author":"Liang Rongjian","year":"2024","unstructured":"Rongjian Liang, Anthony Agnesina, Wen-Hao Liu, and Haoxing Ren. 2024. GPU\/ML-enhanced large scale global routing contest. In International Symposium on Physical Design (2024). ACM, New York, NY, USA, 269\u2013274."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.917583"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.2006095"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3177878"},{"issue":"12","key":"e_1_3_1_17_2","doi-asserted-by":"crossref","first-page":"1928","DOI":"10.1109\/TCAD.2014.2363390","article-title":"Efficient multilayer obstacle-avoiding rectilinear steiner tree construction based on geometric reduction","volume":"33","author":"Liu Chih-Hung","year":"2014","unstructured":"Chih-Hung Liu, Chun-Xun Lin, I-Che Chen, D. T. Lee, and Ting-Chi Wang. 2014. Efficient multilayer obstacle-avoiding rectilinear steiner tree construction based on geometric reduction. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33, 12 (2014), 1928\u20131941.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"e_1_3_1_18_2","first-page":"1","volume-title":"Proceedings of the 60th Annual ACM\/IEEE Design Automation Conference (2023)","author":"Liu Jinwei","year":"2023","unstructured":"Jinwei Liu and Evangeline F. Y. Young. 2023. EDGE: Efficient DAG-based global routing engine. In Proceedings of the 60th Annual ACM\/IEEE Design Automation Conference (2023). IEEE Press, San Francisco, CA, USA, 1\u20136."},{"key":"e_1_3_1_19_2","first-page":"464","volume-title":"IEEE\/ACM International Conference on Computer-Aided Design (2006)","author":"Pan Min","year":"2006","unstructured":"Min Pan and Chris Chu. 2006. FastRoute: A step to integrate global routing into placement. In IEEE\/ACM International Conference on Computer-Aided Design (2006). ACM, New York, NY, USA, 464\u2013471."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.923255"},{"key":"e_1_3_1_21_2","first-page":"320","volume-title":"Annual Design Automation Conference (2009)","author":"Wu Tai-Hsuan","year":"2009","unstructured":"Tai-Hsuan Wu, Azadeh Davoodi, and Jeffrey T. Linderoth. 2009. GRIP: Scalable 3D global routing using integer programming. In Annual Design Automation Conference (2009). ACM, New York, NY, USA, 320\u2013325."},{"key":"e_1_3_1_22_2","first-page":"250","volume-title":"Proceedings of the International Conference on Computer-Aided Design (2011)","author":"Xu Yue","year":"2011","unstructured":"Yue Xu and Chris Chu. 2011. MGR: Multi-level global router. In Proceedings of the International Conference on Computer-Aided Design (2011). IEEE Press, San Jose, CA, USA, 250\u2013255."},{"key":"e_1_3_1_23_2","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1109\/ASPDAC.2009.4796542","volume-title":"Asia and South Pacific Design Automation Conference (2009)","author":"Xu Yue","year":"2009","unstructured":"Yue Xu, Yanheng Zhang, and Chris Chu. 2009. FastRoute 4.0: Global router with efficient via minimization. In Asia and South Pacific Design Automation Conference (2009). IEEE Press, Yokohama, Japan, 576\u2013581."},{"key":"e_1_3_1_24_2","first-page":"348","article-title":"Rectilinear steiner minimal tree among obstacles","volume":"1","author":"Yang Yang","year":"2003","unstructured":"Yang Yang, Qi Zhu, Tong Jing, Xianlong Hong, and Yin Wang. 2003. Rectilinear steiner minimal tree among obstacles. International Conference on ASIC 1 (2003), 348\u2013351.","journal-title":"International Conference on ASIC"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TETCI.2023.3306241"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769005","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T14:14:25Z","timestamp":1762784065000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,10]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1,31]]}},"alternative-id":["10.1145\/3769005"],"URL":"https:\/\/doi.org\/10.1145\/3769005","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2025,11,10]]},"assertion":[{"value":"2025-03-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-02","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}