Coded time-symbolic simulation using shared binary decision diagram

ABSTRACT

In this paper we propose a new timing verification technique named coded time-symbolic simulation, CTSS. We are concerned with simulation of logic circuits consisting of gates whose delay is specified only by its minimum and maximum values. We encode the cases of possible delay values of each gate by binary values and simulate all the possible combinations of the delay values by means of symbolic simulation. This simulation technique can deal with logic circuits containing feedback loops as well as combinational circuits. We implemented an efficient simulator by using a shared binary decision diagram (SBDD) as an internal representation of Boolean functions. We also propose novel techniques of analyzing the results of CTSS.

REFERENCES

• 1: M. A. Breuer and A. D. Friedman: Diagnosis & Rehable Design of Digital Systems, Computer Science Press, (1976).
• 2: N. Ishiura and H. Yasuura: On a Relation between Time-Models and Computation Time of Hazard Detection Problems, IEICE (the Institute of Electronics, Information aa~d Communication Engineers of Japan) Technical Report, COMP88-21, pp. 45-52, in Japanese, (1988)
• 3: N. Ishiura , M. Takahashi , S. Yajima, Time-symbolic simulation for accurate timing verification of asynchronous behavior of logic circuits, Proceedings of the 26th ACM/IEEE conference on Design automation, p.497-502, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74465]
• 4: N. Ishiura, H. Yasuura and S. Yajima: Time-First Evaluation Algorithnl for High-Speed Logic Simulation, Proc. ICCAD-84, pp. 197-199, (1984).
• 5: Shin-ichi Minato , Nagisa Ishiura , Shuzo Yajima, Shared binary decision diagram with attributed edges for efficient Boolean function manipulation, Proceedings of the 27th ACM/IEEE conference on Design automation, p.52-57, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123225]
• 6: 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]
• 7: M. Ohmura: Extraction of Logic and Arithmetic Functions from Combinatio~tal Circuits, Master thesis, Department of Electronics, Faculty of Engineering, Kyoto University, (1990).
• 8: William C. Carter , William H. Joyner, Jr. , Daniel Brand, Symbolic simulation for correct machine design, Proceedings of the 16th Conference on Design automation, p.280-286, June 25-27, 1979, San Diego, CA, United States
• 9: T. Yoneda, K. Nakade and Y. Tohma: A Fast Timing Verification Method Based on the Independence of Units Proc. FTCS- 19, pp. 134-141, (1989).

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Design, Verification