Optimal time borrowing analysis and timing budgeting optimization for latch-based designs

ABSTRACT

An interesting property of a latch-based design is that the combinational path delay is allowed to be longer than the clock cycle as long as it can "borrow" time from the shorter paths in the subsequent logic stages. This gives designers a lot of flexibility in designing circuits, especially high performance ones. However, it also increases the complexity in timing analysis. Finding the best clock period or determining how much time to borrow from the subsequent logic stages is difficult especially for designs containing multiple clocks, mixed-clock paths, user-specified multicycle paths, and false paths. In this article, we formulate the time borrowing problem as a linear programming problem. An optimal time borrowing solution can be found by solving the formulation. Based on this time borrowing solver, algorithms are proposed for timing optimization to achieve the optimal clock period. Experimental results show our algorithm is efficient and yields very good results.

REFERENCES

• 1: Krishna P. Belkhale , Alexander J. Suess, Timing analysis with known false sub graphs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.736-740, November 05-09, 1995, San Jose, California, United States
• 2: Jin-fuw Lee , Donald T. Tang , C. K. Wong, A timing analysis algorithm for circuits with level-sensitive latches, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.743-748, November 06-10, 1994, San Jose, California, United States
• 3: Karem A. Sakallah , Trevor N. Mudge , Oyekunle A. Olukotun, Analysis and design of latch-controlled synchronous digital circuits, Proceedings of the 27th ACM/IEEE conference on Design automation, p.111-117, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123237]
• 4: SAKALLAH, K., MUDGE, T., AND OLUKOTUN, O. 1990b. Check tc and min tc: Timing verification and optimal clocking of synchronous digital circuit. In Proceedings of IEEE/ACM ICCAD (Nov.), 552-555.
• 5: 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
• 6: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Verification

General Terms:
Design, Verification

Keywords:
Cycle stealing, latch-based design, static timing analysis, time borrowing, timing budgeting