David Blaauw

Professor

David Blaauw

Professor

David Blaauw

Professor

University of Michigan
EECS Department
Electrical & Computer Engineering
1301 Beal Ave., 2417C EECS
Ann Arbor, MI 48109
Tel: 734 763 4526
Fax: 734 763-4617
Email:

Modelling Variable Flip-Flop delay in Timing Analysis

Primary Contact

Amit Jain <amjain@umich.edu>

Traditionally, the task of determining the minimum clock period of a flip-flop based sequential circuit has consisted of finding the longest combinational path between any two flip-flops of the circuit and adding setup-time, flip-flop delay and clock skew to it.  The above formulation is based on the assumption that the setup time of a flip-flop is fixed and the clock to output delay of a flip-flop is constant. This results in the major simplification that each pipeline stage can be considered independently from every other pipeline stage of the circuit. However, it is well known that the delay of a flip-flop is in fact a function of the difference between the 
clock and the data arrival time. We define TDiff as the difference between the clock and data arrival time and refer to Tff as the clock to output delay of the flip-flop. Tff increases with decreasing TDiff until the flip-flop goes metastable and Tff approaches infinity. Hence, both Tff and TDiff of a flip-flop must be considered as variables with mutual dependencies rather than being treated as constants. We show in this work that the simplification of using a fixed setup time and constant flip-flop delay may yield a pessimistic minimum clock period, and it is therefore necessary to consider these interdependencies between pipeline stages. The problem of finding the clock period of circuit considering this dependency has similarity with the problem of finding the clock period of a latch based sequential 
circuit  except for the fact that this problem is nonlinear while latter in can be solved linearly. 
We model the flip-flop Tff dependencies on data arrival times and propose a new timing analysis algorithm that accounts for these dependencies, which to our knowledge is the first effort to address this problem formally. We describe the problem of determining the minimum clock period as non-linear optimization 
problem and prove that it is convex. We propose three solution methods, a sequential quadratic programming approach, simple rectilinear manhattan decent approach, a satisfiability approach, and have compared their performance in terms of their runtime and number of iterations on ISCAS’89 sequential benchmark 
circuits. We have also discussed their ease of integration with the existing static timing analyzers. We compared the exact solution obtained from the proposed formulation with the traditional approach using different Tsetup times and observed a reduction in the clock period of approximately 50-60ps, which is 
equivalent to approximately one fan out of four delay in this technology.

Publications:

Modeling Flip-flop Dependencies in Timing Analysis

Amit M Jain, David Blaauw "Modelling Flip-flop Dependencies in Timing Analysis" TAU February 2004 ©IEEE

File: