Efficient circuit partitioning to extend cycle simulation beyond synchronous circuits

ABSTRACT

Cycle simulation techniques, such as levelized compiled code, can ordinarily be applied only to synchronous designs. They usually cannot be applied to designs containing circuit features like combinational paths, multiple clock domains, generated clocks, asynchronous resets, and transparent latches. This paper presents a novel partitioning algorithm that partitions a non-cycle-simulatable circuit containing these features into sub-circuits that can be cycle simulated. Cycle simulation techniques can be applied to the individual sub-circuits, and the whole collection of sub-circuits can be simulated together using conventional co-simulation techniques. Empirical results demonstrate that this approach brings the benefits of cycle simulation to circuits that were previously impossible to cycle simulate. The partitioning algorithm requires time and space linear in the size of the circuit, and in practice is very fast. We also discuss how the key ideas presented here can be applied to accelerate HDL simulation.

REFERENCES

• 1: Pranav Ashar , Sharad Malik, Fast functional simulation using branching programs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.408-412, November 05-09, 1995, San Jose, California, United States
• 2: Zeev Barzilai, J. Lawrence Carter, Barry K. Rosen, and Joseph D. Rutledge. Hss-a high speed simulator. IEEE Transactions on Computer-Aided Design, pages 601- 617, July 1987.
• 3: Robert S. French , Monica S. Lam , Jeremy R. Levitt , Kunle Olukotun, A general method for compiling event-driven simulations, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.151-156, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217522]
• 4: 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
• 5: David M. Lewis. Hierarchical compiled event-driven logic simulation. In Proceedings of the IEEE International Conference on Computer-Aided Design, November 1989.
• 6: Patrick C. McGeer , Kenneth L. McMillan , Alexander Saldanha , Alberto L. Sangiovanni-Vincentelli , Patrick Scaglia, Fast discrete function evaluation using decision diagrams, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.402-407, November 05-09, 1995, San Jose, California, United States
• 7: L. W. Nagel. Spice2: A comuter program to simulate semiconductor circuits. Technical Report Rep. No ERL-M520, Electronics Research Laboratory, University of California, Berkeley, CA, May 1975.
• 8: 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]
• 9: 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]
• 10: Zhicheng Wang , Peter M. Maurer, LECSIM: a levelized event driven compiled logic simulation, Proceedings of the 27th ACM/IEEE conference on Design automation, p.491-496, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123349]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification

Keywords:
logic simulation, cycle simulation, circuit partitioning, levelized compiled code