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

Buffer Placement in Distributed Rc Tree Networks for Minimal Elmore Delay

IP.com Disclosure Number: IPCOM000119340D
Original Publication Date: 1991-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 149K

Publishing Venue

IBM

Related People

van Ginneken, LPP: AUTHOR

Abstract

Disclosed is an algorithm that places buffers in a given wiring tree. The required arrival times of the signal at the leafs of the wiring tree are given. The algorithm places the buffers such that the required signal departure time is as late as possible. The algorithm takes the delays due to capacitative and resistive parasitics into account. For a more extensive description of the algorithm see (1).

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

Buffer Placement in Distributed Rc Tree Networks for Minimal Elmore
Delay

      Disclosed is an algorithm that places buffers in a given
wiring tree.  The required arrival times of the signal at the leafs
of the wiring tree are given.  The algorithm places the buffers such
that the required signal departure time is as late as possible.  The
algorithm takes the delays due to capacitative and resistive
parasitics into account. For a more extensive description of the
algorithm see (1).

      The wiring trees are modeled by a tree of distributed RC
sections (see figure).  The capacitance to the surrounding wires is
modeled as an extra contribution to the capacitance to ground.  The
root of the tree is the source of the signal, and the leafs of the
tree are the sinks of the signal.

      The Elmore delay (2), also known as the inertia, is defined as
the first order moment of the impulse response hi(t) at leaf i.  One
can interpret this as the "average arrival time" of the electrons at
the sink capacitor.  For an RC tree network with discrete resistors
and capacitors, the Elmore delay from the root to sink i is a sum
over all nodes k in the tree (3), so:

      Ck is the capacitance between node K and ground.  Rki is the
resistance of common sections of the path from K to the root and the
path from i to the root.  (For instance in the figure R4,5 = R1 +
R2 .)  The interpretation of this formula is that the delay through a
single resistor is the product of its resistance times all the
capacitance that is charged through it.  One can see it as a
generalization of the RC-delay.

      The task of the new algorithm is to put buffers into existing
wiring tree.  On the wiring tree there are legal positions where the
algorithm may place a buffer.  Each buffer is characterized by an
input capacitance Cbuf, an internal delay Dbuf, and an output
impedance Rbuf .  The required arrival times T1 for the signal at the
sinks and the capacitance C1 of the sinks are given.  The algorithm
places buffers such that the resulting required departure time T5 of
the signal at the source is as late as possible. Using the
Elmore-delay, the required departure time can be expressed as:

                            (Image Omitted)

      Using the Elmore delay model, T5 can easily be computed
recursively.  Let Sk be the sub-tree rooted at node k.  Each sub-tree
Sk can be modeled by two numbers, the total capacitative load in the
sub-tree Lk, and the required time at the root of the sub-tree Tk, if
the sub-tree would be driven by a buffer of zero impedance.

      When a piece of wire length P is added, the new values can be
computed by

      When a sub-tree is buffered the new values can be computed by

      When two sub-trees Sm and Sn are joined, the new values for the
whole sub-tree Sk are

      The buffer placement algorithm computes all the different (T,L)
pairs for possible assignmen...