Browse Prior Art Database

Scanline Approach to Fast Extraction and Checking of Layouts Described Hierarchically

IP.com Disclosure Number: IPCOM000109716D
Original Publication Date: 1992-Sep-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 2 page(s) / 95K

Publishing Venue

IBM

Related People

Nair, R: AUTHOR

Abstract

Disclosed is a technique which can take advantage of the time efficiency of hierarchical techniques with the space efficiency of scanline techniques for extraction and check of VLSI mask layouts.

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

Scanline Approach to Fast Extraction and Checking of Layouts Described Hierarchically

       Disclosed is a technique which can take advantage of the
time efficiency of hierarchical techniques with the space efficiency
of scanline techniques for extraction and check of VLSI mask layouts.

      Assume that it is desired to check whether shapes at a given
level are at least some unit d apart from each other in the vertical
direction.  Maintained for each cell in the hierarchy is a list of
edges sorted by increasing order of left x-coordinate.  The edges may
be of two types--either those of some basic shape, or those
corresponding to some "shadow" or bounding box of a cell that is
invoked by the current cell.  The scanline passes across the design
checking for distances in the traditional manner (1).  If a violation
is detected which involves an edge corresponding to a bounding box,
the edge list corresponding to that bounding box is expanded and
traversed to an appropriate point in its scanline to verify whether
the violation really exists.  For example, this newly opened box may
have a real edge near its top boundary which needs to be checked.  If
the top edge is the edge of yet another bounding box, AND if there is
a potential violation with this bounding box, due to the original
edge, only then will the cell at this lower level have to be
expanded.

      By performing this process for each cell in the hierarchy, the
required distance check is completed for the entire chip.  As with
hierarchical checking techniques this technique ensures that in the
absence of interactions, replicated instances of cells are not
checked more than once.  In some situations, as in certain checks for
memory cells, this could yield a reduction in computation time by two
orders of magnitude or more.

      The superiority of this technique over a non-scanline technique
arises primarily from the fact that only those cells along the
current scanline are examined.  Moreover, even among these cells,
only those that could potentially interact with other shapes or cells
are expanded.  Thus even when the layout needs to be flattened
locally to a large depth, the overhead in memory space is manageable.
Further, the fact that edges are in sorted order within the region to
be expanded makes the search f...