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

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: John P. Fishburn, Clock Skew Optimization, IEEE Transactions on Computers, v.39 n.7, p.945-951, July 1990 [doi>10.1109/12.55696]
• 5: Ivan S. Kourtev , Eby G. Friedman, Clock skew scheduling for improved reliability via quadratic programming, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.239-243, November 07-11, 1999, San Jose, California, United States
• 6: Xun Liu , Marios C. Papaefthymiou , Eby G. Friedman, Maximizing performance by retiming and clock skew scheduling, Proceedings of the 36th ACM/IEEE conference on Design automation, p.231-236, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309919]
• 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: José Luis Neves , Eby G. Friedman, Optimal clock skew scheduling tolerant to process variations, Proceedings of the 33rd annual conference on Design automation, p.623-628, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240636]
• 11: M. Saitoh , M. Azuma , A. Takahashi, Clustering based fast clock scheduling for light clock-tree, Proceedings of the conference on Design, automation and test in Europe, p.240-245, March 2001, Munich, Germany
• 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.
• 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.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.1 Control Design Styles

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.2 Control Structure Performance Analysis and Design Aids
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Performance