Microprocessor Design Verification:Coverage Metrics

Coverage Metrics

Coverage analysis provides information on how thoroughly a design has been exercised during simulation. Coverage metrics are used to evaluate the effectiveness of random simulation vectors as well as guide the generation of deterministic tests. A number of coverage metrics have been proposed and verification engineers often use a variety of metrics simultaneously to determine test completeness. The simplest metrics used are based on the HDL description of the design. Examples are statement coverage, branch and conditional coverage, toggle coverage, and path coverage [2,4].

HDL Metrics

Statement coverage determines the number of statements in the HDL description that are executed. Conditional branch coverage metrics compute the number of conditional expressions that are toggled during simulation. Each of the important conditional expressions, e.g., if and case statements, is assigned to a monitored variable. If the variable is assigned to both 0 and 1 during simulation, both paths of the conditional branch are considered activated. Toggle coverage is the ratio of the number of signals that experienced 1-to-0 and 0-to-1 transitions during simulation to the total number of effective signals. The number of effective signals is adjusted to include only those that can possibly be toggled in the fault-free model. Another recently proposed HDL metric is based on error observability at the primary outputs of the design [12]. Observability is computed by tagging variables during simulation and checking whether the tags are propagated to the outputs. A tag calculus, similar to that of the D-algorithm used for ATPG, is introduced. Coverage is measured as the percentage of tags visible at the design outputs. The method provides a stricter measure of coverage than does HDL-line coverage. However, while HDL-based metrics are useful, they are generally not effective measures of whether logic is being functionally exercised.

Manufacturing Fault Models

A second class of coverage metrics is based on manufacturing fault models [13,14]. These metrics characterize a class of design errors analogous to faults in hardware testing and measure coverage through fault simulation. Logic design errors, such as gate substitution, missing gates, and extra inverters are injected randomly into the design. The design is then simulated using a stuck-at fault simulator. This approach has been used for measuring the coverage of ATPG tests for embedded arrays in microprocessors. ATPG is the process of automatically generating test patterns for manufacturing tests and is typically performed at the gate level. The problems with using manufacturing fault models to estimate coverage are that fault simulation is often computationally intensive, and faults introduced during the manufacturing process do not always model design errors.

Sequence and Case Analysis

Other metrics widely used in industry include sequence analysis, occurrence analysis, and case analysis [4,7]. Sequence analysis monitors sequences of events during simulation, e.g., request-acknowledge sequences, interrupt assertions, and traps. Occurrence analysis determines the presence of one-time events such as a carry-out being generated for every bit in an adder. The absence of such an event could signal a failure. Finally, case analysis consists of collecting and studying simulation statistics such as exerciser type, cycles simulated, issue rate, and instruction types [7].

State Machine Coverage

A more formal way to evaluate coverage is to look at an abstraction of the design in the form of a finite state machine (FSM) [5,15–17]. The control logic of the design is extracted as an FSM, which has a smaller state space than the original design, but which exhibits the design’s control behavior. Coverage is typically estimated by the fraction of different states reached by the FSM or the fraction of state transitions exercised during simulation. FSM coverage metrics are also used to generate test programs with high coverage, as described in Section 64.6. Binary decision diagrams (BDDs), borrowed from formal verification, are used to describe and traverse the implementation state space. A BDD is a way of efficiently representing a set of binary-valued decisions (scalar boolean functions) in the form of a tree or directed acyclic graph.

A method of transforming the high-level description of the circuit into a reduced FSM that has far fewer states than the original design is proposed in Ref. [12]. Simulation coverage is estimated by relating the fraction of transitions in the state graph traversed by this reduced FSM to the number of HDL statements exercised in the high-level description.

More recently, Moundanos et al. [17] describe the extraction of the control logic of the design from its HDL description. The control logic is extracted in the form of an FSM, which represents the control space of the entire circuit. The vectors whose coverage is to be evaluated are simulated on the FSM. Simulation coverage is estimated by the following two ratios:

A similar approach to evaluating coverage is used in Ref. [16]. Since only a subset of state variables directly controls the datapath, the noncontrolling independent state variables are removed from the state graph of the FSM. This reduced state graph is called a control event graph, and each reachable state is a control event. Coverage is evaluated in terms of the number of control events visited and the number of transitions exercised in the control event graph.

Further along the spectrum toward formal verification lie techniques dubbed smart simulation [2], which not only evaluate coverage of the given vectors, but also generate new functional tests using coverage metrics. In Section 64.6, we discuss several such techniques that use semiformal coverage metrics to derive simulation vectors. We begin with techniques based on identifying hazard patterns and later discuss more formal methods that use state machine coverage.