A method for finding the statically sensitized critical path in VLSI circuits

Abstract

The longest sensitizable paths of a circuit are referred to as the critical paths of the circuit. Finding all the critical paths in a circuit is called the critical path problem. There are various methods at present to find the critical path of a circuit. The first is the block-oriented technique in which delays along all paths are summed up without taking into account the functional relationships between signals. The second approach, called timing analysis, is a path enumeration technique in which the longest structural paths are examined, one path at a time, to see if one can be sensitized. A third approach, called timing simulation, is a vector-dependent method in which each input vector is simulated in order to find the sensitized paths. Most research until now has focused on finding single, path-oriented algorithms that could solve this problem more accurately and/or more efficiently. Due to the huge number of paths contained in some circuits, we feel that a more effective way is to attack this problem with a series of deterministic sieves, trying to process and learn as much information as possible at each level before proceeding on to the next level. Using the results obtained from the previous levels, successively more sophisticated algorithms can be developed to process the increasingly difficult but smaller sections of the circuit until the longest true paths have been found. In our timing analysis system, all circuits are initially examined using the Static Timing Analysis procedure. If the longest statically-sensitizable path of the circuit being examined is found to have a delay equal to or very close to the longest structural delay, timing analysis is stopped at this point and the structural delay is used as the critical delay of the circuit. However, if there is a significant difference between the longest structural delay and the delay found by the Static Timing Analysis procedure, then the Dynamic Timing Analysis procedure is run to see if a tighter critical delay can be found. This thesis deals with the development of the Static Timing Analysis algorithm. This algorithm uses some Automatic Test Pattern Generation (ATPG) concepts like imply and justify and also the backtracing and forward imply techniques of Path-Oriented Decision Making (PODEM) for simplicity. The algorithm proposed here also reduces the search space by completing all the mandatory assignments of constant values to the gates that need to have these values for the path to be sensitized before proceeding on to fill in the optional assignments of the other gates.