**
**

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.

**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: