Routing congestion estimation with real design constraints

Wen Hao Liu, Yaoguang Wei, Cliff Sze, Charles J. Alpert, Zhuo Li, Yih-Lang Li, Natarajan Viswanathan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

13 Scopus citations


To address the routability issue, routing congestion estimators (RCE) become essential in industrial design flow. Recently, several RCEs [1-4] based on global routing engines are developed, but they typically ignore the effects of routing on timing so that the identified routing paths may be overlong and thus impractical. To be aware of the timing issues, our proposed global-routing-based RCE obeys the layer directive and scenic constraints to respectively limit the routing layers and the maximum routing wirelength of the potentially timing-critical nets. To handle the scenic constrains, we propose a novel method based on a relaxation-legalization scheme. Also, because the work in [5] reveals that congestion ratio is a better indicator than overflow to evaluate routability, this work focuses on minimizing the congestion ratio rather than overflows. As will be shown, the problem of minimizing congestion ratio is more complicated than minimizing overflows, so we develop a new rip-up and rerouting scheme to reduce congestion and further to approach a target congestion ratio. Moreover, to fit the demands of practical uses, this work presents a control utility to trade off runtime and quality, which is an essential function to an industrial RCE tool. Experiments reveal that the proposed RCE is faster and more accurate than another industrial global-routing-based RCE.

Original languageEnglish
Title of host publicationProceedings of the 50th Annual Design Automation Conference, DAC 2013
StatePublished - 12 Jul 2013
Event50th Annual Design Automation Conference, DAC 2013 - Austin, TX, United States
Duration: 29 May 20137 Jun 2013

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X


Conference50th Annual Design Automation Conference, DAC 2013
Country/TerritoryUnited States
CityAustin, TX


  • Congestion estimation
  • Global routing
  • Routability


Dive into the research topics of 'Routing congestion estimation with real design constraints'. Together they form a unique fingerprint.

Cite this