Extraction of Routing-Trees from Polygon Routing-Patterns in an LSI Layout

In LSI layout design, two kinds of wire patterns are used to connect equipotential terminals. One is a so-called “ordinary routing-pattern” which is defined by line segments with a given width along a route, and another is a “polygon routing-pattern” whose shape is defined by coordinates of polygon's vertices. The latter is difficult to deal with layout CAD/DA tools like a layout compactor, because direction of wire's expansion and contraction cannot be recognized. So, we propose an algorithm which can efficiently transform a polygon routing-pattern into an ordinary one, by constructing a routing tree connecting terminals in each polygon pattern. Experimental results show that a transformed routing pattern obtained by the proposed algorithm is good for existent CAD tools.

LSI

Layout

Compaction

Polygon Routing

Steiner Tree

Maze Method