Site News  |   Monitor Keywords  |   Monitor Archive  |   Organizer  |   Account Info  |

Performing utilization of traces for incremental refinement in coupling a structural overapproximation algorithm and a satisfiability solver

Performing utilization of traces for incremental refinement in coupling a structural overapproximation algorithm and a satisfiability solver description/claims

This application is a continuation of U.S. patent application Ser. No. 11/340,534, filed on Jan. 26, 2006, entitled “Method and System for Performing Utilization of Traces for Incremental Refinement in Coupling a Structural Over-Approximation Algorithm and a Satisfiability Solver” which is co-related to U.S. patent application Ser. No. 11/340,477, filed on even date herewith, the contents of which are incorporated herein by reference.

1. Technical Field

The present invention relates in general to verifying designs and in particular to reducing resource consumption during verification. Still more particularly, the present invention relates to a system, method and computer program product for performing utilization of traces for incremental refinement in coupling a structural overapproximation algorithm and a satisfiability solver.

2. Description of the Related Art

With the increasing penetration of processor-based systems into every facet of human activity, demands have increased on the processor and application-specific integrated circuit (ASIC) development and production community to produce systems that are free from design flaws. Circuit products, including microprocessors, digital signal and other special-purpose processors, and ASICs, have become involved in the performance of a vast array of critical functions, and the involvement of microprocessors in the important tasks of daily life has heightened the expectation of error-free and flaw-free design. Whether the impact of errors in design would be measured in human lives or in mere dollars and cents, consumers of circuit products have lost tolerance for results polluted by design errors. Consumers will not tolerate, by way of example, miscalculations on the floor of the stock exchange, in the medical devices that support human life, or in the computers that control their automobiles. All of these activities represent areas where the need for reliable circuit results has risen to a mission-critical concern.

In response to the increasing need for reliable, error-free designs, the processor and ASIC design and development community has developed rigorous, if incredibly expensive, methods for testing and verification for demonstrating the correctness of a design. The task of hardware verification has become one of the most important and time-consuming aspects of the design process.

Among the available verification techniques, formal and semiformal verification techniques are powerful tools for the construction of correct logic designs. Formal and semiformal verification techniques offer the opportunity to expose some of the probabilistically uncommon scenarios that may result in a functional design failure, and frequently offer the opportunity to prove that the design is correct (i.e., that no failing scenario exists).

Unfortunately, the resources needed for formal verification, or any verification, of designs are proportional to design size. Formal verification techniques require computational resources which are exponential with respect to the design under test. Simulation scales polynomially and emulators are gated in their capacity by design size and maximum logic depth. Semi-formal verification techniques leverage formal algorithms on larger designs by applying them only in a resource-bounded manner, though at the expense of incomplete verification coverage. Generally, coverage decreases as design size increases. Overapproximation is frequently used to reduce the size of a design in order to increase verification coverage.

Unfortunately, the prior art provides only limited tools for the merger of various verification techniques. Specifically, the prior art does not provide an effective method for performing utilization of traces for incremental refinement in coupling a structural overapproximation algorithm and a satisfiability solver.

A method, system and computer program product for performing verification are disclosed. The method includes creating and designating as a current abstraction a first abstraction of an initial design netlist containing a first target and unfolding the current abstraction by a selectable depth. A composite target is verified, using a satisfiability solver and, in response to determining that the verifying step has hit the composite target, a counterexample is examined to identify one or more reasons for the first target to be asserted. One or more refinement pairs are built by examining the counterexample and a second abstraction is built by composing the refinement pairs. A new target is built over one or more cutpoints in the first abstraction that is asserted when the one or more cutpoints assume values in the counterexample, and the new target is verified with the satisfiability solver.

The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as a preferred mode of use, further objects and advantages thereof, will best be understood by reference to the following detailed descriptions of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

FIG. 1 depicts a block diagram of a general-purpose data processing system with which the present invention of a method, system and computer program product for performing verification by closely coupling a structural overapproximation algorithm and a structural satisfiability solver may be performed;

FIG. 2 is a high-level logical flowchart of a process for performing verification by closely coupling a structural overapproximation algorithm and a structural satisfiability solver; and

FIG. 3 is a high-level logical flowchart of a process for performing utilization of traces for incremental refinement.

• Provisional Patent
• Utility Patent

• What Is a Patent?
• What Is a Trademark or Servicemark?
• What Is a Copyright?
• Patent Laws