Symbolic timing simulation using cluster scheduling

ABSTRACT

We recently introduced symbolic timing simulation (STS) using data-dependent delays as a tool for verifying the timing of full-custom transistor-level circuit designs, and for the functional verification of delay-dependent logic. While STS leverages efficient symbolic encodings to yield huge gains over conventional simulation methodologies, it still suffers from a problem known as event multiplication. We discuss this problem and present an event-list management technique based on event-clusters, and a new simulator which utilizes this technique. Finally, we demonstrate substantial speedups on a wide range of test cases, including exponential improvement on a simple logic chain.

REFERENCES

• 1: R. Iris Bahar , Erica A. Frohm , Charles M. Gaona , Gary D. Hachtel , Enrico Macii , Abelardo Pardo , Fabio Somenzi, Algebraic decision diagrams and their applications, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.188-191, November 07-11, 1993, Santa Clara, California, United States
• 2: R. E. Bryant. Symbolic Verification of MOS Circuits. 1985 Chapel Hill Conference on VLSI, pages 418-438, 1985.
• 3: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 4: R. E. Bryant. Boolean Analysis of MOS Circuits. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, CAD-6(4):634-639, July 1987.
• 5: C. Y. Chu. Improved Models for Switch-Level Simulation. PhD thesis, Stanford University, October 1988.
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: S. Devadas , K. Keutzer , S. Malik , A. Wang, Certified timing verification and the transition delay of a logic circuit, Proceedings of the 29th ACM/IEEE conference on Design automation, p.549-555, June 08-12, 1992, Anaheim, California, United States
• 8: I. Hajj and D. Saab. Symbolic Logic Simulation of MOS Circuits. International Conference on Circuits and Systems, pages 249-249, 1983.
• 9: Clayton B. McDonald , Randal E. Bryant, Symbolic functional and timing verification of transistor-level circuits, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.526-530, November 07-11, 1999, San Jose, California, United States
• 10: A. Salz , M. Horowitz, IRSIM: an incremental MOS switch-level simulator, Proceedings of the 26th ACM/IEEE conference on Design automation, p.173-178, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74412]
• 11: F. Somenzi. CUDD: CU Decision Diagram Package - Release 2.2.0, Online User Manual, May 1998.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
  B.8 Performance and Reliability

  C. Computer Systems Organization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Design, Measurement, Performance, Theory