skip to main content
10.1145/1735023.1735057acmconferencesArticle/Chapter ViewAbstractPublication PagesispdConference Proceedingsconference-collections
research-article

Accurate clock mesh sizing via sequential quadraticprogramming

Published: 14 March 2010 Publication History

Abstract

Clock mesh is widely used in microprocessor designs for achieving low clock skew and high variation tolerance. Clock mesh optimization is a very difficult problem because it has highly-connected structure and requires accurate delay models which are computationally expensive. Existing methods on clock network optimization are either restricted to clock trees, which are easy to be separated into smaller problems, or naive heuristics based on crude delay models. In this paper, we propose a clock mesh sizing algorithm which is aimed to minimize mesh wire area with consideration of clock skew constraints. This algorithm is a systematic solution search through rigorous Sequential Quadratic Programming (SQP). The SQP is guided by an efficient adjoint sensitivity analysis which has near-SPICE-level accuracy and faster-than-SPICE speed. Experimental results on various benchmark circuits indicate that our algorithm leads to significant wire area reduction while maintaining low clock skew.

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". In Proc. of ACM/IEEE Design Automation Conference, pp 168--171, 2000.
[2]
J.P. Fishburn. "Clock skew optimization". In IEEE Trans. Computers, pp 945--951, July 1990.
[3]
S.M. Reddy, G.R. Wilke and R. Murgai. "Analyzing timing uncertainty in mesh-based clock architectures". In Proc. of IEEE/ACM International Conference on Computer-Aided Design, pp 1--6, 2006.
[4]
D.E. Duarte, N. Vijaykrishnan and M. J. Irwin. "A clock power model to evaluate impact of architectural and technology optimizations". In IEEE Trans. Very Large Scale Integration, pp 844--855, December 2002.
[5]
C. Yeh, G. Wilke, H. Chen, S. Reddy, H. Nguyen, T. Miyoshi, W. Walker and R. Murgai. "Clock distribution architectures: a comparative study". In Proc. of IEEE International Symposium on Quality Electronic Design, pp 7--91, 2006.
[6]
M. R. Guthaus, D. Sylvester and R. B. Brown. "Clock buffer and wire sizing using sequential programming". In Proc. of ACM/IEEE Design Automation Conference, pp 1041--1046, 2006.
[7]
M. Mori, H. Chen, B. Yao and C. Cheng. "A mulitple level network approach for clock skew minimization with process variations". In Proc. of Asia and South Pacific Design Automation Conference, pp 263--268, 2004
[8]
S. Pullela, N. Menezes and L. T. Pileggi. Moment-sensitivity-based wire sizing for skew reduction in on-chip clock nets". In IEEE Trans. Computer-Aided Design, pp 210--215, February 1997.
[9]
K. Wang, Y. Ran, H. Jiang and M. Marek-Sadowska. "General skew constrained clock network sizing based on sequential linear programming". In IEEE Trans. Computer-Aided Design, pp. 773--782, May 2005.
[10]
A. Rajaram, J. Hu and R. Mahapatra. "Reducing clock skew variability via crosslinks". In IEEE Trans. Computer-Aided Design, pp. 1176--1182, June 2006.
[11]
R. Samanta, J. Hu and P. Li. "Discrete buffer and wire sizing for link-based non-tree clock networks". In Proc. of ACM International Symposium on Physical Design, pp 175--181, 2008
[12]
G. Venkataraman, Z. Feng, J. Hu and P. Li. "Combinatorial algorithms for fast clock mesh optimization". In Proc. of IEEE/ACM International Conference on Computer-Aided Design, pp 563--567, 2006.
[13]
A. Rajaram and D. Z. Pan. "MeshWorks: An efficient framework for planning, synthesis and optimization of clock mesh networks". In Proc. of Asia and South Pacific Design Automation Conference, pp 250--257, 2008.
[14]
M. P. Desai, R. Cvijetic and J. Jensen. "Sizing of clock distribution networks for high performance CPU chips". In Proc. of ACM/IEEE Design Automation Conference, pp 389--394, 1996.
[15]
http://www.sigda.org/ispd/contests/ispd09cts.html
[16]
http://www.pld.ttu.ee/ maksim/benchmarks/iscas89/verilog/
[17]
J. Stoer and K. Schittkowski. "Principles of sequential quadratic programming methods for solving nonlinear programs. In Computational Mathematical Programming Ed. Series, vol. 15. Berlin, Germany: Springer-Verlag, pp. 165--205, 1984.
[18]
M. S. Bazaraa, D. S. Hanif and C. M. Shetty. "Nonlinear programming: theory and algorithms". WILEY, Third Edition, 2006.
[19]
P. Li, Z. Feng and E. Acar. "Characterizing multistage nonlinear drivers and variability for accurate timing and noise analysis". In IEEE Trans. Very Large Scale Integration, pp 1205--1214, November 2007.
[20]
X. Ye and P. Li. "An application-specific adjoint sensitivity analysis framework for clock mesh sensitivity computation". In Proc. of IEEE International Symposium on Quality Electronic Design, pp 634--640, 2009.
[21]
http://www.eas.asu.edu/ ptm/
[22]
http://www.mosek.com/

Cited By

View all
  • (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)Clock mesh synthesis method using the Earth Mover's Distance under transformationsProceedings of the 2012 IEEE 30th International Conference on Computer Design (ICCD 2012)10.1109/ICCD.2012.6378627(121-126)Online publication date: 30-Sep-2012
  • (2010)High variation-tolerant obstacle-avoiding clock mesh synthesis with symmetrical driving treesProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133524(452-457)Online publication date: 7-Nov-2010

Index Terms

  1. Accurate clock mesh sizing via sequential quadraticprogramming

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ISPD '10: Proceedings of the 19th international symposium on Physical design
    March 2010
    220 pages
    ISBN:9781605589206
    DOI:10.1145/1735023
    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

    In-Cooperation

    • IEEE CAS

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 14 March 2010

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. optimization
    2. sequential quadratic programming

    Qualifiers

    • Research-article

    Conference

    ISPD '10
    Sponsor:
    ISPD '10: International Symposium on Physical Design
    March 14 - 17, 2010
    California, San Francisco, USA

    Acceptance Rates

    ISPD '10 Paper Acceptance Rate 22 of 70 submissions, 31%;
    Overall Acceptance Rate 62 of 172 submissions, 36%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (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)Clock mesh synthesis method using the Earth Mover's Distance under transformationsProceedings of the 2012 IEEE 30th International Conference on Computer Design (ICCD 2012)10.1109/ICCD.2012.6378627(121-126)Online publication date: 30-Sep-2012
    • (2010)High variation-tolerant obstacle-avoiding clock mesh synthesis with symmetrical driving treesProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133524(452-457)Online publication date: 7-Nov-2010

    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