[Indigo]<DA>MITPaper.dm!1>MITPaper.bravo

The artwork of integrated circuit designs is usually available in the form of a hierarchical specification, in which each cell is made up of geometric primitives and references to other cells. Such a representation captures structure and repetition in the layout. As the realizable device count of integrated circuits increases with every passing year there is an increasing trend towards structured design approaches that result in even greater degrees of regularity and hierarchy. Yet the typical approach to design verification requires fully instantiating the hierarchical representation thereby removing all structure from it. Consequently much time is spent repeating the analyses of identical cells. This paper presents a general approach to exploiting hierarchy and repetition in the analysis of integrated circuit designs, and includes details of a circuit extraction algorithm that uses this approach. The implementation and performance of such a system is also described.

Techniques for verifying the artwork of integrated circuits are now well established both in the literature and in the form of software packages available from a number of vendors.1,2 The basic theme behind such tools involves carrying out geometric analyses of the mask specification with a view to establishing wellformedness and conformity with given specifications. Wellformedness checks include Design Rule Checking, which checks for conformity to a set of rules concerned with the geometry of the layout, and Electrical Rules Checking, which involves a Circuit Extraction phase to derive a circuit representation and then checking it for conformity to a set of rules concerned with wellformedness of the circuit. The extracted circuit can also be used for comparison with a given circuit specification that the layout is intended to implement, or can be used to carry out a dynamic simulation of the circuit taking into account parasitic effects that are a function of the layout.

The artwork of integrated circuit designs is usually available in the form of a hierarchical specification, in which each cell is made up of primitives (typically rectangles and polygons) and references to other cells. The typical approach to design rule checking and circuit extraction involves fully instantiating the hierarchical representation to remove all structure from it. The analyses then traverse this flat representation, either by a moving line approach or by region growing techniques, and carry out their function on local areas.

There are several objections to analyses that involve fully instantiating a layout description. The most obvious of these is a question of efficiency of space and time. Currently integrated circuit designs containing 10,000 to 100,000 transistors are common. Layout analysis programs, such as design rule checking and circuit extraction, for designs of this size can take several hours of CPU time. Many have predicted that in a few years we will be able to fabricate VLSI circuits with over a million transistors.3,4 Even if we assume that flat analysis algorithms grow linearly in time with respect to the number of devices in a design, we can expect these programs to take several days for VLSI circuits. Yet integrated circuit designs often exhibit considerable degrees of regularity and hierarchy. It is unreasonable, then, to carry out an analysis of one instance of a cell, only to repeat that analysis for every other instance of the same cell. As the realizable device count on integrated circuit chips increases there is a trend towards structured design approaches that result in higher degrees of regularity and hierarchy. This, in turn, increases the absurdity of carrying out analyses on fully instantiated versions of layout artwork.

Another objection to analysis techniques that operate on fully instantiated representations will be familiar to anyone who has waded through pages of error messages obtained from a conventional design rule checker. Frequently a genuine error is missed because it is lost in a mass of messages that are due to a few errors in often repeated cells. How much more effective it would be to analyze each cell once and to report any error only once.

The role of repetition in any attempt to reduce computation is in the opportunity to avoid repeating the analysis of any cell that is instanced more than once. The role of hierarchy is in the fact that it provides groups of instances that can be recognized as repeating as a group. Hierarchy reduces the number of objects considered to be repeated, without sacrificing the ability to fully exploit repetition. For example consider a cell, A, containing a row of 16 instances of another cell, B. Contrast this with a cell, A’, containing a binary hierarchy with 4 levels, culminating in 16 leaf instances of the cell P positioned exactly the same as their counterparts in A. Both A and A’ represent the same layout. However, the number of instances that must be dealt with in A’ is only 8, being 2 at each of the 4 levels, compared with the 16 in A. Moreover, only 4 interfaces between instances need be considered in A’ compared with 15 in A.

Whitney5 has developed an algorithm for exploiting the hierarchy in the area of design rule checking. The algorithm operates as a filter on the given layout, and produces another layout that contains only a subset of the instances present in the original layout. This filtered version is claimed to contain at least one occurrence of any design rule violation present in the original layout. The filtered layout is then analyzed by a conventional DRC program, typically with a considerable decrease in time and in the number of duplicate error reports.

Whitney’s algorithm walks the hierarchy, and for each instance ensures that a copy of the symbol has been output to the filtered version. It then checks all interactions between this instance and its neighbors. For each neighbor sufficiently close to potentially provoke a design rule violation, if the pair of cells involved has not previously been seen in the current juxtaposition then components of each member of the pair that are near the other member are output to the filtered version.

Whitney’s algorithm is not directly applicable to other analyses such as circuit extraction. Hon6 has extensively generalized Whitney’s algorithm to enable such other analyses. The algorithm is configured as a common front end process that analyses and tracks repeated juxtapositions in the given hierarchy, and then makes calls on any one of a variety of modules that implement the various analyses required. Each analysis module has to implement the operations of analyzing a single cell, and composing the analyses of two non-overlapping cells.

The basic problem with exploiting hierarchy is concerned with overlapping instances. Overlaps can make the analysis of the interior of one instance of a cell quite irrelevant to the analysis of the interior of another instance of the same cell. In the case of design rule checking an overlapping feature can introduce new errors or even remove apparent errors that exist in the absence of the overlap. In circuit extraction an overlapping feature can radically change the implied circuit. It is easy to show cases where overlapping geometry can create transistors that were not in the original symbol, or remove transistors that previously were there. A conductive path might get broken by an overlap, or it might get shorted to another path. If we could ensure that cells do not overlap, it would greatly simplify the task of design rule checking and circuit extraction.

Scheffer7 has addressed this observation by prohibiting overlap between the subcells of any given cell, or between subcells and geometry, in the design specification itself. By allowing more general outlines than simple bounding boxes, no loss of component density is necessarily incurred.

However, it would be more convenient if methods for avoiding or removing overlap could be found, thereby allowing existing design synthesis aids and methodologies to continue to be used. This is the basis for the approach used here. A method has been developed for transforming a given hierarchical representation that allows overlapping instances into another hierarchical representation with no overlaping instances, yet still preserves hierarchy and repetition.

The Disjoint Hierarchy is a hierarchical representation of a layout that is free from any overlapping instances of cells, or overlap of instances with geometry. It is derived from the given hierarchical description by the Disjoint Transformation, which ensures that the disjoint hierarchy reflects the hierarchical structure of the given description, and that it preserves repetition of instances where possible.

Details of the Disjoint transformation algorithm are given later. Basically it is a recursive tree walk procedure that partitions each symbol into regions where instances overlap. Repetition amongst these regions is then recognized and new symbols corresponding to repeated regions are created.

One side effect of the Disjoint transformation is that active devices and atomic features such as contact cuts can be divided in ways that make it impossible to correctly interpret these features given only one created symbol. Subsequent analyses must be able to handle these anomalies. The authors take the attitude that any system that processes unrestricted designs will have to address this problem anyway.

Having obtained the Disjoint Hierarchy the task of the analysis procedures is greatly simplified. Three analyses will be outlined: Drawing on a raster display, design rule checking, and circuit extraction. Details of the circuit extraction algorithm are given later in the paper.

While drawing on the screen of a raster display may not qualify as an analysis, it does indicate a particularly simple example of exploiting the Disjoint Hierarchy. Drawing on the screen involves instantiating the whole layout and scan converting it to a raster format. The process can be accelerated if the scan converted version of one instance of a cell can be reused as a "rubber stamp" to draw the other instances. This approach can consume large amounts of buffer space. However, in drawing the Disjoint Hierarchy, the scan converted version of a cell already in the display memory can be used as the master copy to be duplicated for other instances of the same cell, throughout the hierarchy. It involves remembering with each cell definition whether it has been scan converted yet, and if so where its image can be found in the display memory. This method works well for color displays, but raises the question of matching the phase of stipple patterns used on monochrome displays. In practice the problem can be solved by outlining each instance.

Design rule checking is a more meaningful analysis and can proceed in a number of ways. In one approach each cell is checked individually and any errors sufficiently distant from the boundary of the cell to eliminate the possibility of a design rule interaction with a neighbor, are considered genuine errors. The region near the boundary is used to generate a specification of conditions that must be met in neighbors. Checking a cell that contains subcells then involves checking for conformance with these conditions where the subcells come sufficiently close to enable the possibility of design rule interactions.

Circuit extraction can be achieved as follows. Each extracted cell is represented as a circuit representing the interior of the cell, and a set of connections to the boundary of the cell where conductors inside the cell touch the boundary. Since transistors can be divided by the boundary of a symbol it is necessary to be able to also represent partial transistors. The extraction of a cell involves first of all extracting all the cells which are called at least once in this cell. The circuit for the current cell is derived from the geometry of the cell as well as from the circuits of called cells that are already extracted. Since cells can communicate only through their boundaries it is always clear exactly where a neighboring cell or piece of geometry will connect, and the internal circuit of a cell cannot be affected. The result of this algorithm is a hierarchical description of the circuit. If a fully instantiated circuit description is needed then a final phase that generates this is needed.

Fig. 1 shows a symbol, A, made up of one instance each of symbols B, C, D, E, and F. Consider a layout consisting of four instances of A juxtaposed in the form of a regular array as in Fig. 2a. The function of the Disjoint transformation is to remove overlapping cell instances. This is done by generating new cells from combinations of given instances where they overlap. The partitioning uses the edges of the boundaries of the given instances, so that every edge of a derived cell is coincident with an edge of a given instance. The result of partitioning the case in Fig. 2a is shown exploded in Fig. 2b. Four new cells have been generated, P, Q, R, and S, of which P and S are instanced once each, Q is instanced three times, and R is instanced twice.

It is now necessary to consider the contents of each of P,Q,R,S to fill out the next level of the derived disjoint hierarchy. The contents of the derived cells are shown in Fig. 3. The cells B’, B’’, F’, F’’ are parts of the cells B and C out of which the original A was made. The partitioning algorithm is now applied to each of P,Q,R,S in turn. This process continues to recurse until cells containing only geometry are met.

Of course, this example is atypical, not just in the small number of cells involved, but in the fact that only one type of cell is involved at the top level and that overlaps involve only two instances. A realistic algorithm has to generalize on both of these issues.

An outline of the basic algorithm is given in the Approach section under The Disjoint Hierarchy. The algorithm is implemented as two procedures, Split, and Gather, that call each other recursively. In the example above, the Split procedure generates the structure shown in Fig. 2b, except that the repetition of R and Q is not yet recognized. The Gather procedure recognizes repetition and creates the cells P, Q, R, and S.

The Split procedure takes as input a symbol. A symbol here is a generalization of the normally accepted use of the term. In common with conventional usage, a symbol is made up of geometry and instances of other symbols. However, also associated with the symbol is a window. The window is a manhattan polygonal clipping region outside of which any component instances or parts of instances are to be ignored. This extended definition is convenient for the intermedate structures generated during the Split procedure. Each input cell is initially converted to a symbol by defining its window to be its minimum bounding box.

The function of the Split procedure is to partition those parts of the symbol’s geometry and instances that lie inside the window into a minimum number of disjoint manhattan-polygonal regions, called Discells. Discells are defined by regions uniformly covered by an integral number of instances. Geometry of the given cell is partitioned to the boundaries of the Discells. Therefore, each Discell is associated with parts of instances that overlap and with fragments of geometry of the given cell that overlap the Discell. The union of all the Discells must be identical with the given symbol definition.

The Split procedure uses a conventional moving line algorithm in which the set of instance windows is cut into horizontal swaths whose upper and lower limits coincide with vertices of the instance windows. Each swath is scanned left to right keeping track of the set of instances between each consecutive pair of vertical window edges. Each set corresponds to a Discell to be used in subsequent processing by the Gather procedure. Discells are kept in a hash coded dictionary to make it possible to determine quickly whether a given Discell has been seen before. The hash is a function of the addresses of the component instances in memory. If a Discell has been previously seen the entry in the dictionary is updated to extend the window of that Discell. In the present implementation rotations and mirrors of symbols are considered unique and will generate different new symbols. The geometry of the given symbol is partitioned to the individual Discells generated by the above procedure.

