{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T16:07:12Z","timestamp":1780675632164,"version":"3.54.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,3,1]],"date-time":"2009-03-01T00:00:00Z","timestamp":1235865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:p>In this article, we present BoxRouter 2.0, and discuss its architecture and implementation. As high-performance VLSI design becomes more interconnect-dominant, efficient congestion elimination in global routing is in greater demand. Hence, we propose a global router which has a strong ability to improve routability and minimize the number of vias with blockages, while minimizing wirelength. BoxRouter 2.0 is extended from BoxRouter 1.0, but can perform multi-layer routing with 2D global routing and layer assignment. Our 2D global routing is equipped with two ideas: node shifting for congestion-aware Steiner tree and robust negotiation-based A* search for routing stability. After 2D global routing, 2D-to-3D mapping is done by the layer assignment which is powered by progressive via\/blockage-aware integer linear programming. Experimental results show that BoxRouter 2.0 has better routability with comparable wirelength than other routers on ISPD07 benchmark, and it can complete (no overflow) the widely used ISPD98 benchmark for the first time in the literature with the shortest wirelength. We further generate a set of harder ISPD98 benchmarks to push the limit of BoxRouter 2.0, and propose the hardened ISPD98 benchmarks to map state-of-the-art solutions for future routing research.<\/jats:p>","DOI":"10.1145\/1497561.1497575","type":"journal-article","created":{"date-parts":[[2009,4,6]],"date-time":"2009-04-06T16:34:22Z","timestamp":1239035662000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":49,"title":["BoxRouter 2.0"],"prefix":"10.1145","volume":"14","author":[{"given":"Minsik","family":"Cho","sequence":"first","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Katrina","family":"Lu","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kun","family":"Yuan","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David Z.","family":"Pan","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,4,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.205007"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.920691"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.825864"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.809662"},{"key":"e_1_2_1_5_1","first-page":"4","article-title":"Hierarchical wire routing","volume":"2","author":"Burstein M.","year":"1983","journal-title":"IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2007.357995"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.759077"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.4616"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146909.1147009"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907003"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233501.1233599"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2004.1382665"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Design Automation Conference.","author":"Ciesielski M. J."},{"key":"e_1_2_1_14_1","unstructured":"Cong J. 1997. Challenges and opportunities for design innovations in nanometer technologies. SRC Design Science Concept Papers.  Cong J. 1997. Challenges and opportunities for design innovations in nanometer technologies. SRC Design Science Concept Papers."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.842803"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference.","author":"Gao J.-R."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/775832.775842"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1231996.1232024"},{"key":"e_1_2_1_19_1","unstructured":"http:\/\/www.ispd.cc\/ispd07_contest.html.  http:\/\/www.ispd.cc\/ispd07_contest.html."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Computer Aided Design.","author":"Hu J."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-9260(01)00020-7"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the International Conference on Microelectronics.","author":"Jhang K.","year":"2000"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/369691.369711"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2002.1013891"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/332357.332375"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the International Conference on Computer Aided Design.","author":"Kutzschebauch T."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1118299.1118376"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/201310.201328"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.42135"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International Conference on Computer Aided Design.","author":"Ozdal M. M."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233501.1233596"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2007.357994"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the International Conference on Computer Aided Design.","author":"Roy J. A."},{"key":"e_1_2_1_34_1","volume-title":"International Technology Roadmap for Semiconductors","author":"Semiconductor Industry Association"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009683110027"},{"key":"e_1_2_1_36_1","unstructured":"UTDA. http:\/\/www.cerc.utexas.edu\/utda.  UTDA. http:\/\/www.cerc.utexas.edu\/utda."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/370155.370560"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/981066.981110"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1053355.1053377"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the IEEE Design Automation Technical Conference on Electronic Design Process.","author":"Westra J."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055137.1055144"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.870061"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference.","author":"Wu D."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120725.1120836"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1497561.1497575","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1497561.1497575","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:43Z","timestamp":1750250743000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1497561.1497575"}},"subtitle":["A hybrid and robust global router with layer assignment for routability"],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["10.1145\/1497561.1497575"],"URL":"https:\/\/doi.org\/10.1145\/1497561.1497575","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}