{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T05:55:16Z","timestamp":1775454916927,"version":"3.50.1"},"reference-count":25,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2012,8,9]],"date-time":"2012-08-09T00:00:00Z","timestamp":1344470400000},"content-version":"vor","delay-in-days":221,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["VLSI Design"],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Modern large\u2010scale circuit designs have created great demand for fast and high\u2010quality global routing algorithms to resolve the routing congestion at the global level. Rip\u2010up and reroute scheme has been employed by the majority of academic and industrial global routers today, which iteratively resolve the congestion by recreating the routing path based on current congestion. This method is proved to be the most practical routing framework. However, the traditional iterative maze routing technique converges very slowly and easily gets stuck at local optimal solutions. In this work, we propose a very efficient and high\u2010quality global router\u2014FastRoute. FastRoute integrates several novel techniques: fast congestion\u2010driven via\u2010aware Steiner tree construction, 3\u2010bend routing, virtual capacity adjustment, multisource multi\u2010sink maze routing, and spiral layer assignment. These techniques not only address the routing congestion measured at the edges of global routing grids but also minimize the total wirelength and via usage, which is critical for subsequent detailed routing, yield, and manufacturability. Experimental results show that FastRoute is highly effective and efficient to solve ISPD07 and ISPD08 global routing benchmark suites. The results outperform recently published academic global routers in both routability and runtime. In particular, for ISPD07 and ISPD08 global routing benchmarks, FastRoute generates 12 congestion\u2010free solutions out of 16 benchmarks with a speed significantly faster than other routers.<\/jats:p>","DOI":"10.1155\/2012\/608362","type":"journal-article","created":{"date-parts":[[2012,8,9]],"date-time":"2012-08-09T21:03:16Z","timestamp":1344546196000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["FastRoute: An Efficient and High\u2010Quality Global Router"],"prefix":"10.1155","volume":"2012","author":[{"given":"Min","family":"Pan","sequence":"first","affiliation":[]},{"given":"Yue","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Yanheng","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Chris","family":"Chu","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2012,8,9]]},"reference":[{"key":"e_1_2_7_1_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167\u20109260(01)00020\u20107"},{"key":"e_1_2_7_2_2","doi-asserted-by":"crossref","unstructured":"MoffittM. D. RoyJ. A. andMarkovI. L. The coming of age of (academic) global routing Proceedings of the ACM International Symposium on Physical Design (ISPD \u203208) April 2008 148\u2013155 2-s2.0-43349102191 https:\/\/doi.org\/10.1145\/1353629.1353662.","DOI":"10.1145\/1353629.1353662"},{"key":"e_1_2_7_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.920691"},{"key":"e_1_2_7_4_2","doi-asserted-by":"crossref","unstructured":"ChoM.andPanD. Z. BoxRouter: a new global router based on box expansion and progressive ILP Proceedings of the Design Automation Conference 2006 373\u2013378.","DOI":"10.1145\/1146909.1147009"},{"key":"e_1_2_7_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2002.1013891"},{"key":"e_1_2_7_6_2","doi-asserted-by":"crossref","unstructured":"HadsellR. T.andMaddenP. H. Improved global routing through congestion estimation Proceedings of the 40th Design Automation Conference June 2003 28\u201331 2-s2.0-0043092229.","DOI":"10.1145\/775832.775842"},{"key":"e_1_2_7_7_2","doi-asserted-by":"crossref","unstructured":"ChoM. LuK. YuanK. andPanD. Z. BoxRouter 2.0: architecture and implementation of a hybrid and robust global router Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD \u203207) November 2007 503\u2013508 2-s2.0-43349093583 https:\/\/doi.org\/10.1109\/ICCAD.2007.4397314.","DOI":"10.1109\/ICCAD.2007.4397314"},{"key":"e_1_2_7_8_2","doi-asserted-by":"crossref","unstructured":"OzdalM. M.andWongM. D. F. Archer: a history-driven global routing algorithm Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD \u203207) November 2007 488\u2013495 2-s2.0-43349087745 https:\/\/doi.org\/10.1109\/ICCAD.2007.4397312.","DOI":"10.1109\/ICCAD.2007.4397312"},{"key":"e_1_2_7_9_2","doi-asserted-by":"crossref","unstructured":"GaoJ.-R. WuP.-C. andWangT.-C. A new global router for modern designs Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC \u203208) March 2008 232\u2013237 2-s2.0-43349104421 https:\/\/doi.org\/10.1109\/ASPDAC.2008.4483948.","DOI":"10.1109\/ASPDAC.2008.4483948"},{"key":"e_1_2_7_10_2","doi-asserted-by":"crossref","unstructured":"ChangY.-J. LeeY.-T. andWangT.-C. NTHU-route 2.0: a fast and stable global router Proceedings of the International Conference on Computer-Aided Design (ICCAD \u203208) November 2008 338\u2013343 2-s2.0-57849137400 https:\/\/doi.org\/10.1109\/ICCAD.2008.4681595.","DOI":"10.1109\/ICCAD.2008.4681595"},{"key":"e_1_2_7_11_2","doi-asserted-by":"crossref","unstructured":"QienH. Y. HsuC. H. andChangY. W. High-performance global routing with fast overflow reduction Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC \u203209) January 2009 582\u2013587 2-s2.0-64549098136 https:\/\/doi.org\/10.1109\/ASPDAC.2009.4796543.","DOI":"10.1109\/ASPDAC.2009.4796543"},{"key":"e_1_2_7_12_2","doi-asserted-by":"crossref","unstructured":"RoyJ. A.andMarkovI. L. High-performance routing at the nanometer scale Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD \u203207) November 2007 496\u2013502 2-s2.0-43349099015 https:\/\/doi.org\/10.1109\/ICCAD.2007.4397313.","DOI":"10.1109\/ICCAD.2007.4397313"},{"key":"e_1_2_7_13_2","doi-asserted-by":"crossref","unstructured":"McMurchieL.andEbelingC. PathFinder: a negotiation-based performance-driven router for FPGAs Proceedings of the ACM 3rd International Symposium on Field-Programmable Gate Arrays February 1995 111\u2013117 2-s2.0-0029204986.","DOI":"10.1145\/201310.201328"},{"key":"e_1_2_7_14_2","doi-asserted-by":"crossref","unstructured":"MoffittM. D. MaizeRouter: engineering an effective Global Router Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC \u203208) March 2008 226\u2013231 2-s2.0-43349083037 https:\/\/doi.org\/10.1109\/ASPDAC.2008.4483946.","DOI":"10.1109\/ASPDAC.2008.4483946"},{"key":"e_1_2_7_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.923255"},{"key":"e_1_2_7_16_2","doi-asserted-by":"crossref","unstructured":"PanM.andChuC. FastRoute: a step to integrate global routing into placement Proceedings of the International Conference on Computer-Aided Design (ICCAD \u203206) November 2006 464\u2013471 2-s2.0-46149111721 https:\/\/doi.org\/10.1109\/ICCAD.2006.320159.","DOI":"10.1145\/1233501.1233596"},{"key":"e_1_2_7_17_2","doi-asserted-by":"crossref","unstructured":"PanM.andChuC. FastRoute 2.0: a High-quality and efficient global router Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC \u203207) January 2007 250\u2013255 2-s2.0-46649104482 https:\/\/doi.org\/10.1109\/ASPDAC.2007.357994.","DOI":"10.1109\/ASPDAC.2007.357994"},{"key":"e_1_2_7_18_2","doi-asserted-by":"crossref","unstructured":"YanhengZ. YueX. andChuC. FastRoute3.0: a fast and high quality global router based on virtual capacity ASP-DAC International Conference on Computer-Aided Design (ICCAD \u203208) November 2008 344\u2013349 2-s2.0-57849120664 https:\/\/doi.org\/10.1109\/ICCAD.2008.4681596.","DOI":"10.1109\/ICCAD.2008.4681596"},{"key":"e_1_2_7_19_2","doi-asserted-by":"crossref","unstructured":"XuY. ZhangY. andChuC. FastRoute 4.0: global router with efficient via minimization ASP-DAC Asia and South Pacific Design Automation Conference (ASP-DAC \u203209) January 2009 576\u2013581 2-s2.0-64549091868 https:\/\/doi.org\/10.1109\/ASPDAC.2009.4796542.","DOI":"10.1109\/ASPDAC.2009.4796542"},{"key":"e_1_2_7_20_2","unstructured":"http:\/\/www.ispd.cc\/contests\/ispd08rc.html."},{"key":"e_1_2_7_21_2","doi-asserted-by":"crossref","unstructured":"WuT. H. DavoodiA. andLinderothJ. T. GRIP: scalable 3D global routing using integer programming Proceedings of the 46th ACM\/IEEE Design Automation Conference (DAC \u203209) July 2009 320\u2013325 2-s2.0-70350706092.","DOI":"10.1145\/1629911.1629999"},{"key":"e_1_2_7_22_2","doi-asserted-by":"crossref","unstructured":"ChuC. FLUTE: fast lookup table based wirelength estimation technique Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design Digest of Technical Papers (ICCAD \u203204) November 2004 696\u2013701 2-s2.0-16244366458.","DOI":"10.1109\/ICCAD.2004.1382665"},{"key":"e_1_2_7_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907068"},{"key":"e_1_2_7_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_7_25_2","volume-title":"CRC Standard Curves and Surfaces","author":"von Seggern D.","year":"1993"}],"container-title":["VLSI Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/archive\/2012\/608362.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/archive\/2012\/608362.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2012\/608362","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T19:03:26Z","timestamp":1743966206000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2012\/608362"}},"subtitle":[],"editor":[{"given":"Rached","family":"Tourki","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1155\/2012\/608362"],"URL":"https:\/\/doi.org\/10.1155\/2012\/608362","archive":["Portico"],"relation":{},"ISSN":["1065-514X","1563-5171"],"issn-type":[{"value":"1065-514X","type":"print"},{"value":"1563-5171","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2012-02-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-04-10","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-08-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"608362"}}