US 5,491,641 AGranted

Towards optical steiner tree routing in the presence of rectilinear obstacles

AssigneeLSI Logic Corporation

InventorsRanko Scepanovic, Cheng-Liang Ding

Life of this patent

Estimating the term…

Loading patent…

Abstract

An apparatus and method for locating a good approximation of optimal Steiner tree routing in the presence of rectilinear obstacles, including finding a Steiner tree on an escape graph. The escape graph is constructed by forming lines from given points (pins) and obstacles. Obstacles and the segments of obstacles are provided with lines parallel to that segment at a given minimum distance S.sub.min from the obstacle. The lines are constructed until they reach either a boundary of an obstacle or a boundary of the core. For pins which do belong to a boundary of an obstacle, a ray, perpendicular to the segment of the boundary on which the pin is located is constructed from the pin and out from the obstacle until it reaches another obstacle or a boundary of the core. For pins which do not belong to an obstacle, vertical and horizontal lines are constructed. A Steiner tree may then be found on the escape graph by using any number of algorithms such as algorithm S and algorithm M. The solution to the problem of finding a Steiner tree for the escape graph also provides a suitable approximation of a Steiner tree for the original problem. This apparatus or method may be used to optimize the routing of conductive paths on integrated circuits.

Claims4

Dependent claims

An apparatus for constructing an approximate Minimum Rectilinear Steiner Tree (MRST) which constitutes an interconnective routing path for a net of pins on edges of rectilinear components of an integrated circuit such that said routing path extends between said components, comprising:

first processing means for constructing an escape graph for said net in accordance with locations of said components, wherein said escape graph includes points which are formed by the intersection of lines from said pins and said edges of said components;
and
second processing means for constructing said approximate MRST, the second processor comprising:
third processing means for constructing Voronoi regions in said escape graph;
and for constructing a first graph including said pins, and edges connecting two of said pins respectively in said escape graph which extend between adjacent Voronoi regions;
fourth processing means for constructing a second graph as a minimum spanning tree of said first graph;
fifth processing means for constructing a third graph as a subgraph of said second graph including shortest paths in said escape graph corresponding to edges in said second graph;
sixth processing means for constructing a fourth graph as a minimum spanning tree of said third graph;
and
seventh processing means for constructing said approximate MRST from said fourth graph by deleting said points which constitute end points in said fourth graph and do not correspond to said pins.

7 more elements

Dependencies are inferred from the claim text.