Browse Prior Art Database

Linear Algorithm for Distributing Slack So That All Nets of A Design Have a Zero Slack Pin

IP.com Disclosure Number: IPCOM000121121D
Original Publication Date: 1991-Jul-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 5 page(s) / 246K

Publishing Venue

IBM

Related People

Relis, Y: AUTHOR

Abstract

With a methodology which takes timing into consideration at every phase of the design cycle, costly redesign efforts are inevitable. However, in the rush to develop such a methodology, a view towards the future must be maintained. That means that the algorithms employed must be fast enough that they will not in themselves become bottlenecks as designs grow. Ideally, the algorithms should be linear in time and space. This article describes a particular application of a new linear algorithm which can be used to insure that path constraints in a network are met while optimizing other factors.

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

Linear Algorithm for Distributing Slack So That All Nets of A Design
Have a Zero Slack Pin

      With a methodology which takes timing into consideration
at every phase of the design cycle, costly redesign efforts are
inevitable.  However, in the rush to develop such a methodology, a
view towards the future must be maintained. That means that the
algorithms employed must be fast enough that they will not in
themselves become bottlenecks as designs grow.  Ideally, the
algorithms should be linear in time and space.  This article
describes a particular application of a new linear algorithm which
can be used to insure that path constraints in a network are met
while optimizing other factors.

      In this application the path constraints are the timing
requirements.  The factors to be optimized are net capacitance
targets that are passed to placement.  The intention is to pass
targets which will minimize the constraints on placement while
insuring that timing is met. This is achieved by generating targets
which will produce a zero slack condition on each net while insuring
that net capacitances are not overly constrained.  The idea of
generating such targets was first proposed in [1].  The algorithm
employed there was demonstrated to take O(N x P) time (N = number of
nets, P = number of pins).  Using the new algorithm, it is possible
to generate the zero slack condition at every PO/REG input of O(P)
time.  In addition, zero slacks at every net in the design can be
generated in O(P x L) time where L is the number of levels of logic.
Since, due to design constraints, L is a small number independent of
the size of the design, even at worst case this is a linear
algorithm. A simplified version of this algorithm can generate the
zero slack condition in O(P).  This simplified version will be
described first.
O(3 x P) Zero Slack Algorithm

      Unlike the algorithm in [1], which processes a minimum slack
path at a time, then updates all logic in the fan-in and fan-out
cones of the path to reflect the modifications of the delays on the
path, the O(P) algorithm makes a right to left pass through the
logic, a left to right pass and a final right to left pass.  First, a
right to left pass through the logic is made, starting from POs and
REG inputs and ending with PIs and REG outputs.  This is done a level
of logic at a time.  During this pass, a weight Wi is associated with
each net Ni .  This weight is meant to reflect the various factors
which come into play when determining how much excess delay to assign
to the net. A weight which has been demonstrated to accurately
reflect these considerations is SENSITIVITY/SLACK [2] where
sensitivity is a measure of how rapidly the net source delay changes
when capacitance changes.  (e.g.,
(Delay(nom_wire_cap)-Delay(zero_wire_cap))/nom_wire_cap.)
Furthermore, the total weight Ti along the minslack path from a
PO/REG to Ni is calculated recursively as this right to left pass is
made.  Th...