Multimodal optimization technique in test generation

Details Multimodal optimization technique in test generation Multimodal optimization technique in test generation

1999-12-07

2004-10-26

Jones, Hugh (Department: 2128)

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

Simulating electronic device or electrical system

C703S014000, C703S015000, C714S738000, C716S030000

Reexamination Certificate

active

06810372

ABSTRACT:

TECHNICAL FIELD
The present invention generally relates to very large scale (VLSI) testing and more particularly to the use of a genetic algorithm to generate families of test vectors to validate simulated and silicon-based VLSI performance.
BACKGROUND OF THE INVENTION
Various approaches have been taken to the design and testing of very large scale integrated (VLSI) circuits. Because of the costs of design and testing, various tools have been developed to support circuit design, evaluation, and testing. Since the mid-1970s, digital designers have utilized hardware description languages (HDLs), the most prominent of which are Verilog and the IEEE standard VHDL. While Verilog is a C-like language, VHDL provides similar functionality in an Ada-like environment. These tools allow the designer to describe circuits at a very high level of abstraction as well as at gate and switch levels to design VLSI integrated circuits, provide layouts and support chip fabrication. Thus, a primary use of HDLs is to simulate designs before the design is committed to silicon. After a design is proved through simulation, and committed to silicon prototyping, the prototype device is then subjected to additional testing to verify operation and compliance with the specifications.
At both the simulation stage prior to IC fabrication and after the design has been fabricated in the form of a VLSI, testing is carried out using tests of predetermined test vectors which exercise and drive either the simulated or the actual fabricated VLSI to verify operation and identify faults, i.e., “bugs.”
Typically, test design starts with the generation of random test vectors which may be optimized to cause the circuitry under test to enter particular states. The tests may be designed to provide three types of coverage: block, where an encapsulated piece of simulation code is exercised; expression coverage, which verifies evaluation of particular expressions; and path coverage, which uses a state machine paradigm to ensure proper operation of the state machine. Ultimately, the test vectors should provide for maximal coverage so as to identify all faults in either the simulation or the prototype.
Because of the extreme resources required to fully test complex circuitry, it is not feasible to fully exercise all paths and ensure that there are no holes in either the simulation or the test. Instead, tests are evaluated to determine if they hit interesting corner cases or other conditions which are more likely to identify faults or limitations of the design (e.g., register overflow, excess wait cycles, etc.). Collections of such tests and their component test vectors may be maintained as a library, particularly if such tests have previously been found to identify bugs in the design.
The generalized method of testing a VLSI device such as an ASIC (application-specific integrated circuit) is shown in
FIG. 1
including Functional Simulation and Silicon Testing processes. Tests are for use in both the simulations framework and actual silicon test framework. In the simulation framework, these tests are normally defined at the transaction level, the tests being specified by means of test profiles which include knobs (or parameters.) Thus, for example, in a processor bus there are several parameters for a transaction on the bus such as transaction type, transaction length, number of snoop stalls for the transaction, response delay, response type, etc. In contrast, tests in the actual silicon framework are defined in terms of bit vectors. The bit vectors are typically extracted from the simulation framework itself. Chip pin observer code in the simulations framework captures these bit vectors which are then fed into actual silicon in the chip testers.
At entry point
10
, specified interesting events are defined. These interesting events include (a) software counters embedded in the simulation framework that indicate corner cases likely to get the ASIC to interesting states (e.g., queue filled, hard to reach states in state machines, interesting bus conditions, etc.), and (b) hardware counters built into a chip that flag corresponding interesting chip states. Test Profile data is provided at an initial step
20
and used to control the operation of a Test Generator
30
and the application of tests from library
40
. Tests from Test Generator
30
are used by Simulator
50
to exercise the HDL representation of the ASIC. The results of this testing are then used at step
60
to determine the quality of the test which is in turn used to redefine the tests maintained in library
40
. Library
40
is then used to exercise Actual Silicon at step
70
so as to identify an faults introduced during ASIC fabrication.
A problem with this methodology is that it is often difficult to design a minimal set of test vectors which provide maximum coverage of such interesting events and conditions. This is particularly true when tests developed and used to evaluate the simulation may be deficient in identifying faults introduced during or because of conditions unique to the fabrication process and because it is necessary to reengineer the tests to accommodate the VLSI once committed to and produced in silicon. That is, present methods are unable to identify and define a minimum set of tests using the simulation framework which ensure high functional coverage of the chip and would likely identify any faults introduced during fabrication during actual silicon testing.
Accordingly, an object of the invention is to provide a method and system for generating tests and test vectors to validate simulated and silicon-based VLSI performance and operation, identify errors and faults in logic, layout, circuit spectrum, fabrication and otherwise. Another object of the invention is to provide a dynamic test generation method and system which heuristically adapts to particular test environments and conditions and translates from simulation, to prototyping, to production-stage quality control applications.
SUMMARY OF THE INVENTION
These and other objects, features and technical advantages are achieved by a method of and system which uses a genetic algorithm to breed a population of tests from an initial set of random test vectors to maximize coverage and confirm circuit operation. The resultant tests subject the VLSI to extreme conditions by observing “interesting events” likely to produce or require recovery from fault conditions. The resulting tests are then sorted according to the conditions or events included in or exercised by the test. The list is then reviewed in order of increasing number of events covered by individual tests with the elimination of tests covering events or conditions already covered by tests later in the ordered list. Thus, the minimal set of tests spanning particular events or interesting conditions is obtained.
A method according to the invention tests an integrated circuit (simulated or in silicon) by providing a population of tests. Types and numbers of events are examined and identified for each of the tests. The tests are then sorted in order of the number of events examined to provide a sorted list of the tests. The sorted list of tests is examined and those tests having events which are duplicated by other tests are eliminated. The remaining population of tests are then bred using a genetic algorithm and possibly including new randomly generated tests to form a new generation of tests constituting a new population. The process of categorizing tests to identify number and types of events evaluated by each of the tests, sorting and pruning to eliminate redundant tests, and using a genetic algorithm to converge the tests results in an optimized population having a predetermined criteria (e.g., maximal spanning).
According to a feature of the invention, each of the tests comprises at least one test vector defining a state condition of the integrated circuit. The integrated circuit in this case may be either a simulation or a physical integrated circuit.
According to another aspect of the invention, the step of breeding includes runni

Affiliated with

Also associated with

Rating

Multimodal optimization technique in test generation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multimodal optimization technique in test generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multimodal optimization technique in test generation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3271654