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

Automatic Jog Algorithm for Layout Compactor

IP.com Disclosure Number: IPCOM000108620D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 8 page(s) / 325K

Publishing Venue

IBM

Related People

Lee, J: AUTHOR

Abstract

Modern layout compactors are gradually being accepted by the IC designer community. Jog introduction is one of the important optimization techniques for compaction. How to efficiently generate jog has automatically gotten a lot of attention, for example (1,2,3). Force-directed jog strategy was first introduced in Computer-Aided Building-Block Artwork Generator and Editor (CABBAGE) (1). Consider the situations that a wire sits between two objects. If they fall on the critical path (or the longest path), then we can imagine that opposite forces exerted by these two objects produce a torque on the wire during the compaction. If the wire bends or jogs at some point between two force points, the critical path length can be reduced. CABBAGE failed to point out good jog points when many wires lie between two objects.

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

Automatic Jog Algorithm for Layout Compactor

       Modern layout compactors are gradually being accepted by
the IC designer community.  Jog introduction is one of the important
optimization techniques for compaction.  How to efficiently generate
jog has automatically gotten a lot of attention, for example (1,2,3).
Force-directed jog strategy was first introduced in Computer-Aided
Building-Block Artwork Generator and Editor (CABBAGE) (1).  Consider
the situations that a wire sits between two objects.  If they fall on
the critical path (or the longest path), then we can imagine that
opposite forces exerted by these two objects produce a torque on the
wire during the compaction.  If the wire bends or jogs at some point
between two force points, the critical path length can be reduced.
CABBAGE failed to point out good jog points when many wires lie
between two objects.  Later works (2,3) developed a "contour
compaction" strategy for providing good jog candidates.  The idea was
borrowed from the experience of river routing.  Suppose that the
compaction is to the left.  We push objects as far left as possible,
and when we push wires to the left, they bend around "convex corners"
of the contour to form river-routing patterns.

      The contour compaction approach does not work well when the
wire lengths become an important factor.  For a good layout, we need
also to minimize the overall wire lengths in order to reduce
parasitic resistance and capacitance.  Less parasitic will yield
better circuit performance.  The capability to minimize wire lengths
(4,5) is considered one of the basic ingredients in modern
compactors.  A good automatic jog strategy for layout compactor
should take this into account.  In other words, jogs need to be
introduced not only to places where the overall cell size (span) can
shrink, but also to places where wire lengths and parasitic can be
minimized.

      First, we describe a physical model of compaction based on
which a new automatic jog strategy is developed with the dual goals
of minimizing both the cell span length and wire lengths.  In what
follows, we shall assume that the compaction direction is along the
x-axis.  (Analysis of y compaction essentially goes the same way.)
We model the compaction process as follows:
      1.   A pair of enormous push forces along the x-direction are
exerted on the cell bounding box to minimize the cell size.
      2.   Pulling forces along the x-direction are exerted at two
ends of horizontal wires to shorten wire lengths.  The sizes of these
pulling forces are determined by the parasitic
(resistance/capacitance) of the horizontal wires.
      3.   Vertical wires are not rigid.  Under the influence of
various opposing forces, net torques may be exerted on the vertical
wires.  Then these wires would bend (jog) to release the stress, if
space permits the creation of horizontal bent wire segments.  The
bending (jogging) of wires...