Analysis and design of latch-controlled synchronous digital circuits

ABSTRACT

We present a succinct formulation of the timing constraints for latch-controlled synchronous digital circuits. We show that the constraints are mildly nonlinear, and prove the equivalence of the nonlinear optimal cycle time calculation problem to an associated and simpler linear programming (LP) problem. We present an LP-based algorithm which is guaranteed to obtain the optimal cycle time for arbitrary circuits controlled by a general class of multi-phase overlapped clocks. We illustrate the formulation and an initial implementation of the algorithm on some example circuits.

REFERENCES

• 1: N. P. Jouppi, Timing Verification and Performance Improvement of MOS VLSI Designs, PhD thesis, Stanford University, Stanford, CA 94305- 2192, October 1984.
• 2: J. K. Ousterhout, "A Switch-Level Timing Verifier for Digital MOS VLSI," IEEE Transactions on Computer-Aided Design, vol. CAD-4, no. 3, pp. 336-349, July 1985.
• 3: M. R. Dagenais and N. C. Rumin, "On the Calculation of Optimal Clocking Parameters in Synchronous Circuits with Level-Sensitive Latches," IEEE Transactions on Computer-Aided Design, vol. 8, no. 3, pp. 268-278, March 1989.
• 4: Don T. Phillips , James J. Solberg, Operations research: principles and practice, 2nd ed., John Wiley & Sons, Inc., New York, NY, 1987
• 5: Vishwani D. Agrawal, Synchronous path analysis in MOS circuit simulator, Proceedings of the 19th conference on Design automation, p.629-635, January 1982
• 6: S H Unger , Chung-Jen Tan, Clocking schemes for high-speed digital systems, IEEE Transactions on Computers, v.35 n.10, p.880-895, Oct. 1986 [doi>10.1109/TC.1986.1676679]
• 7: T. G. Szymanski, "LEADOUT :A Static Timing Analyzer for MOS Cieuits," in 1CCAD-g6 Digest of Technical Papers, pp. 130-133, 1986.
• 8: James J. Cherry, Pearl: a CMOS timing analyzer, Proceedings of the 25th ACM/IEEE conference on Design automation, p.148-153, June 12-15, 1988, Atlantic City, New Jersey, United States
• 9: David E. Wallace , Carlo H. Séquin, ATV: an abstract timing verifier, Proceedings of the 25th ACM/IEEE conference on Design automation, p.154-159, June 12-15, 1988, Atlantic City, New Jersey, United States
• 10: K. A. Sakallah, T. N. Mudge, and O. A. Olukotun, "Analysis and Design of Latch-Controlled Synchronous Digital Circuits," Technical Report CSE- TR-31-89, University of Michigan, Dept of EECS, Ann Arbor, MI 48109-2122, October 1989.
• 11: Lance A. Glasser , Daniel W. Dobberpuhl, The design and analysis of VLSI circuits, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation; Optimization

General Terms:
Algorithms, Design