Article

Optimal useful clock skew scheduling in the presence of variations using robust ILP formulations

Authors:

Vaibhav Nawale,

Thomas W. ChenAuthors Info & Claims

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

Pages 27 - 32

https://doi.org/10.1145/1233501.1233508

Published: 05 November 2006 Publication History

Abstract

This paper exploits useful skew to improve system performance and robustness. We formulate a robust integer linear programming problem considering the interactions between data and clock paths on a microprocessor chip to improve clock frequency. The timing slack is optimized for each path to determine a clock schedule. The percentage of timing violations, obtained from a 1000 point Monte Carlo simulation, is higlighted as yield predictions and conveys the robustness of the clock schedule. The results show performance improvement of up to 9.747% with 20% yield and up to 6.682% with 100% yield. The novelty of the proposed method is its ability to tradeoff between performance improvement in frequency and robustness, via a single variable in the formulation.

References

[1]

M. Bertsimas, D. Sim. Robust Discrete Optimization and Network Flows. Oper. Res. Center, MIT, Jan.

[2]

L.-F. Chao and H.-M. Sha. Retiming and clock skew for synchronous systems. ISCAS; pp 283--286, May 1994.

[3]

R. Deokar and S. Sapatnekar. A graph-theoretic approach to clock skew optimization. ISCAS; pp 407--410, 30 May - 2 June 1994.

[4]

J. P. Fishburn. Clock skew optimization. IEEE Trans. Comput.; pp 945--951, July 1990.

Digital Library

[5]

I. Kourtev and F. E. G. Clock skew scheduling for improved reliability via quadratic programming. ICCAD; pp 339--243, Nov 1999.

Digital Library

[6]

X. Liu, M. Papaefthymiou, and E. Friedman. Maximizing performance by retiming and clock skew scheduling. DAC; pp 231--236, 1999.

Digital Library

[7]

P. Mahoney, E. Fetzer, B. Doyle, and S. Naffziger. Clock Distribution on a Dual-Core Multi-Threaded Itanium- Family Processor. ISSCC Session 16, 2005.

[8]

S. Malik, E. Sentovich, R. Brayton, and A. Sangiovanni-Vincentelli. Retiming and resynthesis: optimizing sequential networks with combinational techniques. 1990., Proc. 23rd Annual Hawaii Int. Conf.; pp 397--406, 2--5 Jan 1990 1997.

[9]

V. Mehrotra and D. Boning. Technology scaling impact of variation on clock skew and interconnect delay. Interconnect Tech. Conf., Proc. of IEEE, 4--6 June 2001.

[10]

J. Neves and E. Friedman. Optimal clock skew scheduling tolerant to process variations. DAC; pp 623--628, 3--7 June 1996.

Digital Library

[11]

M. Saitoh, M. Azuma, and A. Takahashi. Clustering based fast clock scheduling for light clock-tree. DATE, Conf.; pp 240--244, 13--16 March 2001.

Digital Library

[12]

K. e. a. Sakallah. Analysis and design of latch-controlled synchronous digital circuits. DAC; pp 322--333, March 1992.

[13]

R. Saleh, S. Z. Hussain, S. Rochel, and D. Overhauser. Clock skew in the presence of IR-drop in the power distribution network. IEEE Tran. on CAD of ISCAS, Jun 2000.

Digital Library

[14]

A. L. Soyster. Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res.; pp 1154--1157, 1973.

[15]

Y. Taur and D. Buchanan. CMOS scaling in nanometer regime. Proc. IEEE; pp 486--503, Apr 1997.

Cited By

