Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Circuit simulation
Reexamination Certificate
1998-07-14
2001-04-24
Teska, Kevin J. (Department: 2763)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Circuit simulation
C703S017000, C703S019000, C703S027000
Reexamination Certificate
active
06223141
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This work addresses the problem of speeding up levelized compiled code generation based functional (delay independent) logic simulation for synchronous digital systems. In particular, the invention relates to methods for manipulation of the netlist to be simulated so that the simulation speed is increased.
2. Description of Related Work
In designing digital systems, it is important to validate the design of the interconnected logic gates. This may be referred to as design validation.
For today's large and complex systems, it is preferred to validate the design by simulation. Design validation by simulation is a key step in the design cycle of digital systems. It is also one of the most time consuming. Each time a design is iterated, it must be re-simulated until a satisfactory confidence level is achieved.
Simulation is performed at various levels of abstraction during the design process. One level of simulation involves delay-independent (i.e. purely functional) cycle-based logic simulation of synchronous digital circuits. At this level, the simulator is required to determine the output sequence produced by a circuit for a sequence of input vectors, independent of the delays associated with the gates and wires. In effect, the simulator determines the output vector for each input vector by evaluating the Boolean equations associated with each gate in the circuit. The circuit is assumed to possess feedback through flip-flops. Therefore, the circuit can be evaluated for the next input vector only after the evaluation for the current input vector is complete. This type of simulation where the input vectors must be simulated sequentially in this is manner is said to be cycle-based sequential simulation.
It will be understood that circuit timing may be checked using static timing analysis. Circuit initialization may be checked using an event driven front end used for simulation of a few thousand cycles. The bulk of the verification tests are done using a pure binary valued functional simulator.
This invention relates particularly to delay-independent (i.e. purely functional) cycle-based logic simulation of synchronous digital circuits. This invention relates, more particularly, to solving the problem that prior simulation methods have been too slow.
Two techniques have traditionally been applied for logic simulation at this level. One technique is event-driven simulation. For their useful background on this topic, the following are incorporated by reference:
M. A. Breuer and A. D. Friedman.
Diagnosis and Reliable Design of Digital Systems.
Computer Science Press, Inc., 1976.
E. Ulrich. Exclusive simulation of activity in digital networks. In
Communications of the ACM,
volume 13, pages 102-110, February 1969.
The other to the two techniques traditionally applied for logic simulation at this level is levelized compiled-code (LCC) simulation. The following, which are incorporated by reference, provide useful background on prior efforts in LCC simulation:
M. Chiang and R. Palkovic. LCC simulators speed development of synchronous hardware. In
Computer Design,
pages 87-91, 1986.
N. Ishiura, H. Yasuura, T. Kawata, and S. Yajima. High-speed logic simulation on a vector processor. In
Proceedings of the International Conference on Computer
-
Aided Design,
pages 119-121, November 1985.
G. F. Pfister. The Yorktown Simulation Engine: Introduction. In
The Proceedings of the Design Automation Conference,
pages 51-54, June 1982.
L. T. Wang, N. H. Hoover, E. H. Porter, and J. J. Zasio. SSIM: A software levelized compiled-code simulator. In
The Proceedings of the Design Automation Conference,
pages 2-8, June 1987.
FIG. 1
presents a high-level view of how these simulators are used. It has been observed in practice that levelized compiled-code simulation is much faster than event driven simulation for purely functional simulation of current designs.
Event-Driven (ED) Simulation
In event-driven simulation, the output of a gate is evaluated only when there is a change in the value of one of its inputs. In effect, gates are dynamically scheduled for evaluation at run time. The running time of this approach for some input vector is roughly proportional to the number of signal transitions (or events) in the circuit for that input vector. Consequently, this approach tends to be very fast when the amount of activity (ratio of the number of signal transitions to the number of signals) in the circuit is low (between 1 and 20%). In practice though, much higher activity is observed in current designs as maximal use of silicon is attempted through parallelism and pipelining. For more information on this point, see the following publication, incorporated by reference for its background:
E. J. Shriver and K. A. Sakallah. Ravel: Assigned-delay compiled-code logic simulation. In
Proceedings of the International Conference on Computer
-
Aided Design,
pages 364-368, November 1992.
A large overhead must be paid in event-driven simulation for the flexibility of scheduling gates dynamically. A consequence of this overhead is that when the activity level increases, event-driven simulation becomes much slower than the levelized compiled-code approach described below.
On the positive side, dynamic scheduling of gates allows arbitrary signal propagation delay models to be incorporated into this approach. This allows essentially the same event-driven framework to be used for both delay-dependent and delay-independent simulation, as well as for the simulation of circuits with asynchronous feedback. As mentioned in the Shriver and Sakallah publication, the proliferation of synchronous designs has made the need for simulation of asynchronous feedback virtually unnecessary. The event-driven approach is still required for delay-dependent simulation, although attempts have been made to incorporate arbitrary delays into the compiled-code paradigm.
Levelized Compiled-Code (LCC) Simulation
In levelized compiled-code simulation, all the gates are evaluated for each input vector even if the gate output has not changed since the last input vector. As the name suggests, the circuit is first levelized topologically. Here, the level of a gate is defined as the largest number of gates on any path to it from a primary input. The gates are always evaluated in the order of increasing level. This ordered sequence of gates is translated into C-code. Each gate is either coded using its constituent Boolean equations or by means of a look-up table characterizing its I/O behavior. This C-code is then compiled into a binary which accepts as input the simulation vectors, and generates as output the output vector that would be produced by the original circuit.
Given that the gates are scheduled statically, a restriction of the levelized compiled-code approach is that non-zero signal propagation delays cannot be incorporated into the simulation easily. The run time for each input vector is proportional to the number of gates in the circuit, or to be more precise, the total number of basic two-input Boolean operations (AND, OR, NOT) that can be implemented by a single machine instruction.
A measure of the number of basic Boolean operations is the total number of literals in the factored form in the circuit (see: R. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. Wang, “MIS: A multiple-level logic optimization system” in
IEEE Transactions on CAD,
volume C-6, pages 1062-1081, November 1987; incorporated by reference for its useful background information).
In the absence of feedback, it has been proposed to simulate a number of vectors in parallel by taking advantage of the multiple bits per word on modern computers (see: Z. Barzilai, J. L. Carter, B. K. Rosen, and J. D. Rutledge, “HSS—A High Speed Simulator” in
IEEE Transactions on Computer
-
Aided Design,
volume C-6, pages 601-617, July 1987; incorporated by reference herein for its useful background information).
Finally, since the binary being executed is free of all branch statements, this results in very good exploitat
NEC USA Inc.
Phan Thai
Sughrue Mion Zinn Macpeak & Seas, PLLC
Teska Kevin J.
LandOfFree
Speeding up levelized compiled code simulation using netlist... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Speeding up levelized compiled code simulation using netlist..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Speeding up levelized compiled code simulation using netlist... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2444379