Timing verification and test generation for delay and crosstalk
faults
Computer Engineering Research Center
The University of Texas at Austin
The objective of this research is to develop technique and tools for
generating tests for delay and crosstalk faults. As clock speeds increase and
the physical geometries decrease, the likelihood of such faults becomes much
higher. In addition, the greater complexity of the designs makes the
development of efficient algorithms even more critical. It has been found
that many of the structural worst-case paths within the circuit may be
false paths. Therefore, the timing verification problem is one
of determining the worst case sensitizable paths in a circuit. In addition,
the number of paths in a circuit may be exponential, so clever algorithms need
to be developed to identify the true paths without enumerating all the
possible candidate paths.
One important reason for identifying the longest true paths is to enable the
designer to attempt to optimize the delay along paths using a variety of
techniques. Such optimization procedures are crucial in meeting the required
clock speeds for a circuit, and directly translate to market share and profit
for a company. Optimized false paths do not contribute to any improvement in
the circuit but in turn may adversely affect one or more aspects of
performance, which is clearly undesirable. If an embedded module is
considered, the crucial problem is to find the longest true path in this
module when signals are applied at the inputs and observed at the outputs.
Note that existence of testability techniques for the embedded block are
irrelevant to the problem at hand, and timing verification and performance
optimization at the chip level requires the identification of functional
(i.e., sequential) worst-case paths in a design.
Selected Papers
H. Chang and J. A. Abraham,
"VIPER: An Efficient Vigorously Sensitizable Path Extractor,"
Proceedings 30th IEEE/ACM Design Automation Conference,
Dallas, Texas,
June 14-18, 1993, pp. 112-117.
Abstract
Fast and correct timing verification is a critical issue in VLSI design.
Several timing verifcation algorithms have been proposed in the last
few years. However, due to the huge computation time needed to eliminate
false paths, existing algorithms have difficulty in performing timing
verification for large circuits. This paper presents an efficient timing
verification algorithm, with a new sensitization criterion, which
directly identifies the critical path without eliminating false paths
from a path list. The inputs which sensitize the critical path are
determined as well.
Rathish Jayabharathi, Kyung Tek Lee and Jacob A. Abraham, "A Novel Solution
for Chip-Level Functional Timing Verification,"
Proceedings 1997 VLSI Test Symposium, Monterey, CA, April 28-30, 1997.
Abstract
Existing timing verification tools can provide methodologies for identifying
and optimizing critical true paths in a embedded combinational module;
however, the problem of justifying these paths to the chip level is a very
difficult one. This paper addresses the problem of timing verification at the
entire chip level. We use a critical path tool, CRITIC, to obtain critical
paths in a embedded combinational module. In order to reduce the complexity
of checking whether the module-level critical path is indeed critical at the
chip level, we use techniques from formal verification to extract the control
behavior of the circuit, and check whether there is any control sequence which
will justify the path to the chip level. The results of the experiments on
several preocessor designs show that our approach is very effective in large
sequential circuits such as microprocessors, where conventional ATPG
techniques require inordinate amounts of CPU time. The experiments also show
that the execution time does not blow up as the circuit size increases, since
we deal with a reduced control space rather than the entire state space of the
circuit.
Back to:
