Article

Accurate estimation of global buffer delay within a floorplan

Authors:

S. S. Sapatnekar,

C. N. SzeAuthors Info & Claims

ICCAD '04: Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design

Pages 706 - 711

https://doi.org/10.1109/ICCAD.2004.1382667

Published: 07 November 2004 Publication History

Abstract

Closed formed expressions for buffered interconnect delay approximation have been around for some time. However, previous approaches assume that buffers are free to be placed anywhere. In practice, designs frequently have large blocks that make the ideal buffer insertion solution unrealizable. The theory of Otten (1998) is extended to show how one can model the blocks into a simple delay estimation technique that applies both to two-pin and to multi-pin nets. Even though the formula uses one buffer type, it shows remarkable accuracy in predicting delay when compared to an optimal realizable buffer insertion solution. Potential applications include wire planning, timing analysis during floorplanning or global routing. Our experiments show that our approach accurately predicts delay when compared to constructing a realizable buffer insertion with multiple buffer types.

References

[1]

{1} C. J. Alpert and A. Devgan, "Wire segmenting for improved buffer insertion", ACM/IEEE DAC pp. 588-593, 1997.

Digital Library

[2]

{2} C. J. Alpert, G. Gandham, M. Hrkic, J. Hu, A. B. Kahng, J. Lillis, B. Liu, S. T. Quay, S. S. Sapatnekar and A. J. Sullivan, "Buffered Steiner trees for difficult instances", IEEE Transactions on CAD, 21(1):3-14, January 2002.

Digital Library

[3]

{3} C. C. N. Chu and D. F. Wong, "Closed form solution to simultaneous buffer insertion/sizing and wire sizing", ACM/IEEE Intl. Symposium on Physical Design, pp. 192-197, 1997.

Digital Library

[4]

{4} J. Cong, L. He, C.-K. Koh, and P. H. Madden, "Performance Optimization of VLSI Interconnect Layout", Integration: the VLSI Journal, 21, 1996, pp. 1-94.

Digital Library

[5]

{5} J. Cong, T. Kong, and D. Z. Pan, "Buffer block planning for interconnect-driven floorplanning", IEEE/ACM Conf. on Computer-Aided Design, pp. 358-363, 1999.

Digital Library

[6]

{6} J. Cong and D. Z. Pan, "Interconnect performance estimation models for design planning" IEEE Transactions on CAD, 20(6):739-752, June 2001.

Digital Library

[7]

{7} J. Cong and X. Yuan, "Routing tree construction under fixed buffer locations", ACM/IEEE DAC, pp. 379-384, 2000.

Digital Library

[8]

{8} S. Dhar and M. A. Franklin, "Optimum buffer circuits for driving long uniform lines", IEEE Journal of Solid State Circuits , 26(1):33-38, January 1991.

[9]

{9} W. C. Elmore, "The Transient Response of Damped Linear Network with Particular Regard to Wideband Amplifiers", J. Applied Physics, 19, 1948, pp. 55-63.

[10]

{10} M. Hrkic and J. Lillis, "Buffer tree synthesis with consideration of temporal locality, sink polarity requirements, solution cost and blockages", ACM/IEEE ISPD, pp. 98-103, 2002.

Digital Library

[11]

{11} J. Hu, C. J. Alpert, S. T. Quay and G. Gandham, "Buffer insertion with adaptive blockage avoidance", ACM/IEEE International Symposium on Physical Design, pp. 92-97, 2002.

Digital Library

[12]

{12} R. H. J. M. Otten, "Global Wires Harmful?", ACM/IEEE Intl. Symposium on Physical Design, pp. 104-109, 1998.

Digital Library

[13]

{13} P. Saxena, N. Menezes, P. Cocchini and D. A. Kirkpatrick, "The scaling challenge: can correct-by-construction design help?", ACM/IEEE ISPD, pp. 51-58, 2003.

Digital Library

[14]

{14} X. Tang, R. Tian, H. Xiang and D. F. Wong, "A new algorithm for routing tree construction with buffer insertion and wire sizing under obstacle constraints", IEEE/ACM International Conf. on Computer-Aided Design, pp. 49-56, 2001.

Digital Library

[15]

{15} L. P. P. P. van Ginneken, "Buffer Placement in Distributed RC-Tree Network for Minimal Elmore Delay", Intl Symp. on Circuits and Systems, pp. 865-868, 1990.

[16]

{16} C. J. Alpert, M. Hrkic, J. Hu, and S. T. Quay, "Fast and Flexible Buffer Trees that Navigate the Layout Environment", IEEE/ACM DAC, pp. 24-29, 2004.

Digital Library

Cited By

Krishna Kashyap SOzev S(2023)IMPRoVED: Integrated Method to Predict PostRouting setup Violations in Early Design StagesACM Transactions on Design Automation of Electronic Systems10.1145/357254628:4(1-23)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1145/3572546
Guo ZLiu MGu JZhang SPan DLin YOshana R(2022)A timing engine inspired graph neural network model for pre-routing slack predictionProceedings of the 59th ACM/IEEE Design Automation Conference10.1145/3489517.3530597(1207-1212)Online publication date: 10-Jul-2022
https://dl.acm.org/doi/10.1145/3489517.3530597
Barboza EShukla NChen YHu J(2019)Machine Learning-Based Pre-Routing Timing Prediction with Reduced PessimismProceedings of the 56th Annual Design Automation Conference 201910.1145/3316781.3317857(1-6)Online publication date: 2-Jun-2019
https://dl.acm.org/doi/10.1145/3316781.3317857
Show More Cited By

Recommendations

Accurate estimation of global buffer delay within a floorplan

Closed-form expressions for buffered interconnect delay approximation have been around for some time. However, previous approaches assume that buffers are free to be placed anywhere. In practice, designs frequently have large blocks that make the ideal ...
Floorplan Evaluation with Timing-Driven Global Wireplanning, Pin Assignment and Buffer/Wire Sizing
ASP-DAC '02: Proceedings of the 2002 Asia and South Pacific Design Automation Conference

We describe a new algorithm for floorplan evaluation using timing-driven buffered routing according to a prescribed buffer site map. Specifically, we describe a provably good multi-commodity flow based algorithm that finds a global routing minimizing ...
Congestion Estimation with Buffer Planning in Floorplan Design
DATE '02: Proceedings of the conference on Design, automation and test in Europe

In this paper, we study and implement a routability-drivenfloorplanner with buffer block planning. It evaluatesthe routability of a floorplan by computing the probabilitythat a net will pass through each particular locationof a floorplan taken into ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '04: Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design

November 2004

913 pages

ISBN:0780387023

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Computer Society

United States

Publication History

Published: 07 November 2004

Check for updates

Qualifiers

Article

Conference

ICCAD04

Sponsor:

SIGDA

ICCAD04: The International Conference on Computer-Aided Design 2004

November 7 - 11, 2004

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
103
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Krishna Kashyap SOzev S(2023)IMPRoVED: Integrated Method to Predict PostRouting setup Violations in Early Design StagesACM Transactions on Design Automation of Electronic Systems10.1145/357254628:4(1-23)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1145/3572546
Guo ZLiu MGu JZhang SPan DLin YOshana R(2022)A timing engine inspired graph neural network model for pre-routing slack predictionProceedings of the 59th ACM/IEEE Design Automation Conference10.1145/3489517.3530597(1207-1212)Online publication date: 10-Jul-2022
https://dl.acm.org/doi/10.1145/3489517.3530597
Barboza EShukla NChen YHu J(2019)Machine Learning-Based Pre-Routing Timing Prediction with Reduced PessimismProceedings of the 56th Annual Design Automation Conference 201910.1145/3316781.3317857(1-6)Online publication date: 2-Jun-2019
https://dl.acm.org/doi/10.1145/3316781.3317857
Wu HWong M(2009)Incremental improvement of voltage assignmentIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2008.200915528:2(217-230)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1109/TCAD.2008.2009155
Jiang ZShi WFix L(2008)Circuit-wise buffer insertion and gate sizing algorithm with scalabilityProceedings of the 45th annual Design Automation Conference10.1145/1391469.1391652(708-713)Online publication date: 8-Jun-2008
https://dl.acm.org/doi/10.1145/1391469.1391652
Chen YFang JChang YGielen G(2007)ECO timing optimization using spare cellsProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326183(530-535)Online publication date: 5-Nov-2007
https://dl.acm.org/doi/10.5555/1326073.1326183
Mang FHou WHo PLevitan S(2007)Techniques for effective distributed physical synthesisProceedings of the 44th annual Design Automation Conference10.1145/1278480.1278692(859-864)Online publication date: 4-Jun-2007
https://dl.acm.org/doi/10.1145/1278480.1278692
Wu HWong MLevitan S(2007)Improving voltage assignment by outlier detection and incremental placementProceedings of the 44th annual Design Automation Conference10.1145/1278480.1278600(459-464)Online publication date: 4-Jun-2007
https://dl.acm.org/doi/10.1145/1278480.1278600
Saxena PHutton MDambre J(2006)The scaling of interconnect buffer needsProceedings of the 2006 international workshop on System-level interconnect prediction10.1145/1117278.1117300(109-112)Online publication date: 4-Mar-2006
https://dl.acm.org/doi/10.1145/1117278.1117300
Chen RZhou H(2005)Efficient algorithms for buffer insertion in general circuits based on network flowProceedings of the 2005 IEEE/ACM International conference on Computer-aided design10.5555/1129601.1129649(322-326)Online publication date: 31-May-2005
https://dl.acm.org/doi/10.5555/1129601.1129649
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