Article

Free access

An Algorithm for Zero-Skew Clock Tree Routing with Buffer Insertion

Authors:

Y. P. Chen,

D. F. WongAuthors Info & Claims

EDTC '96: Proceedings of the 1996 European conference on Design and Test

Page 230

Published: 11 March 1996 Publication History

PDF eReader

Abstract

We study the problem of multi-stage zero skew clock tree construction for minimizing clock phase delay and wirelength. In existing approaches clock buffers are inserted only after clock tree is constructed. The novelty of this paper lies in simultaneously perform clock tree routing and buffer insertion. We propose a clustering-based algorithm which uses shortest delay as the cost function. We show that the feasible positions for clock tree nodes and buffers can be generalized from diagonal segments (merging segments) to rectangles (merging blocks). Buffers are large components and must be placed pairwise disjointly. We also show that the problem of finding legal positions for buffers such that no buffers overlap can be formulated as a shortest path problem on graphs, and can be solved by the Bellman-Ford algorithm. By making use of the special properties of the graphs, we further speedup the Bellman-Ford algorithm. The experimental results show that our algorithm greatly outperforms the approach of inserting buffers after clock routing.

References

[1]

[1] H. B. Bakoglu, Circuits, Interconnections, and Packaging for VLSI, Addison-Wesley Publishing Co., 1990.

Google Scholar

[2]

[2] K. D. Boose and A. B. Kahng, "Zero-skew clock routing trees with minimum wirelength," Proc. IEEE Intl. Conf. on ASIC, pp.1.1.1-1.1.5, 1992.

Google Scholar

[3]

[3] T. Chao, Y. Hsu and J. Ho, "Zero skew clock net routing," Proc. ACM/IEEE Design Automation Conference, pp. 518-523, 1992.

Digital Library

Google Scholar

[4]

[4] T. Chao, Y. Hsu, J. Ho, K. D. Boose and A. B. Kahng, "Zero skew clock routing with minimum wirelength," IEEE Trans. on Circuits and Systems 39(11), pp. 799-814, 1992.

Crossref

Google Scholar

[5]

[5] J. D. Cho aud M. Sarrafzadeh, "A buffer distribution algorithm for high-speed clock routing," Proc. ACM/IEEE Design Automation Conference, pp. 537-543, 1992.

Digital Library

Google Scholar

[6]

[6] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, The MIT Press, 1991.

Digital Library

Google Scholar

[7]

[7] M. Edahiro, "Clustering-based optimization algorithm in zeroskew routings," Proc. ACM/IEEE Design Automation Conference , pp. 612-616, 1993.

Digital Library

Google Scholar

[8]

[8] M. Edahiro, "Minimum skew and minimum path length routing in VLSI layout design," NEC Research and Development 32(4), pp. 569-575, 1991.

Google Scholar

[9]

[9] W. C. Elmore, "The transient response of damped linear networks with particular regard to wideband amplifiers," J. Applied Phys., 19(1):55-63, 1948.

Crossref

Google Scholar

[10]

[10] M. A. B. Jackson, A. Srinivasan and E. S. Kuh, "Clock routing for high-performance ICs," Proc. ACM/IEEE Design Automation Conference, pp. 573-579, 1990.

Digital Library

Google Scholar

[11]

[11] A. Kahng, J. Cong and G. Robins, "High-performance clock routing based on recursive geometric matching," Proc. ACM/IEEE Design Automation Conference, pp. 322-327, 1991.

Digital Library

Google Scholar

[12]

[12] S. Pullela, N. Menezes, J. Omar and L. T. Pillage, "Skew and delay optimization for reliable buffered clock trees," Proc. IEEE Intl. Conference on Computer-Aided Design, pp. 556-562, 1993.

Crossref

Google Scholar

[13]

[13] G. Tellez and M. Sarrafzadeh, "Clock period constrained minimal buffer insertion in clock trees," Proc. IEEE Intl. Conference on Computer-Aided Design, pp. 219-223, 1994.

Digital Library

Google Scholar

[14]

[14] R. Tsay, "Exact zero skew," Proc. IEEE Intl. Conference on Computer-Aided Design, pp. 336-339, 1991.

Google Scholar

Cited By

View all

Ewetz RKoh C(2019)Scalable Construction of Clock Trees With Useful Skew and High Timing QualityIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.283443738:6(1161-1174)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1109/TCAD.2018.2834437
Ewetz RKoh C(2017)Fast clock scheduling and an application to clock tree synthesisIntegration, the VLSI Journal10.1016/j.vlsi.2016.10.01256:C(115-127)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.vlsi.2016.10.012
Ewetz RKoh C(2016)Construction of Reconfigurable Clock Trees for MCMM Designs Using Mode Separation and Scenario CompressionACM Transactions on Design Automation of Electronic Systems10.1145/288360921:4(1-27)Online publication date: 18-May-2016
https://dl.acm.org/doi/10.1145/2883609
Show More Cited By

An Algorithm for Zero-Skew Clock Tree Routing with Buffer Insertion
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Legitimate Skew Clock Routing with Buffer Insertion

In this paper, we propose a new quick and effective legitimate skew clock routing with buffer insertion algorithm. We analyze the optimal buffer position in the clock path, and conclude the sufficient condition and heuristic condition for buffer ...
Zero-skew clock tree construction by simultaneous routing, wire sizing and buffer insertion
ICCAD '00: Proceedings of the 2000 international conference on Computer-aided design

We propose an integrated clock tree construction algorithm which performs simultaneous routing, wire sizing and buffer insertion. In existing approaches, wire sizing and clock buffer insertion are typically applied sequentially after a clock tree is ...
An Algorithm for Zero-Skew Clock Tree Routing with Buffer Insertion

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EDTC '96: Proceedings of the 1996 European conference on Design and Test

March 1996

585 pages

ISBN:0818674237

Publisher

IEEE Computer Society

United States

Publication History

Published: 11 March 1996

Check for updates

Author Tags

Qualifiers

Article

Conference

EDTC96

Sponsor:

SIGDA

EDTC96: European Design and Test Conference

March 11 - 14, 1996

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
362
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ewetz RKoh C(2019)Scalable Construction of Clock Trees With Useful Skew and High Timing QualityIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.283443738:6(1161-1174)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1109/TCAD.2018.2834437
Ewetz RKoh C(2017)Fast clock scheduling and an application to clock tree synthesisIntegration, the VLSI Journal10.1016/j.vlsi.2016.10.01256:C(115-127)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.vlsi.2016.10.012
Ewetz RKoh C(2016)Construction of Reconfigurable Clock Trees for MCMM Designs Using Mode Separation and Scenario CompressionACM Transactions on Design Automation of Electronic Systems10.1145/288360921:4(1-27)Online publication date: 18-May-2016
https://dl.acm.org/doi/10.1145/2883609
Ewetz RTan CKoh CYoung EOzdal M(2016)Construction of Latency-Bounded Clock TreesProceedings of the 2016 on International Symposium on Physical Design10.1145/2872334.2872349(81-88)Online publication date: 3-Apr-2016
https://dl.acm.org/doi/10.1145/2872334.2872349
Ewetz RJanarthanan SKoh C(2015)Construction of reconfigurable clock trees for MCMM designsProceedings of the 52nd Annual Design Automation Conference10.1145/2744769.2744811(1-6)Online publication date: 7-Jun-2015
https://dl.acm.org/doi/10.1145/2744769.2744811
Ewetz RKoh CDavoodi AYoung E(2015)A Useful Skew Tree Framework for Inserting Large Safety MarginsProceedings of the 2015 Symposium on International Symposium on Physical Design10.1145/2717764.2717773(85-92)Online publication date: 29-Mar-2015
https://dl.acm.org/doi/10.1145/2717764.2717773
Guthaus MWilke GReis R(2013)Revisiting automated physical synthesis of high-performance clock networksACM Transactions on Design Automation of Electronic Systems10.1145/2442087.244210218:2(1-27)Online publication date: 11-Apr-2013
https://dl.acm.org/doi/10.1145/2442087.2442102
Lu JMao XTaskin BHu A(2012)Clock mesh synthesis with gated local trees and activity driven register clusteringProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429536(691-697)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2429384.2429536
Lin KLin HHo TTsai C(2012)Load-balanced clock tree synthesis with adjustable delay buffer insertion for clock skew reduction in multiple dynamic supply voltage designsACM Transactions on Design Automation of Electronic Systems10.1145/2209291.220930717:3(1-22)Online publication date: 5-Jul-2012
https://dl.acm.org/doi/10.1145/2209291.2209307
Lu JMao XTaskin BChang YHu J(2011)Timing slack aware incremental register placement with non-uniform grid generation for clock mesh synthesisProceedings of the 2011 international symposium on Physical design10.1145/1960397.1960426(131-138)Online publication date: 27-Mar-2011
https://dl.acm.org/doi/10.1145/1960397.1960426
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Recommendations

Legitimate Skew Clock Routing with Buffer Insertion

Zero-skew clock tree construction by simultaneous routing, wire sizing and buffer insertion

An Algorithm for Zero-Skew Clock Tree Routing with Buffer Insertion