Article

How accurately can we model timing in a placement engine?

Authors:

Bill HalpinAuthors Info & Claims

DAC '05: Proceedings of the 42nd annual Design Automation Conference

Pages 801 - 806

https://doi.org/10.1145/1065579.1065792

Published: 13 June 2005 Publication History

Get Access

Abstract

This paper presents a novel placement algorithm for timing optimization based on a new and powerful concept, which we term differential timing analysis. Recognizing that accurate optimization requires timing information from a signoff static timing analyzer, we propose an incremental placement algorithm that uses timing information from a signoff static timing engine. We propose a set of differential timing analysis equations that accurately capture the effect of placement perturbations on changes in timing from the signoff timer. We have formulated an incremental placement optimization problem based on differential timing analysis as a single linear programming (LP) problem which is solved to generate the new timing-optimized placement.Our experiments show that the worst negative slack (WNS) improves by an average of 30% and the total negative slack (TNS) improves by 33% on average for a set of circuits from a 3.0 GHz microprocessor that were already synthesized and placed by a leading industrial physical synthesis tool. We also show that multiple iterations of our engine give further TNS improvements - an average improvement of 51%, which implies that our placer will significantly speed up timing convergence.

References

[1]

W. C. Elmore, "The transient response of Damped Linear network with particular regard to wideband amplifier", Journal of Applied Physics, pp.55--63, 1948.

Crossref

Google Scholar

[2]

ILOG, ILOG CPLEX 8.0 User's Manual. ILOG, 2002.

Google Scholar

[3]

B. Halpin, C. Y. R. Chen, N. Sehgal, "Timing driven placement using physical net constraints", Proc. Design Automation Conf., pp. 780--783, 2001.

Digital Library

Google Scholar

[4]

K. Rajagopal, T. Shaked, Y. Parasuram, T. Cao, A. Chowdhary, B. Halpin, "Force directed timing driven placement with physical net constraints", Proc. Intl Symp. on Physical Design, pp. 147--152, 2003.

Digital Library

Google Scholar

[5]

A.H. Ajami, M. Pedram, "Post-layout timing driven cell placement using an accurate net length model", Proc. Design Automation Conf., pp. 595--600, 2001.

Digital Library

Google Scholar

[6]

A. B. Kahng, S. Mantik, I. L. Markov, "Min-max placement for large-scale timing optimization'', Proc. Intl. Symp. of Physical Design, pp. 143--148, 2002.

Digital Library

Google Scholar

[7]

W.Choi, K.Bazargan, "Incremental Placement for Timing Optimization", Proc. Intl Conf. on CAD, 2003.

Digital Library

Google Scholar

[8]

C.-C. Chang, J.Cong, M. Xie, "Optimality and scalability study of existing placement algorithms", Proc. of the ASP-DAC, Jan. 2003.

Digital Library

Google Scholar

Cited By

View all

Liao PGuo DGuo ZLiu SLin YYu B(2023)DREAMPlace 4.0: Timing-Driven Placement With Momentum-Based Net Weighting and Lagrangian-Based RefinementIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.324013242:10(3374-3387)Online publication date: Oct-2023
https://doi.org/10.1109/TCAD.2023.3240132
Liao PLiu SChen ZLv WLin YYu B(2022)DREAMPlace 4.0: Timing-driven Global Placement with Momentum-based Net Weighting2022 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE54114.2022.9774725(939-944)Online publication date: 14-Mar-2022
https://doi.org/10.23919/DATE54114.2022.9774725
Chen WHuang HWei MZou PChen J(2022)Virtual-Path-Based Timing Optimization for VLSI Global Placement2022 IEEE 16th International Conference on Solid-State & Integrated Circuit Technology (ICSICT)10.1109/ICSICT55466.2022.9963291(1-3)Online publication date: 25-Oct-2022
https://doi.org/10.1109/ICSICT55466.2022.9963291
Show More Cited By

Index Terms

How accurately can we model timing in a placement engine?
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Recommendations

Accurate timing prediction at placement stage with look-ahead RC network
DAC '22: Proceedings of the 59th ACM/IEEE Design Automation Conference

Timing closure is a critical but effort-taking task in VLSI designs. In placement stage, a fast and accurate net delay estimator is highly desirable to guide the timing optimization prior to routing, and thus reduce the timing pessimism and shorten the ...
Machine Learning-Based Pre-Routing Timing Prediction with Reduced Pessimism
DAC '19: Proceedings of the 56th Annual Design Automation Conference 2019

Optimizations at placement stage need to be guided by timing estimation prior to routing. To handle timing uncertainty due to the lack of routing information, people tend to make very pessimistic predictions such that performance specification can be ...
Timing-Driven Placement Based on Dynamic Net-Weighting for Efficient Slack Histogram Compression
ISPD '15: Proceedings of the 2015 Symposium on International Symposium on Physical Design

Timing-driven placement (TDP) finds new legal locations for standard cells so as to minimize timing violations while preserving placement quality. Although violations may arise from unmet setup or hold constraints, most TDP approaches ignore the latter. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '05: Proceedings of the 42nd annual Design Automation Conference

June 2005

984 pages

ISBN:1595930582

DOI:10.1145/1065579

General Chair:
William H. Joyner
IBM Corp./SRC
,
Program Chairs:
Grant E. Martin
Tensilica, Inc.
,
Andrew B. Kahng
University of California at San Diego, CA

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

DAC05

Sponsor:

DAC05: The 42nd Annual Design Automation Conference 2005

June 13 - 17, 2005

California, Anaheim, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
499
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)3

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liao PGuo DGuo ZLiu SLin YYu B(2023)DREAMPlace 4.0: Timing-Driven Placement With Momentum-Based Net Weighting and Lagrangian-Based RefinementIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.324013242:10(3374-3387)Online publication date: Oct-2023
https://doi.org/10.1109/TCAD.2023.3240132
Liao PLiu SChen ZLv WLin YYu B(2022)DREAMPlace 4.0: Timing-driven Global Placement with Momentum-based Net Weighting2022 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE54114.2022.9774725(939-944)Online publication date: 14-Mar-2022
https://doi.org/10.23919/DATE54114.2022.9774725
Chen WHuang HWei MZou PChen J(2022)Virtual-Path-Based Timing Optimization for VLSI Global Placement2022 IEEE 16th International Conference on Solid-State & Integrated Circuit Technology (ICSICT)10.1109/ICSICT55466.2022.9963291(1-3)Online publication date: 25-Oct-2022
https://doi.org/10.1109/ICSICT55466.2022.9963291
Kahng ALienig JMarkov IHu JKahng ALienig JMarkov IHu J(2022)Timing ClosureVLSI Physical Design: From Graph Partitioning to Timing Closure10.1007/978-3-030-96415-3_8(223-267)Online publication date: 15-Jun-2022
https://doi.org/10.1007/978-3-030-96415-3_8
Mangiras DDimitrakopoulos G(2021)Incremental Lagrangian Relaxation based Discrete Gate Sizing and Threshold Voltage Assignment2021 10th International Conference on Modern Circuits and Systems Technologies (MOCAST)10.1109/MOCAST52088.2021.9493338(1-5)Online publication date: 5-Jul-2021
https://doi.org/10.1109/MOCAST52088.2021.9493338
Mangiras DStefanidis ASeitanidis INicopoulos CDimitrakopoulos G(2020)Timing-Driven Placement Optimization Facilitated by Timing-Compatibility Flip-Flop ClusteringIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.294200139:10(2835-2848)Online publication date: Oct-2020
https://doi.org/10.1109/TCAD.2019.2942001
Lee TLi Y(2019)Incremental Timing-Driven Placement With Approximated Signoff Wire Delay and Regression-Based Cell DelayIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2019.291525427:10(2434-2446)Online publication date: Oct-2019
https://doi.org/10.1109/TVLSI.2019.2915254
Wang CSun YHu SJiang LQian W(2018)Variation-Aware Global Placement for Improving Timing-Yield of Carbon-Nanotube Field Effect Transistor CircuitACM Transactions on Design Automation of Electronic Systems10.1145/317550023:4(1-27)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3175500
Dhar SIyer MAdya SSinghal LRubanov NPan DOzdal MChu C(2017)An Effective Timing-Driven Detailed Placement Algorithm for FPGAsProceedings of the 2017 ACM on International Symposium on Physical Design10.1145/3036669.3036682(151-157)Online publication date: 19-Mar-2017
https://dl.acm.org/doi/10.1145/3036669.3036682
Netto RLivramento VGuth Cdos Santos LGüntzel Jde Lima Monteiro DTorres FIndrusiak L(2016)Evaluating the impact of circuit legalization on incremental optimization techniquesProceedings of the 29th Symposium on Integrated Circuits and Systems Design: Chip on the Mountains10.5555/3145862.3145867(1-6)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.5555/3145862.3145867
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Accurate timing prediction at placement stage with look-ahead RC network

Machine Learning-Based Pre-Routing Timing Prediction with Reduced Pessimism

Timing-Driven Placement Based on Dynamic Net-Weighting for Efficient Slack Histogram Compression