More Web Proxy on the site http://driver.im/

Article

Addressing the timing closure problem by integrating logic optimization and placement

Authors:

Sunil P. Khatri,

Alberto L. Sangiovanni-VincentelliAuthors Info & Claims

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

Pages 224 - 231

Published: 04 November 2001 Publication History

Abstract

Timing closure problems occur when timing estimates computed during logic synthesis do not match with timing estimates computed from the layout of the circuit. In such a situation, logic synthesis and layout synthesis are iterated until the estimates match. The number of such iterations is becoming larger as technology scales. Timing closure problems occur mainly due to the difficulty in accurately predicting interconnect delay during logic synthesis.In this paper, we present an algorithm that integrates logic synthesis and global placement to address the timing closure problem. We introduce technology independent algorithms as well as technology dependent algorithms. Our technology independent algorithms are based on the notion of "wire-planning". All these algorithms interleave their logic operations with local and incremental/full global placement, in order to maintain a consistent placement while the algorithm is run. We show that by integrating logic synthesis and placement, we avoid the need to predict interconnect delay during logic synthesis. We demonstrate that our scheme significantly enhances the predictability of wire delays, thereby solving the timing closure problem. This is the main result of our paper. Our results also show that our algorithms result in a significant reduction in total circuit delay. In addition, our technology independent algorithms result in a significant circuit area reduction.

References

[1]

Cadence Design Systems, Inc., 555 River Oaks Parkway, San Jose, CA 95134. Envisia Silicon Ensemble Place-and-route Reference, Nov 1999.

[2]

K. Doll, F.M. Johannes, and G. Sigl. Domino: deterministic placement improvement with hill-climbing capabilities. Proceedings of the IFIP International Conference on VLSI, pages 91-100, Aug 1991.

[3]

H. Eisenmann and F.M. Johannes. Generic global placement and floor-planning. In DAC, pages 269-274, June 1998.

Digital Library

[4]

W. C. Elmore. The transient analysis of damped linear networks with particular regard to wideband amplifiers. J. Applied Physics, (19):55-63, 1948.

[5]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, 1979.

Digital Library

[6]

W. Gosti, A. Narayan, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. Wireplanning in logic synthesis. In ICCAD, pages 26-33, Nov 1998.

Digital Library

[7]

K. Keutzer. DAGON: Technology binding and local optimization by dac matching. In DAC, pages 228-234, 1990.

[8]

S Khatri, A Mehrotra, R Brayton, A Sangiovanni-Vincentelli, and R Otten. A novel VLSI layout fabric for deep sub-micron applications. In DAC, New Orleans, June 1999.

Digital Library

[9]

J.M. Kleinhans, G. Sigl, F.M. Johannes, and K.J. Antreich. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Trans on CAD, 10(3):356-365, March 1991.

Digital Library

[10]

J. Lou, W. Chen, and M. Pedram. Concurrent logic restructuring and placement for timing closure. In ICCAD, pages 31-35, November 1999.

Digital Library

[11]

J. Lou, A. H. Salek, and M. Pedram. An exact solution to simultaneous technology mapping and linear placement problem. In ICCAD, pages 671-675, November 1997.

Digital Library

[12]

M. Pedram and N. Bhat. Layout driven logic restructuring/decomposition. In ICCAD, pages 134-137, 1991.

[13]

M. Pedram and N. Bhat. Layout driven technology mapping. In DAC, pages 99-105, June 1991.

Digital Library

[14]

E. Sentovich, K. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. Stephan, R. Brayton, and A. Sangiovanni-Vincentelli. SIS: A System for Sequential Circuit Synthesis. Technical Report UCB/ERL M92/41, Univ. of CA, Berkeley, May 1992.

[15]

N. Shenoy, M. Iyer, R. Damiano, K. Harer, H. Ma, and P. Thilking. A robust solution to the timing convergence problem in high-performance design. In ICCD, pages 250-257, October 1999.

Digital Library

[16]

A. Srinivasan, K. Chaudhary, and E. S. Kuh. Ritual: a performance driven placement algorithm. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 39(11):825-840, November 1992.

[17]

G. Stenz, B. M. Riess, B. Rohfleisch, and F. M. Johannes. Timing Driven Placement in Interaction with Netlist Transformations. In ISPD, Napa Valley, CA, 1997.

Digital Library

[18]

Hervé J. Touati. Performance-Oriented Technology Mapping. PhD thesis, University of California Berkeley, Univ. of CA, Berkeley, November 1990. Memorandum No. UCB/ERL M90/109.

Digital Library

[19]

A. J. van Genderen and N. P. van der Meijs. Space user's manual, space tutorial, space 3d capacitance extraction user's manual. Technical report, Delft University of Technology, Dept of EE, Delft, The Netherlands, 1995.

Cited By

