[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1233501.1233616acmconferencesArticle/Chapter ViewAbstractPublication PagesiccadConference Proceedingsconference-collections
Article

Combinatorial algorithms for fast clock mesh optimization

Published: 05 November 2006 Publication History

Abstract

We present a fast and efficient combinatorial algorithm to simultaneously identify the candidate locations as well as the sizes of the buffers driving a clock mesh. Due to the high redundancy, a mesh architecture offers high tolerance towards variation in the clock skew. However, such a redundancy comes at the expense of mesh wire length and power dissipation. Based on survivable network theory, we formulate the problem to reduce the clock mesh by retaining only those edges that are critical to maintain redundancy. Such a formulation offers designer the option to trade-off between power and tolerance to process variations. Experimental results indicate that our techniques can result in power savings up to 28% with less than 4% delay penalty.

References

[1]
Y. Liu, S. R. Nassif, L. T. Pileggi, and A. J. Strojwas. Impact of interconnect variations on the clock skew of a gigahertz microprocessor. DAC, pages 168--171, 2000.
[2]
J. P. Fishburn. Clock skew optimization. IEEE Transactions on Computers, vol. 39, no. 7, pages 945--950, 1990.
[3]
T.-H. Chao, Y.-C. Hsu, J.-M. Ho, K. D. Boese, and A. B. Kahng. Zero skew clock routing with minimum wirelength. IEEE Transactions on Circuits and Systems - Analog and Digital Signal Processing, 39(11):799--814, November 1992.
[4]
N. A. Kurd, J. S. Barkatullah, R. O. Dizon, T. D. Fletcher, and P. D. Madland. A multigigahertz clocking scheme for the Pentium 4 microprocessor. IEEE Journal of Solid-State Circuits, 36(11):1647--1653, November 2001.
[5]
P. J. Restle et al. A clock distribution network for microprocessors. IEEE Journal of Solid-State Circuits, 36(5):792--799, May 2001.
[6]
N. Bindal, T. Kelly, N. Velastegui, and K. L. Wong. Scalable sub-10ps skew global clock distribution for a 90nm multi-GHz IA microprocessor. In Proceedings of the ISSCC, pages 346--355, 2003.
[7]
A. Rajaram, J. Hu, and R. Mahapatra. Reducing clock skew variability via cross links. In DAC, pages 18--23, 2004.
[8]
G. Northrop et. al. 609 MHz G5 S/399 microprocessor. In ISSCC, pages 88--89, 1999.
[9]
P. J. Restle et. al. The clock distribution of the Power4 microprocessor. In, ISSCC, pages 144--145, 2002.
[10]
R. Heald. Implementation of a 3rd-generation SPARC V9 64 b microprocessor. In ISSCC, pages 412--413, 2000.
[11]
H. Su and S. Sapatnekar. Hybrid structured clock network construction. In ICCAD, pages, 333--336, 2001.
[12]
V. V. Vazirani. Approximation Algorithms. Springer 2001.
[13]
K. Jain. A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. In IEEE Symposium on Foundations of Computer Science, pages 448--457, 1998.
[14]
H. Kerivin and A. R. Mahjoub. Design of Survivable Networks: A survey. In Networks, pages 1--21, April 2005.
[15]
W Ben-Ameur. Constrained length connectivity and survivable networks. In Networks, pages 17--23, August 2000.
[16]
J. Qian and S. Pullela and L. Pillage. Modeling the 'Effective Capacitance' of RC Interconnect. In IEEE Trans. Computer-Aided Design, pages 1526--1535, December 1994.
[17]
F. Dartu and N. Menezes and J. Qian and L. Pillage. A gate-delay model for high speed CMOS circuits. In DAC, pages 576--580, June 1994.
[18]
R. Arunachalam, F. Dartu and L. Pileggi. CMOS gate delay models for general RLC loading. In ICCAD, pages 224--229, October 1997.
[19]
J. Croix and D. Wong. Blade and Razor: Cell and Interconnect Delay Analysis Using Current-Based Models. In DAC, pages 386--389, June 2006.
[20]
P. Li and E. Acar. A waveform independent gate model for accurate timing analysis. In ICCD, pages 363--365, October 2005.
[21]
I. Keller, K. Tseng and N. Verghese. A robust cell-level crosstalk delay change analysis. In ICCAD, pages 147--154, November 2004.
[22]
http://www.eas.asu.edu/ptm/.
[23]
A. B. Kahng and B. Liu. Q-Tree: A New Iterative Improvement Approach for Buffered Interconnect Optimization. IEEE Comp. Soc. Annual Symp. On VLSI, pages 183--188, February, 2003.
[24]
H. Chang and S. S. Sapatnekar. Statistical timing analysis considering spatial correlations using a single PERT-like traversal. In ICCAD, pages 621--625, 2003.

Cited By

View all
  • (2018)Fast Timing Analysis of Non-Tree Clock Network with Shorted WiresProceedings of the 2018 Great Lakes Symposium on VLSI10.1145/3194554.3194598(279-284)Online publication date: 30-May-2018
  • (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
  • (2012)Library-aware resonant clock synthesis (LARCS)Proceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228389(145-150)Online publication date: 3-Jun-2012
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design
November 2006
147 pages
ISBN:1595933891
DOI:10.1145/1233501
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2006

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

ICCAD06
Sponsor:

Acceptance Rates

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

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)8
  • Downloads (Last 6 weeks)0
Reflects downloads up to 24 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2018)Fast Timing Analysis of Non-Tree Clock Network with Shorted WiresProceedings of the 2018 Great Lakes Symposium on VLSI10.1145/3194554.3194598(279-284)Online publication date: 30-May-2018
  • (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
  • (2012)Library-aware resonant clock synthesis (LARCS)Proceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228389(145-150)Online publication date: 3-Jun-2012
  • (2012)High-performance clock mesh optimizationACM Transactions on Design Automation of Electronic Systems10.1145/2209291.220930617:3(1-17)Online publication date: 5-Jul-2012
  • (2012)Crosslink insertion for variation-driven clock network constructionProceedings of the great lakes symposium on VLSI10.1145/2206781.2206860(321-326)Online publication date: 3-May-2012
  • (2012)Distributed LC Resonant Clock Grid SynthesisIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2012.219067159:11(2749-2760)Online publication date: Nov-2012
  • (2012)Clock mesh frameworkThirteenth International Symposium on Quality Electronic Design (ISQED)10.1109/ISQED.2012.6187528(424-431)Online publication date: Mar-2012
  • (2012)Energy metrics for power efficient crosslink and mesh topologies2012 IEEE International Symposium on Circuits and Systems10.1109/ISCAS.2012.6271575(1656-1659)Online publication date: May-2012
  • (2011)Multilevel tree fusion for robust clock networksProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132468(632-639)Online publication date: 7-Nov-2011
  • (2011)Algorithmic tuning of clock trees and derived non-tree structuresProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132396(279-282)Online publication date: 7-Nov-2011
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media