Technology mapping algorithm targeting routing congestion under delay constraints

Rupesh S. Shelar, Prashant Saxena, Sachin S. Sapatnekar

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


Routing congestion has become a serious concern in today's very-large-scale-integration designs. To address this, the authors propose a technology mapping algorithm that minimizes routing congestion under delay constraints in this paper. The algorithm employs a dynamic-programming framework in the matching phase to generate probabilistic congestion maps for all the matches. These congestion maps are then utilized to minimize routing congestion during the covering, which preserves the delay optimality of the solution using the notion of slack. Experimental results on benchmark circuits in a 100-nm technology show that the algorithm can improve track overflows significantly as compared to conventional technology mapping while satisfying delay constraints.

Original languageEnglish (US)
Pages (from-to)625-635
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number4
StatePublished - Apr 2006

Bibliographical note

Funding Information:
Manuscript received June 23, 2005; revised September 14, 2005. This work was supported in part by the Semiconductor Research Consortium (SRC) under Contract 2002-TJ-1092 and by the National Science Foundation (NSF) under Grant CCR-0098117. It was carried out at the Strategic Computer-Aided Design Laboratories, Intel Corporation, and at the Department of Electrical and Computer Engineering, University of Minnesota. This paper was presented in part at the International Symposium on Physical Design, San Francisco, CA, April 2005. This paper was recommended by Associate Editor L. Scheffer.


  • Congestion estimation
  • Delay minimization
  • Logic synthesis
  • Physical design
  • Physical synthesis
  • Placement
  • Routing congestion
  • Technology mapping


Dive into the research topics of 'Technology mapping algorithm targeting routing congestion under delay constraints'. Together they form a unique fingerprint.

Cite this