Delay computation in combinational logic circuits is complicated by the existence of unsensitizable (false) paths and this problem is arising with increasing frequency in circuits produced by high-level synthesis procedures. Various sensitization conditions have been proposed in the past to eliminate false paths in logic circuits, but we use a recently developed single-vector condition, that is known to be necessary and sufficient for a path to be responsible for the delay of a circuit (i.e., true) in the floating delay model. In this paper we build on this theory and develop an efficient and correct delay computation algorithm, for the floating mode delay. The algorithm uses a technique we call timed-test generation and can be incorporated into any stuck-at fault test generation framework. We describe in detail an implementation of the timed-test generation algorithm that uses both logical and timed, forward/backward implication and backtrace procedures to simultaneously prove the truth or falsity of sets of paths in the circuit. Logical and temporal conflict detection during implication and backtrace are used to speed up the algorithm. Unlike previous techniques, the algorithm remains highly efficient even when a large number of distinct gate and path delays exist in the given circuit. We provide a comprehensive set of results that show significant speedups over previous delay computation techniques.
|Number of pages
|IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
|Published - Dec 1993
All Science Journal Classification (ASJC) codes
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering