Latch inference using dataflow analysis

Details Latch inference using dataflow analysis Latch inference using dataflow analysis

2000-06-12

2004-04-20

Frejd, Russell (Department: 2123)

Data processing: structural design, modeling, simulation, and em

Simulating electronic device or electrical system

Circuit simulation

C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

06725187

ABSTRACT:

FIELD OF THE INVENTION
The invention relates generally to the field of electronic design automation (EDA), and particularly to a system and method for improving the speed and accuracy of latch inference in EDA.
BACKGROUND OF THE INVENTION
Discrete function simulation is one of the core tasks in rapid system prototyping and debugging in EDA. Improvements in discrete function simulation time can dramatically improve system design time. Discrete function simulators address the problem of finding the values of circuit outputs, given a circuit design and a vector of circuit input values. One example of a discrete function simulator is a logic simulator.
Until recently, conventional logic simulators in the EDA environment operated in an event-driven manner, wherein a plurality of wires connect a plurality of logic elements within a circuit-under-test. As input vectors cascade through the logic elements the logical value (1 or 0) of each wire may change. Each change in the value of a wire is regarded as an event. A memory queue stores the events. When the logical value of a wire changes, each gate having the modified wire as an input is subsequently tested to determine whether the logical value on the output wire of the gate has changed. A change in the value on this output wire is a new event which is placed in the memory queue. This process continues until all of the gates within the circuit-under-test have been processed.
The performance of such conventional logic simulators is therefore dependent upon the number of gates in the simulated circuit and is limited by the size and speed of the memory queue. Hundreds of thousands or even millions of gates may be present on a single integrated circuit (IC), e.g., an application specific integrated circuit (ASIC) or circuit implemented on a programmable or reprogrammable logic device. Simulating all of the gates and events occurring on such an IC requires a significant amount of time and computer resources.
To address the need for a more efficient logic simulator which functions in a manner independent of the number of gates in a circuit and the number of events occurring in a system, McGeer, et al. invented and patented an event-independent SYSTEM AND METHOD FOR SIMULATING DISCRETE FUNCTIONS USING ORDERED DECISION ARRAYS, disclosed and claimed in U.S. Pat. No. 5,752,000 (which is incorporated herein by reference), filed Aug. 2, 1994, issued May 12, 1998, and owned by Cadence Design Systems, Inc., the assignee of the present invention.
The reader will benefit at this point in the background discussion from a brief history of logic design. When the now-ubiquitous hardware design tools Verilog and VHDL were first introduced, no single logic synthesis methodology was in widespread use and the only common verification technology was event-driven simulation. Since that time, however, logic synthesis (the automated optimization of a digital circuit for die area, speed, or power) has become a ubiquitous tool among digital designers. Further, a welter of modern verification tools have been added to the circuit designer's desktop: timing analysis (which determines the speed of a digital circuit); formal verification (in which the correctness of the design is proven mathematically); and more efficient forms of simulation (“cycle” simulation) in which only a small proportion of the actual assignments of the circuit are performed, and thus much greater speed is gained.
All of these latter-day tools operate not on the HDL description of the circuit, but on the circuit itself. However, for a variety of reasons, Verilog and VHDL continue to dictate the input format to all circuit verification tools including synthesis tools (which optimize circuit structure for size, complexity, speed, or consumed power), timing analysis tools (which determine how long a circuit takes to perform its function), and formal verification tools (which formally and completely prove circuit properties). The need, therefore, to rapidly, efficiently, and accurately divine the underlying circuit from an HDL description of a circuit becomes paramount.
Unfortunately, HDLs have their basic semantics strongly rooted in their event-driven simulation origins. In particular, in event-driven simulation, each variable is tied to a memory location: each assignment to the variable is stored in the memory location, and remains the value of the variable until the variable is freshly assigned. In the underlying circuit, this specific behavior can only be realized by attaching a memory circuit to each variable—known in the art to which the present invention pertains as a “latch”. However, such latches are both expensive in circuit area and introduce a one-cycle delay to each assignment. For this reason, only about 5-10% of variables in a typical circuit are latched in this manner.
The major problem in finding the underlying circuit from a description in an HDL file is to determine which small set of the variables in the HDL file should be so “latched”. The method must be fast and efficient in all cases, since circuits are often very large, and embody a rule so simple and easy to understand that a competent circuit designer can easily determine which variables in his program will be latched in the realized circuit. This last element is particularly crucial: determination of which signals in a circuit are latched is of great importance in circuit design, and thus must be controlled by the designer.
Thus, while event-independent simulation (often referred to in the industry as fast function evaluation or cycle simulation) has proven advantages, the change has brought severe complications. A cycle simulator cannot seamlessly replace event-driven simulators intended for use with behavioral languages such as Verilog and VHDL. The semantics of event-driven simulation languages find their foundation in the event queue, and so removal of the queue makes simulation difficult. Thus, cycle simulators are based upon a precisely defined, cycle simulating HDL, which comprises a set of state variables and combinational logic. In cycle simulating HDL, combinational logic re-evaluates its output in zero time (clock-independent) in response to an input change, and therefore functions in a manner independent of an event queue.
Put simply, latch inference is the process of determining whether a given design variable is sequential (necessitating a latch-type memory bit) or combinational (no memory needed).
One available approach, provided in the Design Compiler® software tool sold by Synopsis, Inc., comprises tautology checking, wherein every possible value of a given variable is analyzed, and when any unassigned circumstance is encountered, a latch or more complex sequential element is assigned. However, this tautological method involves a global analysis of the whole design, an exhaustive computation which consumes considerable and costly computational resources, making it impractical for a designer to precisely determine which signals are latched. This system is described and claimed in U.S. Pat. No. 5,530,841 to Gregory, et al., incorporated herein by reference. Thus, Gregory, et. al attach a logic expression to each assignment of a variable, and then determine whether the disjunction of these logic expressions is tautologous. It is therefore assumed in the Gregory approach that fewer latches are better, i.e., that the challenge is one of simple optimization with a simple objective function. This approach is flawed in both the simplicity of its conception and complexity of its execution.
SUMMARY OF THE INVENTION
Since tautology checking is an exhaustive and computationally intensive process (i.e., NP-complete), there remains a need in the art for a more refined yet thorough approach to latch inference. More particularly, a fundamental problem in latch inference is determining whether or not a variable is always directly assigned. If it is, then it is assumed that the variable has no need of storage, since its value is determined independent of any stored value. If not, then it is assumed that the stored v

Affiliated with

Also associated with

Rating

Latch inference using dataflow analysis does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Latch inference using dataflow analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Latch inference using dataflow analysis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3214513