W.K.C. Lam, Robert K. Brayton and Alberto L. Sangiovanni-Vincentelli

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M93/6
January 1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/ERL-93-6.pdf

In this paper, we introduce a new circuit delay model, delay by sequences of vectors, which captures the essence of viability and floating delays. Then, we classify delays of circuits according to both the delay models of the gates making up the circuits and the family of inputs to the circuits. In this classification, we give sufficient conditions under which floating delay is the same as delay by sequences of vectors; these sufficient conditions are true for most practical circuits. This implies that the assumption of arbitrary node values used in the floating delay model is not too conservative. Thus, delay by sequences of vectors (hence, viability and floating delays), transition delay, and cycle time delay have coherent definitions under the same framework. Next, we study the problem of computing the exact circuit delays under both bounded and unbounded gate delay models, for some of which only upper bounds are known. By using a new formulation technique, called Timed Boolean Function, we formulate the problem of computing the exact delays as a mixed Boolean linear programming problem for which we give efficient algorithms to compute the exact delays of combinational circuit for transition delay and delay by sequences of vectors. The algorithms consider a subset of paths at one time and only the paths potentially responsible for the delay of a circuit are considered. Moreover, the core computation of the algorithms are composed of two computationally efficient algorithms: linear programming and BDD manipulations. We next compute floating (or viability) delays with the bounded gate delay model and show that delays by sequences of vectors and floating (or viability) delays are invariant under both bounded and unbounded gate delay models. Finally, we address the effect of gate delay lower bounds on delays of circuits. We demonstrate the effectiveness of the method by giving exact delay results for all ISCAS benchmark circuits (except C6188).

BibTeX citation:

@techreport{Lam:M93/6,
    Author = {Lam, W.K.C. and Brayton, Robert K. and Sangiovanni-Vincentelli, Alberto L.},
    Title = {Circuit Delay Models and Their Exact Computation Using Timed Boolean Functions},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Jan},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2269.html},
    Number = {UCB/ERL M93/6},
    Abstract = {In this paper, we introduce a new circuit delay model, delay by sequences of vectors, which captures the essence of viability and floating delays. Then, we classify delays of circuits according to both the delay models of the gates making up the circuits and the family of inputs to the circuits. In this classification, we give sufficient conditions under which floating delay is the same as delay by sequences of vectors; these sufficient conditions are true for most practical circuits. This implies that the assumption of arbitrary node values used in the floating delay model is not too conservative. Thus, delay by sequences of vectors (hence, viability and floating delays), transition delay, and cycle time delay have coherent definitions under the same framework. Next, we study the problem of computing the exact circuit delays under both bounded and unbounded gate delay models, for some of which only upper bounds are known. By using a new formulation technique, called Timed Boolean Function, we formulate the problem of computing the exact delays as a mixed Boolean linear programming problem for which we give efficient algorithms to compute the exact delays of combinational circuit for transition delay and delay by sequences of vectors. The algorithms consider a subset of paths at one time and only the paths potentially responsible for the delay of a circuit are considered. Moreover, the core computation of the algorithms are composed of two computationally efficient algorithms: linear programming and BDD manipulations. We next compute floating (or viability) delays with the bounded gate delay model and show that delays by sequences of vectors and floating (or viability) delays are invariant under both bounded and unbounded gate delay models. Finally, we address the effect of gate delay lower bounds on delays of circuits. We demonstrate the effectiveness of the method by giving exact delay results for all ISCAS benchmark circuits (except C6188).}
}

EndNote citation:

%0 Report
%A Lam, W.K.C.
%A Brayton, Robert K.
%A Sangiovanni-Vincentelli, Alberto L.
%T Circuit Delay Models and Their Exact Computation Using Timed Boolean Functions
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/ERL M93/6
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2269.html
%F Lam:M93/6