Article

Incremental Placement for Timing Optimization

Authors:

Wonjoon Choi,

Kia BazarganAuthors Info & Claims

ICCAD '03: Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design

Page 463

Published: 09 November 2003 Publication History

Get Access

Abstract

An incremental timing driven placement algorithm is presented.We introduce a fast path-based analytical approach for timingimprovement. Our method achieves timing optimization byreducing the enclosing bounding boxes of selected nets oncritical paths. Furthermore, this technique tries to minimizemodifications to the initial placement while improving the delayof the circuit incrementally. Two contributions of this work are1) efficient conversion of a path-based timing minimizationproblem to a geometric net-constraint problem and 2) minimalmodification of a placement to improve timing. Our techniquecan take an initial placement from any algorithm and improvetiming iteratively. The experiments show that the proposedapproach is very efficient.

References

[1]

{1} H. Eisenmann and F. M. Johannes, "Generic Global Placement and Floorplanning", ACM/IEEE Design Automation Conference, 1998.

Digital Library

Google Scholar

[2]

{2} B. Halpin, C. Y. roger Chen, and Naresh Sehgal, "Timing Driven Placement using Physical Net Constraints", Design Automation Conference, pp. 780-783. IEEE/ACM, June 2001.

Digital Library

Google Scholar

[3]

{3} K. Rajagopal et al., "Timing Driven Force Directed placement with Physical Net Constraints", International Symposium on Physical Design, pp. 60-66. IEEE/ACM, April 2003.

Digital Library

Google Scholar

[4]

{4} A. H. Ajami and M. Pedram, "Post-Layout Timing-Driven Cell Placement Using an Accurate Net Length Model with Movable Steiner Points", ASPDAC, 2001

Digital Library

Google Scholar

[5]

{5} ftp://ftp.es.ele.tue.nl/pub/lp_solve/. Information and Communication Systems group at the Electrical Engineering department of the Eindhoven University of Technology, 1998.

Google Scholar

[6]

{6} http://www.cs.wisc.edu/~swright/ooqp/. University of Chicago, 2001

Google Scholar

[7]

{7} C. Ababei, N. Selvakkumaran, K. Bazargan, and G. Karypis, "Multi-objective Circuit Partitioning for Cutsize and Path-based Delay Minimization," ICCAD, 2002

Digital Library

Google Scholar

[8]

{8} X. Yang, B.K. Choi, and M. Sarrafzadeh, "Timing-Driven Placement using Design Hierarchy Guided Constraint Generation", ICCAD, 2002.

Digital Library

Google Scholar

Cited By

View all

Jung JNam GReddy LJiang IShin Y(2018)OWARUIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.277427737:9(1825-1838)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1109/TCAD.2017.2774277
Kim SDo SKang S(2017)Fast Predictive Useful Skew Methodology for Timing-Driven Placement OptimizationProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062247(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062247
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

Index Terms

Incremental Placement for Timing Optimization
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Paths and connectivity problems

Recommendations

Clock-Tree-Aware Incremental Timing-Driven Placement
Special Section on New Physical Design Techniques for the Next Generation Integration Technology and Regular Papers

The increasing impact of interconnections on overall circuit performance makes timing-driven placement (TDP) a crucial step toward timing closure. Current TDP techniques improve critical paths but overlook the impact of register placement on clock tree ...
Pulsed-latch aware placement for timing-integrity optimization
DAC '10: Proceedings of the 47th Design Automation Conference

Utilizing pulsed latches in a circuit is one emerging solution to timing improvements. Pulsed latches, driven by a brief clock signal generated from pulse generators, possess superior design parameters over flip-flops. If pulse generators and pulsed ...
Fast Predictive Useful Skew Methodology for Timing-Driven Placement Optimization
DAC '17: Proceedings of the 54th Annual Design Automation Conference 2017

Incremental timing-driven placement (TDP) is one of the most crucial steps for timing closure in a physical design. The need for high-performance incremental TDP continues to grow, but prior studies have focused on optimizing only setup timing slacks, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICCAD '03: Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design

November 2003

899 pages

ISBN:1581137621

Publisher

IEEE Computer Society

United States

Publication History

Published: 09 November 2003

Check for updates

Qualifiers

Article

Conference

ICCAD03

Sponsor:

SIGDA

ICCAD03: The International Conference on Computer-Aided Design

November 9 - 13, 2003

Acceptance Rates

ICCAD '03 Paper Acceptance Rate 129 of 490 submissions, 26%;

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
267
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jung JNam GReddy LJiang IShin Y(2018)OWARUIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.277427737:9(1825-1838)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1109/TCAD.2017.2774277
Kim SDo SKang S(2017)Fast Predictive Useful Skew Methodology for Timing-Driven Placement OptimizationProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062247(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062247
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
Agashiwala NUpadhyay SBazargan KChen DGreene J(2016)t-QuadPlaceProceedings of the 2016 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/2847263.2847306(284-284)Online publication date: 21-Feb-2016
https://dl.acm.org/doi/10.1145/2847263.2847306
Kim MHu JLi JViswanathan NMarculescu DLiu F(2015)ICCAD-2015 CAD Contest in Incremental Timing-driven Placement and Benchmark SuiteProceedings of the IEEE/ACM International Conference on Computer-Aided Design10.5555/2840819.2840949(921-926)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.5555/2840819.2840949
Livramento VGuth CNetto RGüntzel Jdos Santos LMarculescu DLiu F(2015)Exploiting Non-Critical Steiner Tree Branches for Post-Placement Timing OptimizationProceedings of the IEEE/ACM International Conference on Computer-Aided Design10.5555/2840819.2840893(528-535)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.5555/2840819.2840893
Bock AHeld SKämmerling NSchorr U(2015)Local search algorithms for timing-driven placement under arbitrary delay modelsProceedings of the 52nd Annual Design Automation Conference10.1145/2744769.2744867(1-6)Online publication date: 7-Jun-2015
https://dl.acm.org/doi/10.1145/2744769.2744867
Kim MHu JViswanathan NChang Y(2014)ICCAD-2014 CAD contest in incremental timing-driven placement and benchmark suiteProceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design10.5555/2691365.2691438(361-366)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.5555/2691365.2691438
Wei XTang WWu YSze CAlpert CBrunvard EStevens KCavallaro JZhang T(2012)WRIPProceedings of the great lakes symposium on VLSI10.1145/2206781.2206861(327-332)Online publication date: 3-May-2012
https://dl.acm.org/doi/10.1145/2206781.2206861
Dutt SRen HScheffer LPhillips JHu A(2010)Timing yield optimization via discrete gate sizing using globally-informed delay PDFsProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133549(570-577)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133549
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

Clock-Tree-Aware Incremental Timing-Driven Placement

Pulsed-latch aware placement for timing-integrity optimization

Fast Predictive Useful Skew Methodology for Timing-Driven Placement Optimization