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. Makovic, D; Nikolic, B; Bordersen R,W "Design and Analysis of Low Energy Flip-flop", ISLPED, pp. 52--54, Aug. 2001.
3. Branch, M.A., T.F. Coleman, y. Li, "A Subspace, Interior, and Conjugate Gradient Method for Large Scale Bound Con-strained Minimization Problems," SIAM Journal on Scientific Computing, Vol. 21, Number 1. pp 1--23, 1999.
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. Grace, A.C.W., "Computer-Aided Control System Design Using Optimization Techniques," Ph.D. Thesis, University of Wales, Bangor, Gwynedd, UK, 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. Szymanski, T.G; Shenoy, N.; "Verifying Clock Schedules" ICCAD, pp 124--131, Nov. 1992.
11. Szymanski, T.G; "Computing Optimal Clock Schedules" DAC, pp. 399--404 June '92.
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

• Hardware

  • Hardware validation

  • Robustness