Browse Prior Art Database

Approximation of the Steiner Tree Length

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

Publishing Venue

IBM

Related People

Dueck, G: AUTHOR [+2]

Abstract

This article describes a method of approximating the Steiner tree length.

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

Approximation of the Steiner Tree Length

       This article describes a method of approximating the
Steiner tree length.

      All placement algorithms for VLSI chips are based on
determining the length of the electrical connections between modules.
The connection of a group of modules by electrical lines of minimum
length is described by an (orthogonal) Steiner tree.  The accurate
computation of the Steiner tree length is highly difficult and
involves a tough complex theoretical problem.

      Iterative methods, which are used to determine the optimum
module placement on VLSI chips, necessitate an efficient
approximation of the Steiner tree length.  The efficiency criteria
are
      1.   fast computation and/or simple update and
      2.   accurate approximation.

      The present method estimates the Steiner tree length on the
basis of half the circumference of the rectangle enclosing the module
plus the length of the rectangle's narrow side, multiplying both
summands by coefficients determined in a series of tests.

      This estimate approximates the Steiner tree length with an
accuracy of several percent but is many times faster than
conventional approximations.  Computation times of several hours for
the placement algorithms are reduced accordingly. The use of this
Steiner tree approximation shortens the electrical lines required for
wiring the modules on an average by 10 percent.