skip to main content
10.1145/1055137.1055166acmconferencesArticle/Chapter ViewAbstractPublication PagesispdConference Proceedingsconference-collections
Article

An efficient technology mapping algorithm targeting routing congestion under delay constraints

Published: 03 April 2005 Publication History

Abstract

Routing congestion has become a serious concern in today's VLSI designs. In this paper, we propose a technology mapping algorithm that minimizes routing congestion under delay constraints. 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 by 44%, on an average, as compared to the conventional technology mapping while satisfying delay constraints.

References

[1]
G. E. Moore. Cramming more components onto integrated circuits. In Electronics, pages 114--117, April 1965.
[2]
P. Saxena, N. Menezes, P. Cocchini, and D. A. Kirkpatrick. Repeater scaling and its impact on CAD. IEEE Trans. CAD, 23(4):451--463, April 2004.
[3]
P. Kapur, G. Chandra, and K. C. Saraswat. Power estimation in global interconnects and its reduction using a novel repeater insertion methodology. In Proc. DAC, pages 461--466, June 2002.
[4]
K. Keutzer. DAGON: Technology binding and local optimization by DAG matching. In Proc. DAC, pages 341--347, June 1987.
[5]
K. Chaudhary and M. Pedram. A near optimal algorithm for technology mapping minimizing area under delay constraints. In Proc. DAC, pages 492--498, June 1992.
[6]
Y. Kukimoto, R. K. Brayton, and P. Sawkar. Delay-optimal technology mapping by DAG covering. In Proc. DAC, pages 348--351, June 1998.
[7]
J. Y. Lin, A. Jagannathan, and J. Cong. Placement-driven technology mapping for LUT-Based FPGA's. In Proc. ISFPGA, pages 121--126, February 2003.
[8]
D. Pandini, L. T. Pileggi, and A. J. Strojwas. Congestion aware logic synthesis. In Proc. DATE, pages 664--671, March 2002.
[9]
D. Pandini, L. T. Pileggi, and A. J. Strojwas. Global and local congestion optimization in technology mapping. IEEE Trans. CAD, 22(4):498--505, April 2003.
[10]
L. Stok and T. Kutzschebauch. Congestion aware layout driven logic synthesis. In Proc. ICCAD, pages 216--223, November 2001.
[11]
R. Shelar, S. Sapatnekar, P. Saxena, and X. Wang. A predictive distributed congestion metric and its application to technology mapping. In Proc. ISPD, pages 210--217, April 2004.
[12]
Q. Liu and M. Marek-Sadowska. Technology mapping with pre-layout wirelength prediction. In Proc. IWLS, June 2004.
[13]
P. Kudva, A. Sullivan, and W. Dougherty. Metrics for structural logic synthesis. In Proc. ICCAD, pages 551--556, November 2002.
[14]
Q. Liu and M. Marek-Sadowska. Pre-layout wirelength and congestion estimation. In Proc. DAC, pages 582--587, June 2004.
[15]
M. Pedram and N. Bhat. Layout driven technology mapping. In Proc. DAC, pages 99--105, June 1991.
[16]
E. M. Sentovich et al. SIS: A system for sequential circuit synthesis. Memorandum No. UCB/ERL M92/41, May 1992.
[17]
J. Westra, C. Bartels, and P. Groeneveld. Probabilistic congestion prediction. In Proc. ISPD, pages 204--209, April 2004.
[18]
W-J. Dai. Hierarchial physical design methodology for multi-million gate chips. In Proc. ISPD, pages 179--181, April 2001.
[19]
J. Lou, S. Thakur, S. Krishnamoorthy, and H. S. Sheng. Estimating routing congestion using probabilistic analysis. IEEE Trans. CAD, 21(1):32--41, January 2002.
[20]
Berkeley predictive technology model. http://www-device.eecs.berkeley.edu/~ptm/download.html.
[21]
A. E. Caldwell, A. B. Kahng, and I. L. Markov. Can recursive bisection alone produce routable placements? In Proc. DAC, pages 477--482, June 2000.
[22]
J. Hu and S. Sapatnekar. A timing-constrained simultaneous global routing algorithm. IEEE Trans. CAD, 21(9):1025--1036, September 2002.

Cited By

View all
  • (2010)TRECOProceedings of the 2010 Asia and South Pacific Design Automation Conference10.5555/1899721.1899792(331-336)Online publication date: 18-Jan-2010
  • (2010)Logical and physical restructuring of fan-in treesProceedings of the 19th international symposium on Physical design10.1145/1735023.1735046(67-74)Online publication date: 14-Mar-2010
  • (2010)ECO timing optimization using spare cells and technology remappingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.204357329:5(697-710)Online publication date: 1-May-2010
  • Show More Cited By

Index Terms

  1. An efficient technology mapping algorithm targeting routing congestion under delay constraints

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      ISPD '05: Proceedings of the 2005 international symposium on Physical design
      April 2005
      258 pages
      ISBN:1595930213
      DOI:10.1145/1055137
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 03 April 2005

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. logic synthesis
      2. routing congestion
      3. technology mapping

      Qualifiers

      • Article

      Conference

      ISPD05
      Sponsor:
      ISPD05: International Symposium on Physical Design 2005
      April 3 - 6, 2005
      California, San Francisco, USA

      Acceptance Rates

      Overall Acceptance Rate 62 of 172 submissions, 36%

      Upcoming Conference

      ISPD '25
      International Symposium on Physical Design
      March 16 - 19, 2025
      Austin , TX , USA

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)10
      • Downloads (Last 6 weeks)3
      Reflects downloads up to 12 Jan 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2010)TRECOProceedings of the 2010 Asia and South Pacific Design Automation Conference10.5555/1899721.1899792(331-336)Online publication date: 18-Jan-2010
      • (2010)Logical and physical restructuring of fan-in treesProceedings of the 19th international symposium on Physical design10.1145/1735023.1735046(67-74)Online publication date: 14-Mar-2010
      • (2010)ECO timing optimization using spare cells and technology remappingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.204357329:5(697-710)Online publication date: 1-May-2010
      • (2010)TRECO: Dynamic technology remapping for timing Engineering Change Orders2010 15th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2010.5419874(331-336)Online publication date: Jan-2010
      • (2008)On the decreasing significance of large standard cells in technology mappingProceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design10.5555/1509456.1509492(116-121)Online publication date: 10-Nov-2008
      • (2008)SynECO: Incremental technology mapping with constrained placement and fast detail routing for predictable timing improvement2008 IEEE International Conference on Computer Design10.1109/ICCD.2008.4751915(551-556)Online publication date: Oct-2008
      • (2008)A dynamic accuracy-refinement approach to timing-driven technology mapping2008 IEEE International Conference on Computer Design10.1109/ICCD.2008.4751913(538-543)Online publication date: Oct-2008
      • (2008)On the decreasing significance of large standard cells in technology mapping2008 IEEE/ACM International Conference on Computer-Aided Design10.1109/ICCAD.2008.4681561(116-121)Online publication date: Nov-2008
      • (2007)Algorithms to simplify multi-clock/edge timing constraints2007 25th International Conference on Computer Design10.1109/ICCD.2007.4601937(444-449)Online publication date: Oct-2007
      • (2006)Technology mapping algorithm targeting routing congestion under delay constraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2006.87007825:4(625-636)Online publication date: 1-Nov-2006
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media