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.


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.


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: