Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Allocating Maximum RC Delays to Guarantee Timing by Depth First Search

IP.com Disclosure Number: IPCOM000106007D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 4 page(s) / 185K

Publishing Venue

IBM

Related People

Jepsen, DW: AUTHOR [+2]

Abstract

Disclosed is a method for generating lengths for the segments of a net such that the delay from the source to arbitrary sinks meet timing requirements, and which chooses the smallest allowed segment lengths when this is not feasible. This extents the method described in [1] and [2], which gave a model and a method to control the length of directly connected source-to-sink pairs. Here, disclosed is a procedure for generating the equations of that method when the net has the form of a tree, with or without Steiner points, with the source at the root.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 28% of the total text.

Allocating Maximum RC Delays to Guarantee Timing by Depth First Search

      Disclosed is a method for generating lengths for the segments
of a net such that the delay from the  source to arbitrary sinks meet
timing requirements, and which chooses the smallest allowed segment
lengths when this is not feasible.  This extents the method described
in [1]  and [2], which gave a model and a method to control the
length of directly connected source-to-sink pairs.  Here, disclosed
is a procedure for generating the equations of that method when the
net has the form of a tree, with or without Steiner points, with the
source at the root.

      The source-sink delay requirements are obtained by allocating
slack to the source-sink connections after performing timing analysis
on a logic network [3].  Each sink pin on the net will be a vertex
with a constraint on the delay from the source, while Steiner points
on the net will not.  Obtain an approximate solution of this problem
assuming that the changes in the capacitance and RC values from the
original values given are small, so that a linear method can be used.
The nonlinear problem is solved by iterating this linear method.
Thus, the matrix and right hand side vector of a linear programming
problem for which the changes in lengths of the segments in the tree
are the variables must be built.  Maximize some weighted sum of the
increases of these lengths to get the best solution (also minimizing
decreases).

      For a net with N sinks s(1), ..., s(N), we have T(1), ,,, T(N)
as the respective slack allocated at the sinks.  The source S and the
N sinks are connected by M segments labelled 1, ..., M in the form of
a tree, M <=  N.  Use &sigma.  and &rho.  for the average capacitance
per unit length and average resistance per unit length respectively.
Let L(1), ..., L(M) be the respective length of the segments labelled
1, ..., M and R(1), ..., R(M) be the respective resistance, C(1),
..., C(M) be the respective capacitance.  Let Cg(1), ..., Cg(N) be
the gate capacitance of the sinks.  The wire delay from the source S
to sink s(i), i = 1, ..., N  can be expressed in terms of R(1), ...,
R(M), C(1), ..., C(M), and subsequently in terms of L(1), ..., L(M).
The M segments are allowed to change in length denoted respectively
by &Delta.L(1), ..., &Delta.L(M), when the change is small, the
change in wire delay can be expressed as a linear combination of
&Delta.L(1), ..., &Delta.L(M) at the given length (L(1), ..., L(M))

      The change in delay reflected at the sinks due to the change in
length in the segments is bounded by the slack allocated to the
sinks, expressed as the following N linear constraints.

     &Delta.delay(i)(&Delta.L(1), ..., &Delta.L(M)) = &Sigma.(j=1,
..., M) M(i,j) &Delta.L(j) <=  T(i), i = 1, ..., N

     where each M(i,j) is constant when &Delta.L(j) is small.

      Constrain these changes in length so that the resulting lengths
are greater than...