4. AVOIDING DUPLICATE COMPUTATIONS: HIERARCHY MANAGEMENT
Most integrated circuit layouts today are organized hierarchically. An
arrangement of figures in a structure is enclosed within a cell definition which
may be oriented, scaled and placed many times in the layout by means of cell
placement and arraying references. A cell definition may itself contain cell
references. A layout hierarchy is a non-recursive tree structure in which a top
cell is the base of the tree. The top cell may contain figures and references to
other cells which in turn may contain figures and references to other cells.
Ultimately, the hierarchy ends with references to cells which contain only
figures. Cells may not reference themselves either directly or
indirectly.
Hierarchy may be structural or functional. With structural hierarchy, the
contents of a unit are encompassed by a cell definition for convenience and
there is only one reference to the cell. With functional hierarchy, a cell is
referenced more than onceÑperhaps hundreds, thousands or millions of times.
Functional hierarchy reduces the data volume required to specify the layout,
whereas structural hierarchy does not. In conventional CAD tools, many layout
data operations such as overlap removal or global biasing remove (i.e., flatten)
the functional hierarchy in the layout. If functional hierarchy could be
maintained during a layout data modification process, the size of the output
data would be reduced. Moreover, the time to perform the layout data
modification would be reduced, since it is determined by the amount of data in
the cell definitions, not by the number of cell references.
Hierarchy may be structural or functional. With structural hierarchy, the
contents of a unit are encompassed by a cell definition for convenience and
there is only one reference to the cell. With functional hierarchy, a cell is
referenced more than onceÑperhaps hundreds, thousands or millions of times.
Functional hierarchy reduces the data volume required to specify the layout,
whereas structural hierarchy does not. In conventional CAD tools, many layout
data operations such as overlap removal or global biasing remove (i.e., flatten)
the functional hierarchy in the layout. If functional hierarchy could be
maintained during a layout data modification process, the size of the output
data would be reduced. Moreover, the time to perform the layout data
modification would be reduced, since it is determined by the amount of data in
the cell definitions, not by the number of cell references.
Figure 4. LEFT: Example of an isolated array of cell A; Cell A
has 9 distinct environments. RIGHT: Example of 3 instances of a non arrayed cell
C with 2 distinct environments.
A good example is an array of RAM cells (Figure 4 Left). The cells near the
interior of the array all have the same environment, but those near the edges
and corners have quite distinct environments. Thus a single modification to the
cell definition may be incorrect for some or most of the environments in which
the cell is placed. There may be dozens or even hundreds of distinct
environments for the RAM cell, each of which requires a different modification
of the cell definition.
Even random logic designs have useful functional hierarchy (Figure 4 Right).
Modern designers use logic components from libraries, and a given component is
used many times. For random logic, the repeating units are not on regular arrays
as for RAM cell arrays, but the hierarchy manager can nonetheless take advantage
of the functional hierarchy. The hierarchy manager places no constraints on how
cells and the data within them may overlap. A cell may even overlap itself or a
version of itself which is rotated or mirrored. Such conditions actually occur
in real designs and the hierarchy manager handles them.
The problems arising from different environments for placements of a given cell
definition are not restricted to modifications required for correcting proximity
effects. The issues apply for very basic geometric operations such as overlap
removal and global feature biasing. Conventional design rule checking tools have
avoided the cell environment problem by flattening the data hierarchy. OPRX, on
the other hand, incorporates a sophisticated hierarchy manager which
automatically accounts for the distinct environments in which a cell may be
placed. The hierarchy manager reduces by orders of magnitude the amount of
computation which must be performed for most designs.
Another powerful aspect of the hierarchy manager is that it can identify
incidental hierarchy--that is hierarchy which is not explicit in the original
layout. For example, cell A and cell B may be identical on the Poly layer, but
different on a metal layer. Thus they appear in the design as distinct cells.
When performing a correction on the Poly layer, cells A and B appear identical
and are treated as the same cell.
ABSTRACT
1. INTRODUCTION
2. OPTICAL ENHANCEMENT: NOT JUST OPTICAL PROXIMITY CORRECTION
3. COMPUTATIONAL SPEED: THE RULES BASED APPROACH
4. AVOIDING DUPLICATE COMPUTATIONS: HIERARCHY MANAGEMENT
5. MORE COMPUTING POWER: MULTIPROCESSING
6. POWER AND FLEXIBILITY: INTER-LAYER MANIPULATIONS
7. CONCLUSIONS AND SUMMARY
8. REFERENCES
Return to the OPRX main page
Return to the Trans Vector Technologies home page