Browse Prior Art Database

Scan Line Algorithm for Layout Compactor of Integrated Circuits

IP.com Disclosure Number: IPCOM000034218D
Original Publication Date: 1989-Jan-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 4 page(s) / 56K

Publishing Venue

IBM

Related People

Lee, JF: AUTHOR

Abstract

A technique is described whereby a scan line algorithm provides symbolic layout compactness of integrated circuits to allow dense packing so as to expedite design rule analysis. The algorithm implements a two-step scan line approach for a layout compactor. (Image Omitted) Typically, there are two types of scan line algorithms used for compactors, symbolic oriented and shape oriented. In the symbolic- oriented approach, the layout is organized into groups of symbols which share the same center line where the scan line jumps from one group of objects to another group of objects. In the shape-oriented approach, the layout is viewed as a set of rectilinear masks where the scan line is moved from one mask edge to another mask edge.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 4

Scan Line Algorithm for Layout Compactor of Integrated Circuits

A technique is described whereby a scan line algorithm provides symbolic layout compactness of integrated circuits to allow dense packing so as to expedite design rule analysis. The algorithm implements a two-step scan line approach for a layout compactor.

(Image Omitted)

Typically, there are two types of scan line algorithms used for compactors, symbolic oriented and shape oriented. In the symbolic- oriented approach, the layout is organized into groups of symbols which share the same center line where the scan line jumps from one group of objects to another group of objects. In the shape-oriented approach, the layout is viewed as a set of rectilinear masks where the scan line is moved from one mask edge to another mask edge. Generally, the symbolic-oriented approach is used in the development process since it allows a more natural representation of the layout in terms of circuit components, such as transistors, contacts, etc. This approach offers other advantages, such as the grouping will (a) keep the circuit as close as possible to the original design and (b) enable compaction to be faster because the number of groups is much less than the number of mask shapes. However, one big problem of the symbolic layout approach is that objects cannot be as densely packed as the shape-oriented approach. The concept described herein implements a new scan line algorithm which allows both the grouping of the objects and also provides for dense packing of the objects. An example of a layout in terms of mask shapes is shown in Fig. 1. The same layout in symbolic style is shown in Fig. 2. The source of one transistor, T1, is connected to the drain of another transistor, T2, through two contacts, C1 and C2, and through wires W7, W1, W6, W3, W4, and W5. The symbols are: - denoting diffusion, . denoting polysilicon, ' denoting metal wire, and * denoting contact cut. In comparing the two figures, the symbolic representation is much simpler and more elegant. The new scan line algorithm for the layout compactor is as follows: Assume that compaction is along the x- direction.

(Image Omitted)

$ Sort symbolic objects according to their center

coordinates, XC and YC. Scan the list of symbolic

objects to produce groups of objects with the same XC and

those which are also electrically connected.

$ Decompose symbolic objects into rectilinear masks and

sort the vertical mask edges (x,y1)-(x,y2) in the order

of x/y1/y2. Scan the list of vertical edges to search

pairs of edges whi...