Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Circuit simulation
Reexamination Certificate
1999-06-18
2004-11-09
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Circuit simulation
C703S015000, C716S030000, C324S650000, C714S033000, C714S037000
Reexamination Certificate
active
06816825
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to the automatic generation of vector sequences for the validation of circuit design. In particular, the vector sequences generated are used as inputs to a circuit under simulation to determine whether the desired outputs are produced. More particularly, the invention is embodied in a system, a method, and a program product for the automatic generation of vector sequences for the validation of circuit design, in a manner that targets an observability based coverage metric.
The following papers provide useful background information on the indicated topics, all of which relate to this invention, and are incorporated herein by reference:
A finite state machine (FSM) implementation model:
R. C. Ho, C. H. Yang, M. A. Horowitz, and D. L. Dill, “Architecture Validation for Processors,” in
Proceedings of the
22
nd Annual Symposium on Computer Architecture,
June 1995.
Statement Coverage in HDL Code:
K.-T. Cheng and A. S. Krishnakumar, “Automatic Functional Test Generation Using the Extended Finite State Machine Model,” in
Proceedings of the
30
th
Design Automation Conference
, pp. 86-91, June 1993.
Observability-based statement coverage metric:
S. Devadas, A. Ghosh, and K. Keutzer, “An Observability-Based Code Coverage Metric for Functional Simulation,” in
Proceedings of the International Conference on Computer
-
Aided Design,
pp. 418-425, November 1996.
Evaluation Procedure for Observability-Based Statement Coverage Metric:
F. Fallah, S. Devadas, and K. Keutzer, “OCCOM: Efficient Computation of Observability-Based Code Coverage Metrics for Functional Simulation,” in
Proceedings of the
35
th
Design Automation Conference,
pp. 152-157, June 1998.
Recent Algorithms for Solving Hybrid-Satisfiability (HSAT) Problems:
F. Fallah, S. Devadas, and K. Keutzer, “Functional Test Generation Using Linear Programming and 3-Satisfiability,” in
Proceedings of the
35
th
Design Automation Conference,
pp. 528-533, June 1998.
Application of SAT Algorithms in CAD:
T. Larrabee, “Test Pattern Generation Using Boolean Satisfiability,”
IEEE Transactions on Computer
-
Aided Design,
vol. 11, pp. 4-15, January 1992.
Verilog:
D. E. Thomas and P. R. Moorby,
The Verilog Hardware Description Language.
Kiuwer Academic Publishers, Boston, Mass., second ed., 1994.
Vis verification system:
R. K. Brayton and others, “VIS: A System for Verification and Synthesis,” in
Proc. Computer
-
Aided Verification,
vol. 1102, pp. 428-432, June 1996.
There will now be provided a discussion of various topics to provide a proper foundation for understanding the invention.
Digital Computers
Digital computers have made possible many changes in the scientific, industrial, and commercial arenas. Today, many businesses cannot function without the aid of working information systems. Many special-purpose and general-purpose computers are well-known.
A block diagram of a simple general-purpose digital computer is shown in
FIG. 1
, although the drawing figure could also pertain equally well to a special-purpose digital computer, depending on the functionality provided. Reference numeral
10
indicates the general-purpose digital computer. Such a computer may include a central processing unit
100
, also referred to as a CPU. The main memory
110
may be understood to be a RAM. The computer in this a simplified diagram has only one I/O processor
120
. The I/O processor
120
controls I/O devices
130
. The I/O devices
130
include a display, a keyboard, a printer, a disk drive, and a mouse. It will be understood that this diagram is for explanatory purposes only, and is not intended in any way to limit the invention.
The CPU
100
includes a control unit, an ALU, and registers. The control unit is responsible for fetching instructions from main memory
110
and determining their type. The ALU performs operations, such as ed. and Boolean AND, needed to carry out the instructions. The registers of the CPU
100
provide a small, high-speed memory used to store temporary results and certain control information. The registers may each be designated a certain function, or may be general-purpose registers. Included in the registers is a program counter PC, which points to the next instruction to be executed. There is also an instruction register IR, which holds the instruction currently being executed.
It will be appreciated that the CPU
100
, the main memory
110
, and the I/O processor
120
are interconnected by buses. Communications between these different units takes place across the buses.
Thus, it can be seen that a digital computer is an interconnection of digital modules. There are modules within the CPU
100
, and be CPU, the main memory
110
, and the I/O processor
120
also may be thought of as modules themselves. On a larger scale, when these complements are all included in the same container, this container may be understood to be a module, and the different I/O devices (such as display and keyboard) may be understood to be modules themselves.
Miniaturization
The miniaturization of digital computers is a useful and exciting phenomenon. A CPU enclosed in a small integrated circuit package is referred to as a microprocessor. A microprocessor is just one example of the miniaturization of digital components. When a circuit or a combination of related circuits is miniaturized and produced on a single chip, such a chip may be called an integrated circuit.
Special production techniques are required to produce an integrated circuit. Such production techniques add greatly to the cost of the final product.
In view of the expense of producing a microprocessor, is very important to ensure that there are no errors in the design that would render the microprocessor unusable. Modern, high-performance microprocessors are extremely complex, however, and require substantial validation efforts to ensure functional correctness. Modern microprocessors contain many architectural features designed to improve performance, including branch prediction, speculative execution, lockup free caches, dynamic scheduling, superscalar execution, and the like. Such features and complexity to a microprocessor, because they constitute modules within the CPU which interact with each other.
As a matter of economics, the great expense of producing a miniaturized microprocessor and then testing it makes it impractical to verify the design on an actual prototype of the microprocessor. Instead of testing an actual microprocessor produced according to a given design, the design is tested by simulating the operation of the microprocessor on a computer.
Simulation
To simulate the operation of a physical machine, such as a microprocessor, in a digital computer, it is necessary to represent the functionality of the microprocessor in some manner. One of the ways to represent the functionality of a microprocessor in a form usable by a computer is with the hardware description language HDL. In particular, the desired microprocessor is modeled using HDL. The HDL model describes the interconnections of the arithmetic, logic, and memory modules included in a microprocessor.
An HDL model of a microprocessor is comprised of statements in the hardware description language HDL.
There are computer applications available which will accept, as input, an HDL model of a microprocessor. Based on this input HDL model, the computer application will simulate different aspects of the operation of the microprocessor. The precise aspects of this operation to be simulated may be controlled by the person using the computer application.
It will be appreciated, that the operation of the microprocessor (that is, the microprocessor being simulated) cannot be tested without some inputs being provided to the simulated microprocessor. When the simulated microprocessor is provided with inputs, it will respond in certain predefined ways, providing the design is correct. Such a series of inputs may be referred to as a simulation vector (or, for linguistic convenience, simply as a vector). As used herein, “vector” and “vector sequence” will gener
Ashar Pranav
Devadas Srinivas
Fallah Farzan
NEC Corporation
Sharon Ayal
Sughrue & Mion, PLLC
Teska Kevin J.
LandOfFree
Simulation vector generation from HDL descriptions for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Simulation vector generation from HDL descriptions for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simulation vector generation from HDL descriptions for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3288063