For example, consider a swath, S1, from the simple example shown again in Fig. 4. The individual instances of symbol A have been named A1, A2, A3, A4. While scanning swath S1 the following potential Discells will be found: {A1}, {A1,A2}, {A2}, {A2,A3}, {A3}, where {} denotes the set of instances making up a Discell. Of these, the Discells {A1}, {A1,A2}, {A2} will already be in the Discell dictionary, and so their entries will have their windows extended by the appropriate regions of the swath S1. Discells {A2,A3}, {A3} will make new entries in the dictionary.

The function of the Gather procedure is to recognize sets of Discells that consist of similar juxtapositions of instances and windows, and to convert them to regular symbols. In forming a new symbol from a Discell, Gather replaces the set of component instances with their contents, as shown in Fig. 3 of the simple example. Gather next creates instances of each new symbol to replace the Discells converted to that new symbol. The total set of instances so created replaces the contents of the symbol originally passed to Split and from which the Discells were created.

In Fig. 4, Gather will recognize that Discells {A1,A2}, {A2,A3} and {A3,A4} all consist of similar juxtapositions of instances of symbol A. The new symbol, Q in Fig. 2a, will therefore be created, and will consist of the instances making up the component instances of the replaced Discells that overlap the Discell’s window, as in Fig. 3. Each Discell is replaced by an instance of the symbol Q, shown in Fig. 2b. Similarly Discells {A2} and {A3} are replaced by instances of symbol R. The set of instances of P, Q, R, and S now replace the original contents of the symbol that consisted of four instances of symbol A.

Finally, Gather calls Split for each newly created symbol. The mutual recursion between Split and Gather terminates when a created symbol is found to contain no instances of other symbols. A subsequent process is used to filter out symbols that contain nothing, and to short cut symbols that contain only a single instance by making the call in the next level up the hierarchy.

Fig. 5 shows a four-bit shift register. This shift register contains eight instances of the basic shift register cell. The cell boundaries are outlined. Extraction proceeds by first examining the basic shift register cell, shown in Fig. 6. The heavy black marks indicate external interface segments. External interface segments are regions where the geometry of a cell touches the cell boundary. Interaction among cells and between cells and geometry can be determined by finding where these interface segments touch. Extraction of this cell is straightforward since it contains no other sub-cells. Extraction provides a description of the three transistors in the circuit and how they are connected both among themselves and to the external interface segments. This description is attached to the basic shift register cell. A pictorial representation of this description is shown in Fig. 7. Again, the heavy black lines represent the interface segments.

We now consider the four-bit shift register as the cell to be extracted. In Fig. 8 we show the original four-bit shift register with the geometry of the basic cell replaced by its interface segments. We call these internal interface segments of the four-bit shift register cell since these interface segments connect to sub-cells rather than super-cells. Note that the internal interface segments on the left and right ends of the four-bit shift register are also external interface segments since they touch the boundary of the shift register. Extraction of this cell is a bit more complicated than of the basic cell. Connectivity of geometry and interface segments must be included in the extracted description. Yet the same basic techniques for extracting a geometry-only cell can be used to extract a cell with interface segments. At the end of extraction we have a description of how the interface segments of the the eight basic cells are connected to each other, the two poly lines, and the external interface segments of the shift register.

The basic function of the extractor is to convert a cell’s layout description into a circuit description and a set of interface segments. The circuit description is a list of transistors and their connections to nodes of the circuit. A node is any electrically conductive path not including a transistor. A node is specified by a number, which is called its node number. Often during the extraction we will find that two node numbers have been assigned to what turns out to be the same node. When this happens the extractor merges the two node numbers, so that both numbers refer to the same node.

An interface segment is specified by a line segment, a layer, and a node number. Each external interface segment is assigned a node number corresponding to the node that generated the segment. We can differentiate between two types of nodes in the cell—nodes that have external interface segments and those that do not. Nodes that have an external interface segment are called parameter nodes. Nodes that do not have any external interfaces segment are called local nodes. This distinction is similar to that of parameter and local variables of procedures in programming languages. Parameters nodes can continue on past the cell boundary. Locals are completely contained within the cell.

Let us first consider the simpler case of extraction of a geometry-only cell. A moving line algorithm, similar to that used in the Split procedure described above, is used to extract geometry-only cells. The cell is cut into horizontal swaths coinciding with the vertices of the geometry within the cell. At the bottom and top of each swath we create swath segments. These segments have a similar function to the interface segments mentioned above. Given two adjacent swaths, by comparing the swath segments at the top of the bottom swath with the swath segments at the bottom of the top swath we can propagate node information from one swath to the next. Node information stored with the segments at the bottom of the swath can be passed to the top of the swath by just following edges.

As an example, consider the geometry shown in Fig. 9. The large dots represent vertices of the cell. The area between the three dashed lines represent two adjacent swaths. Fig. 10 provides a closer look at the two swaths of Fig. 9. Node numbers are passed up from the bottom of swath A to the top by following the outer edges of the segment. We now must pass the node numbers from the top of swath A to the bottom of swath B. By running down the segment list for swath A, we see that the first segment overlaps the first segment in B. We assign node number 17 to the first segment of B. We also find that the second segment in B is overlapped by the second and third segments of A. The node numbers 43 and 8 are merged and the second segment of B receives the smaller number, 8. Finally, the third segment of B is overlapped by no one. We generate a new node number for this segment.

When we encounter an active region of a transistor we also give it a node number and propagate the node number upwards like any other piece of geometry. Also we store information about its gate, source, and drain. If any of that information is not present then we leave the field unchanged, but by the time we have seen the entire transistor this information must be known. Since the entire transistor may not be in the cell, this information may be only partially known when the analysis of the cell is complete. We have to wait until other cells are extracted to get complete information about the transistor. We therefore need a procedure for combining two partial transistor records.

Finding the external interface segments for the cell is a matter of simply noting where any geometry touches the boundary. External interface segments are also generated when the active region of a transistor touches a boundary. This allows transistors that cross cell boundaries to be identified. The list of external interface segments is attached to the cell definition, along with the circuit description. The circuit description is actually two lists of transistors—one list of transistors fully contained within the cell, and the second list of transistors whose active regions touch the boundary. The second list is used to record cases where transistors cross cell boundaries.

Now let us consider the case where a cell contains not only geometry but also calls to sub-cells. The extractor first checks each call to see if the called sub-cell has already been extracted. If it has not been extracted then the extractor is applied recursively to the sub-cell. Thus, even if a cell is called several times, it is extracted only once.

We now know that all the called cells have been extracted, leaving a set of interface segments associated with each cell. Each call specifies a transformation to apply to its cell. The transformation is applied to the starting and end points of each interface segment.

Before extracting the connectivity of the cell, we must take into account the connectivity information present in the interface segments. For example, if the sub-cell had a metal bus crossing it, there would be two interface segments for that node; one on each side of the cell. These interface segments are physically separated so the physical connectivity extractor will not find any connection between them. We must take care to ensure that the connectivity of these two interface segments is not lost. We do this by assigning a node number to each interface segment before starting the physical connectivity extraction. This is called the actual node number of the interface segment. This contrasts it with the formal node number, which is the node number assigned to it in the cell for which it is an external interface. The actual node number is assigned by adding an offset for the call that generated the interface segment to the formal node number of the interface segment. Since the formal node numbers of connected interface segments are the same, connected interface segments of the same cell receive the same actual node numbers.

Extraction can now proceed as in the case without sub-cells. The only difference is that the physical connectivity extractor must handle interface segments as well as geometry. At the end of the physical connectivity extraction phase the list of external interface segments and the circuit description are attached to the cell. Also a list of the node numbers assigned to each interface segment of each call is attached to the cell definition.

define ExtractCell[curSymbol]
foreach sub-symbol of curSymbol do
if not extracted then ExtractCell[sub-symbol]
foreach segment of the internal interface segments do
if segment touches boundary
then create an external interface segment
foreach rectangle in the symbols geometry list do
if rectangle touches boundary
then create an external interface segment
extract connectivity and devices
attach external interface segments to the curSymbol
attach transistor descriptors to the curSymbol
attach node numbers assigned to internal interface
segments to calls in the curSymbol
end define

After extraction, the circuit is described in a hierarchical form. This form is not directly usable by many simulators. By the nature of the problem, many simulators work on a flat description of the circuit. It may then be necessary for the extractor to fully instantiate the circuit description. (Because of the space requirements to store a fully instantiated circuit description it may make more sense for the simulator to read the hierarchical form and instantiate it internally according to its needs.)

By instantiating the circuit we can achieve, at best, linear runtime performance in the number of devices in the circuit. Still, instantiating the circuit from a hierarchical description takes much less time than examining the full layout of the circuit. If verification against an already existing circuit description is all that is desired for the extracted description, then instantiation is not necessary and verification can proceed from the hierarchical description.

Instantiating the circuit is simply a matter of tracing through the tree described by the hierarchical circuit description. A correspondence between the actual node numbers and the formal node numbers must be establisted whenever a sub-cell is entered. This can be done with a simple aliasing scheme for numbers and keeping track of an offset to apply to all node numbers in the current cell. An outline of the flattening procedure is shown below.

define Flatten[curSymbol]
local curOffset
curOffset ← newOffset
foreach transistor of curSymbol do
output transistor description
newOffset ← newOffset + (maximum node in curSymbol)
foreach call of curSymbol do
foreach interface segment of called symbol do
alias (formal node number + newOffset)
to (actual node number + curOffset)
Flatten[called symbol]
end define

The Disjoint transformation algorithm and hierarchical circuit extractor have been implemented in Mesa8 for NMOS circuits. Table I shows runtimes for the Disjoint transformation and the circuit extractor, and it compares the runtimes of this implementation with that of another circuit extractor that runs in the same enviroment, but which operates by fully instantiating the circuit. The number of transistors reported are the number of transistors in the fully instantiated layout. Regularity is the number of rectangles in the fully instantiated layout divided by the number of rectangles specified in the original hierarchical description.4 Disjoint regularity is the regularity after running the Disjoint transformation to remove overlaps. Times are for a Dorado, a high performance personal computer,9 and are reported in minutes:seconds.

From Table I we can see that the time for the disjoint transformation and circuit extraction is not strongly correlated with the number of transistors in a circuit. As the discovered regularity increases, so does the performance of the extractor. The time taken to generate the Disjoint Hierarchy is a small fraction of the time taken for circuit extraction. Consequently analysis of only the circuit extraction algorithm will be given here.

Analysis of the algorithm shows it depends more on the design style than on the actual number of rectangles in the layout. Let us assume that the connectivity extraction can be done in linear time with respect to the number of rectangles and interface segments. Further, let us assume that the number of external interface segments of a cell is proportional to the perimeter of the cell. Then if symbol x is made up of k calls to symbol i, the expected time to extract symbol x is O(kpi), where pi is the perimeter of symbol i. If ci is the number of calls to symbol i in the Disjoint hierarchy, then symbol i contributes O(cipi) to the extraction time. Thus, the contribution of all the interface segments is O(P), where P is the sum of all the cipi’s. Let R be the number of rectangles in the Disjoint hierarchy, then the total expected time for extraction is O(P) + O(R).

Table II shows values for P and R for our test cases. The runtimes of these test cases are more closely related to the total perimeter, P, than to the number of rectangles, R, or the number of transistors. Fig. 11 shows the values of P for the test case plotted against runtimes. This graph shows a strong relationship between P and runtimes. This implies that most of the extractor’s time goes into examining the interfaces between cells and little time goes into actually examining mask rectangles.

A system for multi-function design verification that exploits hierarchy and repetition has been developed. The commonly used part of the system, namely the Disjoint transformation, has been found to take a small fraction of the time required by the subsequent analyses themselves. A circuit extractor using the Disjoint Hierarchy has been implemented. This implementation shows that the benefits of exploiting hierarchy begin to pay off with even small circuits, provided that the circuits are regular. The hierarchical extractor performs best when the layout is broken down into small manageable chunks, where no one cell contains a large number of rectangles or calls. This strengthens the argument for structured design of VLSI systems. Large systems with little structure are not only to hard design but are also hard to analyze.

namenumber of regularityDisjointDisjoint flathierarchical
transistorsregularitytransformextractor extractor
powtrans 2 32.7 5.7 :01 1:33 :43
adder 848 5.5 4.4 :01 4:38 :38
cherry 881 10.6 2.8 :08 2:37 2:53
raluchip 1853 6.8 3.0 :05 10:35 1:48
fifo 8082 28.8 14.2 :09 26:54 2:51
testram 20480 1231.2 457.7 :04 62:48 5:42