LECSIM: a levelized event driven compiled logic simulation

ABSTRACT

LECSIM is a highly efficient logic simulator which integrates the advantages of event driven interpretive simulation and levelized compiled simulation. Two techniques contribute to the high efficiency. First it employs the zero-delay simulation model with levelized event scheduling to eliminate most unnecessary evaluations. Second, it compiles the central event scheduler into simple local scheduling segments which reduces the overhead of event scheduling. Experimental results show that LECSIM runs about 8-77 time faster than traditional unit-delay event-driven interpretive simulator. LECSIM also provides the option of scheduling with respect to individual gates or with respect to fan-out free blocks. When the circuit is partitioned into fan-out free blocks, the speed increases by a factor of 2-3. With partitioning, the speed of LECSIM is only about 1.5-3.4 times slower than a levelized compiled simulation for the combinational circuits we have tested.

REFERENCES

• 1: M. A. Breuer, A. D. Frieclman, Diagnosis and Reliable De.sign of Digital Systems, Computer Science Press, Woodland Hills, CA, 1976.
• 2: Ernst G. Ulrich, Event manipulation for discrete simulations requiring large numbers of events, Communications of the ACM, v.21 n.9, p.777-785, Sept. 1978 [doi>10.1145/359588.359611]
• 3: Ernst Ulrich , Dennis Hebert, Speed and accuracy in digital network simulation based on structural modeling, Proceedings of the 19th conference on Design automation, p.587-593, January 1982
• 4: E. G. Ulrich, "Concurrent Simulation at the Switch,Gate,and Register Levels," Proceedings of" the 1985 International Test Conference, 1985, pp.703-9.
• 5: S. Gai, F. Somenzi, M. Spalla, "Fast and Coherent Simulation with Zero Delay Elements," IEEE Trans. on Computer-Aided Design, Vol. 6, No. 1, Jan., 1987, pp.85- 91.
• 6: S. P. Smith , M. R. Mercer , B. Brodk, Demand driven simulation: BACKSIM, Proceedings of the 24th ACM/IEEE conference on Design automation, p.181-187, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37915]
• 7: L.-T. Wang , N. E. Hoover , E. H. Porter , J. J. Zasio, SSIM: a software levelized compiled-code simulator, Proceedings of the 24th ACM/IEEE conference on Design automation, p.2-8, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37889]
• 8: Craig Hansen, Hardware logic simulation by compilation, Proceedings of the 25th ACM/IEEE conference on Design automation, p.712-716, June 12-15, 1988, Atlantic City, New Jersey, United States
• 9: R. E. Bryant , D. Beatty , K. Brace , K. Cho , T. Sheffler, COSMOS: a compiled simulator for MOS circuits, Proceedings of the 24th ACM/IEEE conference on Design automation, p.9-16, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37890]
• 10: Z. Barzilai, D. K. Beece, L. M. Huisman, V. S. Iyengar, G. M. Silberman, "SLS-A Fast Switch-Level Simulator," IEEE Trans. on Computer-Aided Design, Vo}L. 7, No. 8, August, 1988, pp. 838-49.
• 11: Z. Barzilai, I. L. Carter. B. K. Rosen, J. D. Rutledge, "HSS-A High-Speed Simulator," IEEE Trans. on Computer- Aided Design, Vol. 6, No. 4, July, 1987, pp. 601-16.
• 12: D. M. Lewis, "Hierarchical Compiled Event-Driven Logic Simulation," proceeding of ICCAD-89.
• 13: James R. Bell, Threaded code, Communications of the ACM, v.16 n.6, p.370-372, June 1973 [doi>10.1145/362248.362270]
• 14: P. M. Maurer, Z. Wang, C. D. Morency, 'Techniques for Multi-Level Compiled Simulation," University of South Florida, Department of Computer Science and Engineering Technical Report, CS E-89-04.
• 15: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design