COMPUTATION OF FLOATING MODE DELAY IN COMBINATIONAL-CIRCUITS - PRACTICE AND IMPLEMENTATION

Delay computation in combinational logic circuits is complicated by th e existence of unsensitizable (false) paths and this problem is arisin g with increasing frequency in circuits produced by high-level synthes is procedures. Various sensitization conditions have been proposed in the past to eliminate false paths in logic circuits, but we use a rece ntly 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 t his theory and develop an efficient and correct delay computation algo rithm, for the floating mode delay. The algorithm uses a technique we call timed-test generation and can be incorporated into any stuck-at f ault test generation framework. We describe in detail an implementatio n of the timed-test generation algorithm that uses both logical and ti med, forward/backward implication and backtrace procedures to simultan eously prove the truth or falsity of sets of paths in the circuit. Log ical and temporal conflict detection during implication and backtrace are used to speed up the algorithm. Unlike previous techniques, the al gorithm remains highly efficient even when a large number of distinct gate and path delays exist in the given circuit. We provide a comprehe nsive set of results that show significant speedups over previous dela y computation techniques.