Article

Free access

UST/DME: a clock tree router for general skew constraints

Authors:

Chung-Wen Albert Tsao,

Cheng-Kok KohAuthors Info & Claims

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

Pages 400 - 405

Published: 05 November 2000 Publication History

Abstract

In this paper, we propose new approaches for solving the useful-skew tree (UST) routing problem [17]: Clock routing subject to general skew constraints. The clock layout synthesis engine of our UST algorithms is based on the deferred-merge embedding (DME) paradigm for zero-skew tree [5; 1] and bounded-skew tree [8; 2] routings; hence, the names UST/DME and Greedy-UST/DME for our algorithms. They simultaneously perform skew scheduling and tree routing such that each local skew range is incrementally refined to a skew value that minimizes the wirelength during the bottom-up merging phase of DME. The resulting skew schedule is not only feasible, but is also best for routing in terms of wirelength. The experimental results show very encouraging improvement over the previous BST/DME algorithm on three ISCAS89 benchmarks under general skew constraints in terms of total wirelength.

References

[1]

T.-H. Chao, Y.-C. Hsu Hsu, J.-M. Ho, K. D. Boese, and A. B. Kahng. Zero skew clock routing with minimum wirelength. IEEE Trans. on Circuits and Systems, 39(11):799-814, November 1992.

[2]

J. Cong, A. B. Kahng, C.-K. Koh, and C.-W. A. Tsao. Bounded-skew clock and Steiner routing. ACM Trans. on Design Automation of Electronics Systems, 3(3):341-388, 1998.

Digital Library

[3]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms, chapter 25.5, pages 539-543. 1990.

Digital Library

[4]

R. B. Deokar and S. S. Sapatnekar. A graph-theoretic approach to clock skew optimization. In Proc. IEEE Int. Symp. on Circuits and Systems, pages 407-410, 1994.

[5]

M. Edahiro. Minimum path-length equi-distant routing. In Proc. IEEE Asia-Pacific Conf. on Circuits and Systems, pages 41-46, December 1992.

[6]

M. Edahiro. An efficient zero-skew routing algorithm. In Proc. Design Automation Conf, pages 375-380, June 1994.

Digital Library

[7]

J. P. Fishburn. Clock skew optimization. IEEE Trans. on Computers, 39(7):945-951, July 1990.

Digital Library

[8]

A. B. Kahng and C.-W. A. Tsao. Practical bounded-skew clock routing. Journal of VLSI Signal Processing (Special issue on High Performance Clock Distribution Networks), 16(2-3):199-215, June-July 1997.

Digital Library

[9]

J. L. Neves and E. G. Friedman. Optimal clock skew scheduling tolerant to process variations. In Proc. Design Automation Conf, pages 623-628, 1996.

Digital Library

[10]

K. A. Sakallah, T. N. Mudge, and O. A. Olukotun. checkTc and minTc: Timing verification and optimal clocking of synchronous digital circuits. In Proc. Int. Conf. on Computer Aided Design, pages 552-555, 1990.

[11]

N. Shenoy, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. Graph algorithms for clock schedule optimization. In Proc. Int. Conf. on Computer Aided Design, pages 132-136, 1992.

Digital Library

[12]

T.G. Szymanski. Computing optimal clock schedules. In Proc. Design Automation Conf., pages 399-404, 1992.

Digital Library

[13]

R.-S. Tsay. An exact zero-skew clock routing algorithm. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, CAD-12(2):242-249, February 1993.

[14]

A. Vittal, H. Ha, F. Brewer, and M. Marek-Sadowska. Clock skew optimization for ground bounce control. In Proc. Int'l Conf. on Computer Aided Design, pages 395-399, Nov. 1996.

Digital Library

[15]

P. Vuillod, L. Benini, A. Bogliolo, and G. De Micheli. Clock-skew optimization for peak current reduction. In Proc. Int'l Symp. on Low Power Electronics and Design, pages 265-270, Aug. 1996.

Digital Library

[16]

J. G. Xi and W. W.-M. Dai. Jitter-tolerant clock routing in two-phase synchronous systems. In Proc. Int. Conf. on Computer Aided Design, pages 316-320, 1996.

Digital Library

[17]

J. G. Xi and W. W.-M. Dai. Useful-skew clock routing with gate sizing for low power design. Journal of VLSI Signal Processing Systems, 16(2/3):163-170, 1997.

Digital Library

Cited By

Tan CEwetz RKoh CShin Y(2018)Clustering of flip-flops for useful-skew clock tree synthesisProceedings of the 23rd Asia and South Pacific Design Automation Conference10.5555/3201607.3201728(507-512)Online publication date: 22-Jan-2018
https://dl.acm.org/doi/10.5555/3201607.3201728
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
Shen WCai YHong XHu JLu B(2008)Zero skew clock routing in X-architecture based on an improved greedy matching algorithmIntegration, the VLSI Journal10.1016/j.vlsi.2007.10.00441:3(426-438)Online publication date: 1-May-2008
https://dl.acm.org/doi/10.1016/j.vlsi.2007.10.004
Show More Cited By

Recommendations

UST/DME: a clock tree router for general skew constraints

In this article, we propose new approaches for solving the useful-skew tree (UST) routing problem [Xi and Dai 1997]: clock routing subject to general skew constraints. The clock layout synthesis engine of our UST algorithms is based on the deferred-...
Planar-DME: a single-layer zero-skew clock tree router

This paper presents new single-layer, i.e., planar-embeddable, clock tree constructions with exact zero skew under either the linear or the Elmore delay model. Our method, called Planar-DME, consists of two parts. The first algorithm, called Linear-...
Planar-DME: improved planar zero-skew clock routing with minimum pathlength delay
EURO-DAC '94: Proceedings of the conference on European design automation

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 2000

558 pages

ISBN:0780364481

Conference Chair:
Ellen M. Sentovich
Cadence Berkley Labs., Berkley, California

Sponsors

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

Publisher

IEEE Press

Publication History

Published: 05 November 2000

Check for updates

Qualifiers

Article

Conference

ICCAD '00

Sponsor:

SIGDA

ICCAD '00: International Conference on Computer Aided Design

November 5 - 9, 2000

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

11
Total Citations
View Citations
207
Total Downloads

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

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tan CEwetz RKoh CShin Y(2018)Clustering of flip-flops for useful-skew clock tree synthesisProceedings of the 23rd Asia and South Pacific Design Automation Conference10.5555/3201607.3201728(507-512)Online publication date: 22-Jan-2018
https://dl.acm.org/doi/10.5555/3201607.3201728
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
Shen WCai YHong XHu JLu B(2008)Zero skew clock routing in X-architecture based on an improved greedy matching algorithmIntegration, the VLSI Journal10.1016/j.vlsi.2007.10.00441:3(426-438)Online publication date: 1-May-2008
https://dl.acm.org/doi/10.1016/j.vlsi.2007.10.004
Kim MHu JGielen G(2006)Associative skew clock routing for difficult instancesProceedings of the conference on Design, automation and test in Europe: Proceedings10.5555/1131481.1131699(762-767)Online publication date: 6-Mar-2006
https://dl.acm.org/doi/10.5555/1131481.1131699
Rajaram APan D(2006)Fast Incremental Link Insertion in Clock Networks for Skew Variability ReductionProceedings of the 7th International Symposium on Quality Electronic Design10.1109/ISQED.2006.66(79-84)Online publication date: 27-Mar-2006
https://dl.acm.org/doi/10.1109/ISQED.2006.66
Lu YSze CHong XZhou QCai YHuang LHu JTang T(2005)Register placement for low power clock networkProceedings of the 2005 Asia and South Pacific Design Automation Conference10.1145/1120725.1120971(588-593)Online publication date: 18-Jan-2005
https://dl.acm.org/doi/10.1145/1120725.1120971
Huang LCai YZhou QHong XHu JLu YTang T(2005)Clock network minimization methodology based on incremental placementProceedings of the 2005 Asia and South Pacific Design Automation Conference10.1145/1120725.1120755(99-102)Online publication date: 18-Jan-2005
https://dl.acm.org/doi/10.1145/1120725.1120755
Lu YSze CHong XZhou QCai YHuang LHu JJoyner WMartin GKahng A(2005)Navigating registers in placement for clock network minimizationProceedings of the 42nd annual Design Automation Conference10.1145/1065579.1065628(176-181)Online publication date: 13-Jun-2005
https://dl.acm.org/doi/10.1145/1065579.1065628
Rajaram APan DHu JGroeneveld PScheffer L(2005)Improved algorithms for link-based non-tree clock networks for skew variability reductionProceedings of the 2005 international symposium on Physical design10.1145/1055137.1055150(55-62)Online publication date: 3-Apr-2005
https://dl.acm.org/doi/10.1145/1055137.1055150
Rajaram ALu BGuo WMahapatra RHu J(2003)Analytical Bound for Unwanted Clock Skew due to Wire Width VariationProceedings of the 2003 IEEE/ACM international conference on Computer-aided design10.5555/996070.1009921Online publication date: 9-Nov-2003
https://dl.acm.org/doi/10.5555/996070.1009921
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents