Slack borrowing in flip-flop based sequential circuits

ABSTRACT

In this paper, we have modelled the flip-flop clock to output delay dependency on the data arrival time and introduced this phenomenon in timing analysis. Traditionally, finding the minimum clock period of a flip-flop based sequential design was based on the assumption that the setup-time and clock to output delay of a flip-flop are constant and hence each stage of the pipeline can be analyzed independently. However, it is well known that the delay of a flip-flop depends on the data arrival time at its input and hence there exists an interdependence among different pipeline stages. The problem of finding the minimum clock period of such a coupled system is a non-trivial problem. In this paper, we formu-late the problem of finding the minimum clock period of a flip-flop based sequential circuit accounting for these dependencies. We show that the problem is a non-linear convex optimization problem. We propose three different solution approaches and compare their results on ISCAS '89 sequential benchmark circuits. Modeling these data arrival time dependencies we have seen a consistent decrement of approximately 50-60ps compared to the traditional approach using constant setup-time and flip-flop delays. We also show how the analysis can be extended to account for hold time constraints for short paths in the circuit.

REFERENCES

• 1: Sakallah, K.A; Mudge, T.N; Olukotun O.A "Analysis and Design of Latch-Controlled Synchronous Digital Circuits" IEEE Trans. CAD, Vol.11 Issue3, pp. 322--333, Mar. 92.
• 2: Dejan Markovic , Borivoje Nikolic , Robert Brodersen, Analysis and design of low-energy flip-flops, Proceedings of the 2001 international symposium on Low power electronics and design, p.52-55, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383093]
• 3: Mary Ann Branch , Thomas F. Coleman , Yuying Li, A Subspace, Interior, and Conjugate Gradient Method for Large-Scale Bound-Constrained Minimization Problems, SIAM Journal on Scientific Computing, v.21 n.1, p.1-23, Aug.-Sept. 1999 [doi>10.1137/S1064827595289108]
• 4: Brayton, R.K., S.W. Director, G.D. Hachtel, and L.Vidigal, "A New Algorithm for Statistical Circuit Design Based on Quasi-Newton Methods and Function Splitting," IEEE Trans. Circuits and Systems, Vol. CAS-26, pp. 784--794, Sept. 1979.
• 5: A. C. W. Grace, Computer-aided control system design using optimization methods, 1989
• 6: Han, S.P., "A Globally Convergent Method For Nonlinear Programming," Journal of Optimization Theory and Applications, Vol. 22, p. 297, 1977.
• 7: Madsen, K. and H. Schjaer-Jacobsen, "Algorithms for Worst Case Tolerance Optimization," IEEE Transactions of Circuits and Systems, Vol. CAS-26, Sept. 1979.
• 8: Powell, M.J.D., "A Fast Algorithm for Nonlineary Constrained Optimization Calculations," Numerical Analysis, ed. G.A. Watson, Lecture Notes in Mathematics, Springer Verlag, Vol. 630, 1978.
• 9: www.synopsys.com. Design Analyzer user Manuals.
• 10: T. G. Szymanski , N. Shenoy, Verifying clock schedules, 1992 IEEE/ACM international conference proceedings on Computer-aided design, p.124-131, December 1992, Santa Clara, California, United States
• 11: T. G. Szymanski, Computing optimal clock schedules, Proceedings of the 29th ACM/IEEE conference on Design automation, p.399-404, June 08-12, 1992, Anaheim, California, United States
• 12: More, J.J, D.C. Sorensen, "Computing a Trust Region Step," SIAM Journal on Scientific and Statistical Computing, Vol. 3, pp 553--572, 1983.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Verification

Keywords:
timing analysis