Browse Prior Art Database

New Algorithm for Stable Rectilinear Steiner Trees

IP.com Disclosure Number: IPCOM000099385D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-14
Document File: 4 page(s) / 179K

IBM

Related People

Vijayan, G: AUTHOR [+1]

Abstract

Given a set of n points on the plane, the Rectilinear Steiner Tree (RST) problem is to find the rectilinear tree in the plane, of minimum total length, which connects the given set of points. Rectilinear Steiner trees have many applications in VLSI physical design. They have been used to determine global routes for nets during the global routing phase. Timing considerations make it desirable to minimize the cost (wire length) of the Steiner trees used for global routing of nets. Rectilinear Steiner trees have also been used in other VLSI physical design applications, such as estimating the wire length of nets during the placement phase of physical design.

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

New Algorithm for Stable Rectilinear Steiner Trees

Given a set of n points on the plane, the Rectilinear
Steiner Tree (RST) problem is to find the rectilinear tree in the
plane, of minimum total length, which connects the given set of
points.  Rectilinear Steiner trees have many applications in VLSI
physical design.  They have been used to determine global routes for
nets during the global routing phase.  Timing considerations make it
desirable to minimize the cost (wire length) of the Steiner trees
used for global routing of nets.  Rectilinear Steiner trees have also
been used in other VLSI physical design applications, such as
estimating the wire length of nets during the placement phase of
physical design.

Consider a rectilinear MST T of a set of n points S. The grid
obtained by drawing horizontal and vertical lines through each point
of S is called the underlying rectilinear grid.  Consider an edge
(i,j) of the rectilinear MST T.  Any rectilinear staircase on the
underlying grid between the points i and j is a shortest layout of
the edge (i,j) of the rectilinear MST.  However, different
staircase-layouts of different edges of the rectilinear MST will
result in different amounts of overlaps among these edge layouts.  If
we merge these overlapping portions (thus  introducing Steiner
points), the resulting structure will be a rectilinear Steiner tree.

The algorithm described in this disclosure produces minimum
cost RSTs under the condition that we start with a MST and use
arbitrary staircase shapes to layout the MST edges.
We give below some useful definitions:
Definition 1:  An edge in a rectilinear MST is said to be non
degenerate if the two end points of the edge do not lie on a vertical
or horizontal line.

Definition 2:  Let T be a rectilinear MST of a set S of n
points.  A staircase-layout of a nondegenerate edge e= (i,j) is a
rectilinear shortest path (i.e., a staircase) between the points i
and j.

Definition 3:  A layout of a nondegenerate edge is said to be a
Z-shaped-layout, if the staircase path has at most two steps (i.e.,
at most, two turns).

Definition 4:  A MST T in which the layouts of the edges are
fixed is defined as a staircase-RST-draft derived from the MST T.

Definition 5.  A staircase-RST-layout derived from a
rectilinear MST T, is the Steiner tree obtained from a
staircase-RST-draft as a result of merging overlapping segments in
the draft, and generating appropriate Steiner points and edges.  The
cost of a RST-layout is defined to be the sum of the rectilinear
lengths of the edges of the resulting Steiner tree.  For convenience,
we define the cost of a RST-draft to be the cost of its resulting
RST-layout.

Definition 6:  A RST-draft (layout) of a MST T that uses only
Z-shapes for its edges is called a Z-RST-draft (layout).

Minimum cost staircase-RST-layouts have an interesting and
useful pr...