Randomized Test Vector Generation
Directed by Tag Coverage

Introduction and Research Objectives

Functional validation of hardware designs has become the most resource-consuming part of the design process. Validation is predominantly performed by software simulation of HDL models. A simple-minded simulation-based approach is inadequate because it doesn't provide any formal assurance that the design meets a certain specification and it doesn't provide a measure of how well the design has been exercised. Formal verification methods address the former issue, however, they have serious capacity limitations which limits their applicability. As a result of this, in the recent years, significant research activity has focused on methods that lie in between formal verification and simulation. The basic idea is to make more intelligent use of the information obtained from simulation or from partial verification.

Coverage metrics enable us to identify unchecked aspects of designs and to quantify the comprehensiveness of verification achieved. Coverage-directed simulation can significantly improve the quality of the validation achieved. The broad objective of our project is to make use of the coverage information in functional test vector generation.

Tag coverage, introduced by Devadas, Ghosh, and Keutzer (ICCAD '96) augments code coverage metrics with the notion of observability. We have selected to use tag coverage as our metric, because it is a significant improvement over straightforward code coverage metrics and is computationally more viable than state-space-based metrics. The specific goal of our project is to develop efficient algorithms that implement the "coverage feedback loop" in the figure above using tag coverage.

Current Research

Fallah et. al. have devised algorithms to compute the tag coverage achieved by simulation and to determine simulation sequences to cover a given tag. We believe that applying their algorithm to each tag would be too expensive. Therefore, we are developing an algorithm for biased random test generation with tag coverage as its goal. The conception of the algorithm is mostly completed although we have not yet addressed a few important issues. We are going to use the VIS and VERA frameworks to implement our algorithm.

Project Proposals

Below are two project proposals that can be powerful additions to the framework above. If you are interested in working on these projects, please contact me serdar@ic.eecs.berkeley.edu

Testability/Verifiability Estimation for Sequential Circuits

Functional Verification of Datapaths using Biased Random Vectors

Related Research Directions

The relationship between design errors and coverage metrics remains a largely unexplored issue. Ideally, the use of a coverage metric needs to be justified by showing that increased coverage leads to increased confidence that possible errors have been uncovered. An empirical study of this issue, even of limited scope, would be invaluable.

Related Material

ICCAD'99 Embedded Tutorial: Simulation Meets Formal Verification (with Prof. David Dill)

Coverage Metrics for Verification (Slides of Presentation at Cadence Berkeley Labs.)

Coverage Metrics and Error Models: A Literature Survey

Farzan Fallah's Presentation on "Coverage Directed Validation of Hardware Models"

Farzan Fallah's Publications on Coverage and Functional Vector Generation