{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:47:45Z","timestamp":1759146465932,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,3,1]],"date-time":"2014-03-01T00:00:00Z","timestamp":1393632000000},"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":[[2014,3]]},"abstract":"<jats:p>Routing congestion has become a critical layout challenge in nanoscale circuits since it is a critical factor in determining the routability of a design. An unroutable design is not useful even though it closes on all other design metrics. Fast design closure can only be achieved by accurately evaluating whether a design is routable or not early in the design cycle. Lately, it has become common to use a \u201clight mode\u201d version of a global router to quickly evaluate the routability of a given placement. This approach suffers from three weaknesses: (i) it does not adequately model local routing resources, which can cause incorrect routability predictions that are only detected late, during detailed routing; (ii) the congestion maps obtained by it tend to have isolated hotspots surrounded by noncongested spots, called \u201cnoisy hotspots\u201d, which further affects the accuracy in routability evaluation; and (iii) the metrics used to represent congestion may yield numbers that do not provide sufficient intuition to the designer, and moreover, they may often fail to predict the routability accurately. This article presents solutions to these issues. First, we propose three approaches to model local routing resources. Second, we propose a smoothing technique to reduce the number of noisy hotspots and obtain a more accurate routability evaluation result. Finally, we develop a new metric which represents congestion maps with higher fidelity. We apply the proposed techniques to several industrial circuits and demonstrate that one can better predict and evaluate design routability and that congestion mitigation tools can perform much better to improve the design routability.<\/jats:p>","DOI":"10.1145\/2566663","type":"journal-article","created":{"date-parts":[[2014,3,24]],"date-time":"2014-03-24T13:45:50Z","timestamp":1395668750000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Techniques for scalable and effective routability evaluation"],"prefix":"10.1145","volume":"19","author":[{"given":"Yaoguang","family":"Wei","sequence":"first","affiliation":[{"name":"University of Minnesota, Minneapolis, MN"}]},{"given":"Cliff","family":"Sze","sequence":"additional","affiliation":[{"name":"IBM Austin Research Laboratory, Austin, TX"}]},{"given":"Natarajan","family":"Viswanathan","sequence":"additional","affiliation":[{"name":"IBM Systems and Technology Group, Austin, TX"}]},{"given":"Zhuo","family":"Li","sequence":"additional","affiliation":[{"name":"IBM Austin Research Laboratory, Austin, TX"}]},{"given":"Charles J.","family":"Alpert","sequence":"additional","affiliation":[{"name":"IBM Austin Research Laboratory, Austin, TX"}]},{"given":"Lakshmi","family":"Reddy","sequence":"additional","affiliation":[{"name":"IBM Systems and Technology Group, Hopewell Junction, NY"}]},{"given":"Andrew D.","family":"Huber","sequence":"additional","affiliation":[{"name":"IBM Systems and Technology Group, Hopewell Junction, NY"}]},{"given":"Gustavo E.","family":"Tellez","sequence":"additional","affiliation":[{"name":"IBM Systems and Technology Group, Burlington, VT"}]},{"given":"Douglas","family":"Keller","sequence":"additional","affiliation":[{"name":"IBM Systems and Technology Group, Hopewell Junction, NY"}]},{"given":"Sachin S.","family":"Sapatnekar","sequence":"additional","affiliation":[{"name":"University of Minnesota, Minneapolis, MN"}]}],"member":"320","published-online":{"date-parts":[[2014,3,28]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"C. J. Alpert and G. E. Tellez. 2010. The importance of routing congestion analysis. DAC Knowledge Center Online Article. http:\/\/www.dac.com\/back&bsol;_end&plus;topics.aspx&quest;article=47&topic=2.  C. J. Alpert and G. E. Tellez. 2010. The importance of routing congestion analysis. DAC Knowledge Center Online Article. http:\/\/www.dac.com\/back&bsol;_end&plus;topics.aspx&quest;article=47&topic=2."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735023.1735028"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"C.\n      Ans\u00f3tegui M.\n      Sellmann and \n      K.\n      Tierney\n  . \n  2009\n  . A gender-based genetic algorithm for the automatic configuration of algorithms. In Principles and Practice of Constraint Programming Lecture Notes in Computer Science vol. \n  5732 Springer Berlin 142--157.   C. Ans\u00f3tegui M. Sellmann and K. Tierney. 2009. A gender-based genetic algorithm for the automatic configuration of algorithms. In Principles and Practice of Constraint Programming Lecture Notes in Computer Science vol. 5732 Springer Berlin 142--157.","DOI":"10.1007\/978-3-642-04244-7_14"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2188385.2188395"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/505388.505391"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055137.1055177"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1509456.1509536"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735023.1735052"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1326073.1326247"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1509633.1509769"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391651"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.923063"},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. IEEE","author":"Cho M.","key":"e_1_2_1_13_1","unstructured":"M. Cho , K. Lu , K. Yuan , and D. Z. Pan . 2007. BoxRouter 2.0: Architecture and implementation of a hybrid and robust global router . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. IEEE , Los Alamitos, CA, 503--508. M. Cho, K. Lu, K. Yuan, and D. Z. Pan. 2007. BoxRouter 2.0: Architecture and implementation of a hybrid and robust global router. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. IEEE, Los Alamitos, CA, 503--508."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233501.1233599"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907068"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2011.02.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228441"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442087.2442103"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2132325.2132347"},{"volume-title":"Fast surface particle repulsion. Tech. rep. CMU-CS-97-130","author":"Heckbert P.","key":"e_1_2_1_20_1","unstructured":"P. Heckbert . 1997. Fast surface particle repulsion. Tech. rep. CMU-CS-97-130 . Carnegie Mellon University , Pittsburgh, PA . P. Heckbert. 1997. Fast surface particle repulsion. Tech. rep. CMU-CS-97-130. Carnegie Mellon University, Pittsburgh, PA."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2132325.2132348"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488920"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391513"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.846366"},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. IEEE","author":"Kim M.-C.","key":"e_1_2_1_25_1","unstructured":"M.-C. Kim , J. Hu , D.-J. Lee , and I. L. Markov . 2011. A SimPLR method for routability-driven placement . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. IEEE , Los Alamitos, CA, 67--73. M.-C. Kim, J. Hu, D.-J. Lee, and I. L. Markov. 2011. A SimPLR method for routability-driven placement. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. IEEE, Los Alamitos, CA, 67--73."},{"key":"e_1_2_1_26_1","first-page":"144","article-title":"High performance post-placement length estimation techniques","volume":"1","author":"Li Y.","year":"2012","unstructured":"Y. Li , A. Farshidi , L. Behjat , and W. Swartz . 2012 . High performance post-placement length estimation techniques . Int. J. Inform. Comput. Sci. 1 , 6, 144 -- 152 . Y. Li, A. Farshidi, L. Behjat, and W. Swartz. 2012. High performance post-placement length estimation techniques. Int. J. Inform. Comput. Sci. 1, 6, 144--152.","journal-title":"Int. J. Inform. Comput. Sci."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.974135"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.2006082"},{"key":"e_1_2_1_29_1","unstructured":"W. C. Naylor R. Donelly and L. Sha. 2003. Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer. U.S. Patent 6671859 Bl.  W. C. Naylor R. Donelly and L. Sha. 2003. Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer. U.S. Patent 6671859 Bl."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/66.999598"},{"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.1145\/1278480.1278496"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1687399.1687467"},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. IEEE","author":"Shojaei H.","key":"e_1_2_1_34_1","unstructured":"H. Shojaei , A. Davoodi , and J. T. Linderoth . 2011. Congestion analysis for global routing via integer programming . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. IEEE , Los Alamitos, CA, 256--262. H. Shojaei, A. Davoodi, and J. T. Linderoth. 2011. Congestion analysis for global routing via integer programming. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. IEEE, Los Alamitos, CA, 256--262."},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. IEEE","author":"Taghavi T.","key":"e_1_2_1_35_1","unstructured":"T. Taghavi , C. Alpert , A. Huber , Z. Li , G.-J. Nam , and S. Ramji . 2010. New placement prediction and mitigation techniques for local routing congestion . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. IEEE , Los Alamitos, CA, 621--624. T. Taghavi, C. Alpert, A. Huber, Z. Li, G.-J. Nam, and S. Ramji. 2010. New placement prediction and mitigation techniques for local routing congestion. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. IEEE, Los Alamitos, CA, 621--624."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.931037"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228500"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1960397.1960429"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735023.1735051"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228499"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/981066.981110"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837323"},{"volume-title":"Proceedings of the Asia-South Pacific Design Automation Conference. IEEE","author":"Xu Y.","key":"e_1_2_1_43_1","unstructured":"Y. Xu , Y. Zhang , and C. Chu . 2009. FastRoute 4.0: Global router with efficient via minimization . In Proceedings of the Asia-South Pacific Design Automation Conference. IEEE , Los Alamitos, CA, 576--581. Y. Xu, Y. Zhang, and C. Chu. 2009. FastRoute 4.0: Global router with efficient via minimization. In Proceedings of the Asia-South Pacific Design Automation Conference. IEEE, Los Alamitos, CA, 576--581."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1960397.1960410"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228469"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2566663","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2566663","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:01Z","timestamp":1750230061000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2566663"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["10.1145\/2566663"],"URL":"https:\/\/doi.org\/10.1145\/2566663","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2014,3]]},"assertion":[{"value":"2012-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}