Amarú LVuillod PLuo JOlson J(2017)Logic optimization and synthesisProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130687(1303-1305)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130687
Qiu JReda SHassoun SReda SWang J(2010)Fast, accurate a priori routing delay estimationProceedings of the 12th ACM/IEEE international workshop on System level interconnect prediction10.1145/1811100.1811119(77-82)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1811100.1811119
Liu YShelar RHu JNassif SRoychowdhury J(2008)Delay-optimal simultaneous technology mapping and placement with applications to timing optimizationProceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design10.5555/1509456.1509489(101-106)Online publication date: 10-Nov-2008
https://dl.acm.org/doi/10.5555/1509456.1509489
Show More Cited By

Index Terms

Addressing the timing closure problem by integrating logic optimization and placement
1. Hardware

Recommendations

Concurrent logic restructuring and placement for timing closure
ICCAD '99: Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design

In this paper, an algorithm for simultaneous logic restructuring and placement is presented. This algorithm first constructs a set of super-cells along the critical paths and then generates the set of non-inferior re-mapping solutions for each ...
Congestion and timing optimization for standard-cell placement
Timing-driven cell placement optimization for early slack histogram compression
DAC '16: Proceedings of the 53rd Annual Design Automation Conference

As interconnects dominate circuit performance in modern chip designs, placement becomes an essential stage in optimizing timing. Recent timing-driven placement (TDP) techniques focus mainly on optimizing late slack rather than early slack. This paper ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 2001

656 pages

ISBN:0780372492

Conference Chair:
Rolf Ernst
Tech. Univ. of Braunschweig, Braunschweig, Germany

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE Circuits & Systems Society
The IEEE Computer Society DATC

Publisher

IEEE Press

Publication History

Published: 04 November 2001

Check for updates

Qualifiers

Article

Conference

ICCAD01

Sponsor:

SIGDA

ICCAD01: International Conference on Computer Aided Design

November 4 - 8, 2001

California, San Jose

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
283
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Amarú LVuillod PLuo JOlson J(2017)Logic optimization and synthesisProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130687(1303-1305)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130687
Qiu JReda SHassoun SReda SWang J(2010)Fast, accurate a priori routing delay estimationProceedings of the 12th ACM/IEEE international workshop on System level interconnect prediction10.1145/1811100.1811119(77-82)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1811100.1811119
Liu YShelar RHu JNassif SRoychowdhury J(2008)Delay-optimal simultaneous technology mapping and placement with applications to timing optimizationProceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design10.5555/1509456.1509489(101-106)Online publication date: 10-Nov-2008
https://dl.acm.org/doi/10.5555/1509456.1509489
Plaza SMarkov IBertacco VPan DNam G(2008)Optimizing non-monotonic interconnect using functional simulation and logic restructuringProceedings of the 2008 international symposium on Physical design10.1145/1353629.1353653(95-102)Online publication date: 13-Apr-2008
https://dl.acm.org/doi/10.1145/1353629.1353653
Kim HLillis JHrkić MQu GIsmail YNarayanan VZhou H(2006)Techniques for improved placement-coupled logic replicationProceedings of the 16th ACM Great Lakes symposium on VLSI10.1145/1127908.1127959(211-216)Online publication date: 30-Apr-2006
https://dl.acm.org/doi/10.1145/1127908.1127959
Kahng AReda S(2005)Intrinsic shortest path lengthProceedings of the 2005 IEEE/ACM International conference on Computer-aided design10.5555/1129601.1129627(173-180)Online publication date: 31-May-2005
https://dl.acm.org/doi/10.5555/1129601.1129627
Vujkovic MWadkins DSechen C(2005)Efficient post-layout power-delay curve generationProceedings of the 15th international conference on Integrated Circuit and System Design: power and Timing Modeling, Optimization and Simulation10.1007/11556930_41(393-403)Online publication date: 21-Sep-2005
https://dl.acm.org/doi/10.1007/11556930_41
Hrkić MLillis JBeraudo GMalik SFix LKahng A(2004)An approach to placement-coupled logic replicationProceedings of the 41st annual Design Automation Conference10.1145/996566.996761(711-716)Online publication date: 7-Jun-2004
https://dl.acm.org/doi/10.1145/996566.996761
Edman ASvensson CMalik SFix LKahng A(2004)Timing closure through a globally synchronous, timing partitioned design methodologyProceedings of the 41st annual Design Automation Conference10.1145/996566.996586(71-74)Online publication date: 7-Jun-2004
https://dl.acm.org/doi/10.1145/996566.996586
Chatterjee SBrayton R(2004)A new incremental placement algorithm and its application to congestion-aware divisor extractionProceedings of the 2004 IEEE/ACM International conference on Computer-aided design10.1109/ICCAD.2004.1382637(541-548)Online publication date: 7-Nov-2004
https://dl.acm.org/doi/10.1109/ICCAD.2004.1382637
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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents