Computation of Floating Mode Delay in Combinational Circuits: Practice and Implementation

Srinivas Devadas, Kurt Keutzer, Sharad Malik, Albert Wang

Research output: Contribution to journalArticle

29 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1924-1936
Number of pages13
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume12
Issue number12
DOIs
StatePublished - Dec 1993

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Computation of Floating Mode Delay in Combinational Circuits: Practice and Implementation'. Together they form a unique fingerprint.

  • Cite this