Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Circuit simulation
Reexamination Certificate
1998-12-10
2001-11-20
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Circuit simulation
C703S014000, C703S016000, C716S030000
Reexamination Certificate
active
06321184
ABSTRACT:
BACKGROUND
1. Field of the Present Invention
The present invention generally relates to the field of digital circuits and more specifically to a mechanism for reducing latch counts of arbitrary L1-L2 digital circuit models to simplify verification and simulation tasks.
2. History of Related Art
While sequential digital circuits comprised of two latch sets (L1 and L2) driven by opposite phase clock signals have been well known for some time, conventional such circuits tend to include relatively simple combinational logic between the latch sets. In addition, these circuits tend to exhibit a one-to-one correspondence between latch sets such that each latch within the L1 latch set corresponded to a single L2 latch. The demand for extremely high speed and sophisticated sequential circuits, however, has resulted in a breakdown of this conventional design scheme. Combinational logic of ever increasing complexity is being placed between the L1 and L2 latch sets resulting in L1-L2 circuits lacking a simple correspondence between the latches of the L1 latch set and the latches of the L2 latch set. While these more complex circuits are required to deliver ever increasing functionality and performance, they have had a negative impact on the design cycle time, particularly in the simulation and verification phases of the design process. Simulation and verification of conventional L1-L2 circuits could be readily managed by simply collapsing the L1-L2 pairs into a single latch for modeling purposes. Halving the number of latches is highly desirable for model checking because of the exponential relationship between the number of latches and the state space of the circuit (where the circuit's state space refers to the universe of states that the circuit could conceivably occupy). In addition, because the collapsed model requires only one clock signal, verification of a particular sequence of events may be accomplished in N simulated clock transitions whereas the actual circuit would require 2N clock transitions, increased simulation capacity is achieved. Regrettably, however, because existing algorithms for collapsing L1-L2 pairs of conventional sequential circuitry depend upon a simple and direct correspondence between the L1 latches and the L2 latches, these algorithms are no longer effective in providing reduced models of arbitrary dual phase L1-L2 circuits.
SUMMARY OF THE INVENTION
The problems identified above are in large part addressed by a method for generating a model of an arbitrary circuit with a reduced latch count. Broadly speaking, the present invention contemplates a method of generating a digital circuit model that has fewer latches than the circuit being modeled. A determination of whether the digital circuit is reducible is made. The digital circuit suitably includes one or more primary inputs, one or more primary outputs, and a plurality of latches comprised of a level one (L1) latch set and a level two (L2) latch set. In one embodiment, the latch sets lack one-to-one correspondence. After determining that the digital circuit is reducible, one of the latch sets is replaced with combinational logic thereby reducing the latch count of the digital circuit model. In the preferred embodiment, at least half of the latches in the digital circuit are replaced.
Preferably, the determination of whether the digital circuit is reducible is accomplished by determining whether the digital circuit complies with the following four conditions: (a) the transitive fanout of the L1 latch set includes only primary inputs of the digital circuit and outputs of the L2 latch set, (b) the transitive fanout of the L1 latch set includes only inputs to the L2 latch set, (c) the transitive fanin of the L2 latch set includes only outputs from the L1 latch set, and (d) the transitive fanout of the L2 latch set includes only primary outputs of the digital circuit and inputs to the L1 latch set. In the preferred embodiment, the replacement of the latch(es) is made by identifying either the L1 latch set or the L2 latch set as a replaceable latch set and replacing each latch of the replaceable latch set with combinational logic. The L1 latch set is preferably identified as the replaceable latch set if its latch count is greater than the latch count of the L2 latch set. Similarly, the L2 latch set is identified as the replaceable latch sets if the L2 latch count is greater than the L1 latch count. (In the event of a tie, the L1 latch set is preferred to be removed since removal of the L1 latch does not require additional mux circuits to simulate initial an initial output condition of the circuit as discussed below.) Each latch of the replaceable latch set is replaced with a simple wire or, in an alternative embodiment, with a circuit such as a multiplexer (mux). An initialization latch may be included in the model to drive a select input of each mux. Means for modeling a predetermined initial condition of the primary outputs during an initial clock cycle is further provided in one exemplary embodiment.
The present invention further contemplates a storage medium configured with computer instructions for generating a model of a digital circuit comprised of primary inputs, primary outputs, combinational logic, and a plurality of latches. The plurality of latches are organized as an L1 latch set and an L2 latch set where the latch sets may or may not lack one-to-one correspondence. A replaceable latch set is then identified from the group consisting of the L1 latch set and the L2 latch set if the digital circuit is reducible and each latch of the replaceable latch set is replaced with combinational logic. In one embodiment, the storage medium is configured with instructions to determine the reducibility of the digital circuit by an iterative process including: traversing a transitive fanout path of a primary input to discover previously unidentified L1 latches and marking the digital circuit as irreducible if any of the L2 latches are encountered, traversing a transitive fanout path of each previously unidentified L1 latch to discover previously unidentified L2 latches and marking the digital circuit as irreducible if any L1 latches are encountered, and traversing a transitive fanout and fanin path of each previously unidentified L2 latch to discover any previously unidentified L1 latches and marking the digital circuit as irreducible if any L2 latches are encountered. These steps are repeated, for each primary input of the circuit, until no previously undiscovered latches are encountered. Preferably the latch count of the L1 and L2 latch sets are tracked and incremented for each previously undiscovered latch. The replaceable latch set is typically the latch set with the highest latch count (or the L1 latch set in the event of a tie).
The present invention still further comprises a computer system including a storage medium containing a representation of a digital circuit comprised of primary inputs, primary outputs, combinational logic, and a plurality of latches organized as L1 and L2 latch sets. The latch sets may lack a one-to-one correspondence. A processor of the computer system, which is coupled to the storage medium, is suitable for executing computer instructions. The storage medium further includes a plurality of computer instructions suitable for determining whether the digital circuit is reducible and, if so, creating a model of the digital circuit wherein at least one half of the plurality of latches of the digital circuit is replaced in the model by combinational logic. Preferably, the computer system determines whether the digital circuit is reducible according to the four criteria referred to previously.
REFERENCES:
patent: 5790830 (1998-08-01), Segal
patent: 5995425 (1999-11-01), Henkels et al.
patent: 6023568 (2000-02-01), Segal
patent: 6049662 (2000-04-01), Saha et al.
patent: 6058252 (2000-05-01), Noll et al.
Gerst et al., “A General Method to Double Cycle Simulation Speed”, Proceedings of the Tenth Annual IEEE International ASIC Conference and Exhibit, pp. 356-359, Sep. 1997.*
IBM Techn
Baumgartner Jason Raymond
Heyman Tamir
International Business Machines - Corporation
Lally Joseph P.
Leeuwen Leslie A. Van
Sergent Douglas W.
Teska Kevin J.
LandOfFree
Reduction of arbitrary L1-L2 circuits for enhanced verification does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reduction of arbitrary L1-L2 circuits for enhanced verification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reduction of arbitrary L1-L2 circuits for enhanced verification will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2617433