Kim JKim T(2017)Adjustable Delay Buffer Allocation under Useful Clock Skew SchedulingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.259721336:4(641-654)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TCAD.2016.2597213
Roy SPan DMattheakis PColyer PMasse-Navette LRibet PJones ALi HCoskun AMargala M(2015)Skew Bounded Buffer Tree Resynthesis For Clock Power OptimizationProceedings of the 25th edition on Great Lakes Symposium on VLSI10.1145/2742060.2742119(87-90)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1145/2742060.2742119
Roy SMattheakis PMasse-Navette LPan DSze CDavoodi A(2014)Clock tree resynthesis for multi-corner multi-mode timing closureProceedings of the 2014 on International symposium on physical design10.1145/2560519.2560524(69-76)Online publication date: 30-Mar-2014
https://dl.acm.org/doi/10.1145/2560519.2560524
Show More Cited By

Index Terms

Optimal useful clock skew scheduling in the presence of variations using robust ILP formulations
1. Hardware
  1. Hardware validation
    1. Functional verification
      1. Simulation and emulation
  2. Very large scale integration design
    1. Application-specific VLSI designs
      1. Application specific instruction set processors
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Control structures

Recommendations

Statistical skew modeling for general clock distribution networks in presence of process variations

Clock skew modeling is important in the performance evaluation and prediction of clock distribution networks. This paper addresses the problem of statistical skew modeling for general clock distribution networks in the presence of process variations. ...
Clock Skew Scheduling in the Presence of Heavily Gated Clock Networks
GLSVLSI '15: Proceedings of the 25th edition on Great Lakes Symposium on VLSI

Clock skew scheduling is a common and well known technique to improve the performance of sequential circuits by exploiting the mismatches in the data path delays. Existing clock skew scheduling techniques, however, cannot effectively consider heavily ...
Delay insertion method in clock skew scheduling
ISPD '05: Proceedings of the 2005 international symposium on Physical design

This paper describes a delay insertion method that improves the efficiency of clock skew scheduling. Clock skew scheduling is performed on synchronous circuits in order to improve the performance of a circuit; most often by permitting the circuit to ...

Comments

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

General Chair:
Soha Hassoun
Tufts Univ., Medford, MA

Copyright © 2006 ACM.

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

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICCAD06

Sponsor:

SIGDA
IEEE-CAS
IEEE-CS

ICCAD06: The International Conference on Computer-Aided Design 2006

November 5 - 9, 2006

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

7
Total Citations
View Citations
292
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kim JKim T(2017)Adjustable Delay Buffer Allocation under Useful Clock Skew SchedulingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.259721336:4(641-654)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TCAD.2016.2597213
Roy SPan DMattheakis PColyer PMasse-Navette LRibet PJones ALi HCoskun AMargala M(2015)Skew Bounded Buffer Tree Resynthesis For Clock Power OptimizationProceedings of the 25th edition on Great Lakes Symposium on VLSI10.1145/2742060.2742119(87-90)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1145/2742060.2742119
Roy SMattheakis PMasse-Navette LPan DSze CDavoodi A(2014)Clock tree resynthesis for multi-corner multi-mode timing closureProceedings of the 2014 on International symposium on physical design10.1145/2560519.2560524(69-76)Online publication date: 30-Mar-2014
https://dl.acm.org/doi/10.1145/2560519.2560524
Chou HYu HChang SPhillips JHu AGraeb H(2011)Useful-skew clock optimization for multi-power mode designsProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132470(647-650)Online publication date: 7-Nov-2011
https://dl.acm.org/doi/10.5555/2132325.2132470
Joshi VBlaauw DSylvester DGielen G(2007)Soft-edge flip-flops for improved timing yieldProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326214(667-673)Online publication date: 5-Nov-2007
https://dl.acm.org/doi/10.5555/1326073.1326214
Hu SHu JGielen G(2007)Unified adaptivity optimization of clock and logic signalsProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326099(125-130)Online publication date: 5-Nov-2007
https://dl.acm.org/doi/10.5555/1326073.1326099
Long JKu JMemik SIsmail YGielen G(2007)A self-adjusting clock tree architecture to cope with temperature variationsProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326091(75-82)Online publication date: 5-Nov-2007
https://dl.acm.org/doi/10.5555/1326073.1326091

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.

Figures

Tables

Media

View Table of Conten