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.
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., xe2x80x9cbugs.xe2x80x9d
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.
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 xe2x80x9cinteresting eventsxe2x80x9d 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 running each of the tests to evaluate fitnesses thereof, selecting breeders from among the tests based on the fitnesses, selecting a crossover point for each of the breeders to define first and second portions thereof, and, for each of the breeders, splicing the first portion to the second portion of another one of the breeders to form a new generation of the tests. A mutation step may be included for generating a pseudorandom marker and altering a corresponding portion of at least one of the new generation of tests at the marker. The mutation step may be performed a number of times in reverse relationship to the number of a corresponding one of the generations whereby mutations are performed less frequently in each subsequent generation so as to enhance convergence. Alternatively, mutation may be responsive to a fitness evaluation of the breeder (as a measure of convergence) so that mutation occurs less frequently as fitness of the tests increases.
According to another aspect of the invention, the method further includes evaluating a model of an integrated circuit using a final generation of the tests, fabricating a prototype integrated circuit based on the model, and evaluating the prototype integrated circuit using a final generation of the tests.
According to another aspect of the invention, a method of designing an integrated circuit includes the steps of simulating an operation of the integrated circuit, generating test vectors which converge on points in invocation space more likely to produce predetermined types of states using an order-based genetic method applied to the simulation of the integrated circuit, testing the simulation of the integrated circuit using test vectors, fabricating a prototype of the integrated circuit based on the simulation and test results obtained, and testing the prototype using the test vectors.
According to another aspect of the invention, a system for designing an integrated circuit includes a database storing a population of tests, each of the tests including at least one test vector. A simulator emulates an operation of the integrated circuit and identifies types and numbers of events examined by each of the tests. A processor is operative to sort the tests in order of the number of tests examined to provide a sorted list of the tests. The processor examines the sorted list of tests and eliminates ones of the tests from the population having types of events examined that have also been or will be examined by others of the tests. The resulting population of tests is then bred to form a next generation of tests constituting a new population until a predetermined criteria is achieved. The processor may further run each of the tests to evaluate a fitness thereof. Breeders are then selected from among the tests based on fitness, and crossover points are selected for each of the breeders to define first and second portions thereof The processor is further operative to splice a first portion of each of the breeders with a second portion of other breeders to form a second generation of tests. The crossover points may be identified by generating a pseudorandom marker.
According to another aspect of the invention, a system for exercising an integrated circuit includes a database storing a family of randomly generated initial test vectors. An order-based genetic algorithm acts on the initial test vectors to generate a new generation of test vectors which converge on points, in invocation space more likely to produce predetermined types of states. An optimization routine is used for sorting the test vectors and eliminating from the new generation of test vectors those test vectors redundantly producing particular types of states. A circuit simulator executes the test vectors and provides an output to the order-based genetic algorithm for use in generating the new generation of test vectors.
According to another aspect of the invention, a computer program having a computer readable medium with a computer program logic recorded thereon for implementing testing of an integrated circuit includes a database storing a population including a plurality of tests. A test evaluation routine identifies types and numbers of events examined by each of the tests. A sort routine sorts the tests in order of the number of events examined so as to provide a sorted list of tests. A redundant test elimination routine examines the sorted list of tests and eliminates those tests from the population which are limited to examining events which are also examined by others of the tests. A genetic algorithm is used to breed the population to form a next generation of tests constituting a new population with a control routine causing a repeated execution of the evaluation, sort, redundant test elimination and genetic algorithm routines to form successive generations of the populations until a predetermined criteria is achieved.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.