Handling special constructs in symbolic simulation

ABSTRACT

Symbolic simulation is a formal verification technique which combines the flexibility of conventional simulation with powerful symbolic methods. Some constructs, however, which are easy to handle in conventional simulation need special consideration in symbolic simulation. This paper discusses some special constructs that require unique treatment in symbolic simulation such as the symbolic representation of arrays, an efficient This paper discusses some special constructs that are unique to symbolic simulation such as the symbolic representation of arrays, an efficient symbolic method for storing arrayed instances and the handling of symbolic data-dependent delays. We present results which demonstrate the effectiveness of our symbolic array model in the simulation of highly regular structures like FPGAs, memories or cellular automata.

REFERENCES

• 1: Derek L. Beatty , Randal E. Bryant, Formally verifying a microprocessor using a simulation methodology, Proceedings of the 31st annual conference on Design automation, p.596-602, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196575]
• 2: F. M. Brown. Boolean Reasoning --- The Logic of Boolean Equations. Kluwer Academic Publishers, 1990.
• 3: Randal E. Bryant , Derek L. Beatty , Carl-Johan H. Seger, Formal hardware verification by symbolic ternary trajectory evaluation, Proceedings of the 28th conference on ACM/IEEE design automation, p.397-402, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127701]
• 4: 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]
• 5: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 6: Alan J. Hu , David L. Dill , Andreas Drexler , C. Han Yang, Higher-Level Specification and Verification with BDDs, Proceedings of the Fourth International Workshop on Computer Aided Verification, p.82-95, June 29-July 01, 1992
• 7: Innologic Systems: www.innologic-systems.com, 2001.
• 8: Alferd Kölbl , James Kukula , Robert Damiano, Symbolic RTL simulation, Proceedings of the 38th conference on Design automation, p.47-52, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378278]
• 9: B. Lin and F. Somenzi. Minimization of symbolic relations. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 88--91, Nov. 1990.
• 10: Clayton B. McDonald , Randal E. Bryant, Symbolic timing simulation using cluster scheduling, Proceedings of the 37th conference on Design automation, p.254-259, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337411]
• 11: Carl-Johan H. Seger , Randal E. Bryant, Formal verification by symbolic evaluation of partially-ordered trajectories, Formal Methods in System Design, v.6 n.2, p.147-189, March 1995 [doi>10.1007/BF01383966]
• 12: Miroslav N. Velev , Randal E. Bryant, Efficient Modeling of Memory Arrays in Symbolic Ternary Simulation, Proceedings of the 4th International Conference on Tools and Algorithms for Construction and Analysis of Systems, p.136-150, March 28-April 04, 1998
• 13: Miroslav N. Velev , Randal E. Bryant, Verification of Pipelined Microprocessors by Correspondence Checking in Symbolic Ternary Simulation, Proceedings of the 1998 International Conference on Application of Concurrency to System Design, p.200, March 23-26, 1998
• 14: Miroslav N. Velev , Randal E. Bryant , Alok Jain, Efficient Modeling of Memory Arrays in Symbolic Simulation, Proceedings of the 9th International Conference on Computer Aided Verification, p.388-399, June 22-25, 1997
• 15: Xilinx Product Data Sheets, Virtex 2.5V FPGAs: www.xilinx.com.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Verification

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Verification
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Verification

General Terms:
Verification

Keywords:
formal verification, symbolic simulation