Savage Enhanced with Recognition and Reporting of Hierarchical Structure of Errors

Figure Introduction

This article describes a method of reporting DRC errors implemented in Savage, applicable to multi-million transistor layouts. The method of hierarchical information inheritance is a perspective approach in an extension of capabilities of flat DRC systems. This technique makes it possible to report hierarchical errors in ordinary flat DRC systems.


Advantages of Hierarchical Error Reports

It is known that fully hierarchical DRC systems compare favorably with flat DRC systems because of some of their capabilities flat systems do not have. The higher performance on hierarchical designs and the more compact and informative error report are probably the two most important features of hierarchical systems. Of course, the former is due to their very nature. However, it is possible to implement the latter on the basis of flat DRC systems provided the input data is hierarchical. The main benefits of hierarchical error report are as follows.

First, it allows merging of multiple replications of the same error in hierarchical design, so the amount of errors reported is close to the amount of layout corrections need to be carried out in order to get rid of those errors. It is worth mentioning that substantial reduction of amount of DRC errors detected yields noticeable gain in performance in flat DRC systems with hierarchical error report capability.

Second, each DRC error detected is filled with information on its hierarchical nature in addition to geometrical information. Being included in description of particular error this information helps designer to figure out the reason of the error and the method of its correction (see Figure 1).


Figure 1. Hierarchical error display during a flat DRC run in Savage.



Third, unlike flat DRC errors, hierarchical ones are not mixed in one huge melee but distributed over project hierarchy in accordance with their origin. The information on error distribution in the hierarchy tree aims to reveal and localize erroneous parts of project.


Implementation Issues

Hierarchy Information Inheritance

The implementation of hierarchical error report in flat DRC system is based on hierarchy inheritance technique, which is described below. In order to be processed by flat DRC the input layout should be flattened. During the flattening process every polygon of the result is provided with reference to the instance tree of initial hierarchical layout [1]. The reference (called hierarchical reference) points to the instance this object belongs to in original design. Such objects are referred to as objects with compact hierarchical reference (CHR). Objects from the same instance have equal hierarchical references. In the simplest case we perform only metric operations (CHECK group) on flat layout with hierarchical references. Every time the DRC algorithm finds an error it can obtain all necessary hierarchical information about this error from hierarchical references of polygons involved (see "Virtual hierarchy tree" section). We assume here that any metric operation in DRC checks distances between edges of polygons. Hence, any error detected has the form of two segments that lie on wrong distance from each other. The situation with layer generation operations is more complex. The main idea here is that any object in generated layer is some transformation and/or combination of objects in source layers. Hence, it should inherit hierarchical references from its parents. Operations of group SELECT are easy to deal with because they perform only selecting of objects from incoming layers. From some point of view, they do not generate new objects. Thus, objects in generated layers receive the hierarchical references from their prototypes in straightforward way. At the same time, operations of LOGIC group are very likely to generate new objects by combining polygons from source layers. In case when the new polygon is a combination of polygons with identical hierarchical references the resulting polygon is assigned the same hierarchical reference. The most interesting case takes place when the new polygon represents a result of combination of polygons with different hierarchical references. While it has no definite prototype in source layers, every edge is an image of certain edge of some source polygon. It is either exact copy or part of some source edge. It allows us to apply reference distribution technique. The reference distribution means that hierarchical reference in this case are distributed over the edges of resulting polygon. Each edge of such polygon has its own hierarchical reference inherited from the corresponding source edge (see Figure 2). We assume here that edges of polygon with compact hierarchical references have the same references as the polygon. Such polygons are referred to as polygons with distributed hierarchical reference (DHR). When a polygon with distributed hierarchical reference participates in DRC error detected by some metric operation the hierarchy information for this error is taken from that edge which represents error segment.


Figure 2. Hierarchical reference distribution.



Consequent layer generation operations of DRC script can mix objects with compact and distributed hierarchical references in any combination. In general, it results in growth of number of polygons with DHR. However, at some point of DRC script execution it may happen that some polygon with DHR has equal hierarchical references on all of its edges. Provided this situation is easy to detect, it makes sense to perform the reference compacting replacing all distributed hierarchical references on the edges with single reference associated with the whole polygon. It turns polygons with DHR into polygons with CHR.


Virtual Hierarchy Tree

Our implementation of hierarchical error report in flat DRC system is based on special data structure, which is called virtual hierarchy tree. To anticipate a little, references to nodes of this tree play the role of hierarchical references described above. To define the virtual hierarchy tree for given project let's first consider the well known instance tree associated with the project [1] under assumption that the project has only one top cell (top cell is a cell that is not instanced in any other cell). For each cell of the project we choose one of its instances in the tree and mark it as main instance of the cell. All other instances are marked as virtual. Care should be taken to obey the following rule: all direct or indirect parents of main instance in the tree must be main instances. Such marks could be easily placed by means of pre-order tree traversal algorithm [2].

Each node of the tree in question (no matter main or virtual) is assigned a unique integer number - hierarchical index. Steps should be taken to ensure such arrangement of hierarchical indices as any given index could be efficiently found in the tree. The pre-order tree traversal algorithm mentioned above defines acceptable arrangement as well. The corresponding index search technique is well known. An instance tree with placed main/virtual marks and hierarchical indices is called virtual hierarchy tree (see Figure 3). During the flattening process hierarchical indices from virtual hierarchy tree are copied to polygons of corresponding instances of layout. These indices represent hierarchical references described in section "Hierarchy info inheritance". Each DRC error inherits hierarchical indices from corresponding edges of polygons involved. Section "Error classification and dispatching" describes what happens with DRC errors next.


Figure 3. Instance tree and virtual hierarchy tree.



Error Classification and Dispatching

Although all errors generated by metric operations in DRC are similar from geometrical point of view and consist of two segments, they may differ in their hierarchical nature. We distinguish two general classes of hierarchical errors - proper and cross errors. Error is defined as proper error if it occurs between two polygons that belong to the same instance of the same cell. And error is defined as cross error if polygons involved belong to different cells or to different instances of the same cell.

As our main purpose is to provide the most informative error report, we perform error dispatching during DRC script execution. The purpose of error dispatching is to find for each particular DRC error the most natural place in project hierarchy where this error can be reported. In plain words, it finds the cell that is most likely to contain the reason of the error and relates the error to this cell. Proper errors have equal hierarchical references on both segments and are dispatched in straightforward way: the proper error is reported in the cell it refers to. The reason of proper error in most cases is incorrect placement of primitives of the cell it is dispatched to. Cross errors are dispatched in accordance with the nearest common parent rule. It means that the root instance of minimal subtree of virtual hierarchy tree is found that contains both hierarchical references of the cross error. This instance is called the nearest common parent and the error is dispatched to corresponding cell. It may happen that nearest common parent for some cross error coincides with one of instances hierarchical references of this error point to. In this case we call this cross error the semi-proper error. Otherwise it is the pure cross error. The plausible reason of a semi-proper error is incorrect placement of instance in relation to primitives of its parent cell. And the likely reason of a pure cross error is incorrect relative placement of different instances in their parent cell.

Regardless of class of hierarchical error the following simple algorithm can perform the dispatching. Every time metric operation reports an error the algorithm starts to search both hierarchical references of the error in the virtual hierarchy tree simultaneously. The search begins at the root and skips from parent to child nodes building two paths from the root to the instances with desired hierarchical references. Either of two following events causes the algorithm to stop the search: the paths to the references diverge or at least one of the references is found. The error is dispatched to the cell at which instance the algorithm stopped. This instance is the nearest common parent for this error.

In order to eliminate multiple replications of the same error detected in different places of flat layout we just have to check whether the nearest common parent is represented by virtual or by main instance. If it proves to be a virtual one then the error should not be reported at all. It results in DRC errors dispatching to a cell only through its main instance in virtual hierarchy tree. Moreover, there is no necessity to build and keep in memory whole tree. In accordance with virtual hierarchy tree definition all direct and indirect children of virtual instance are virtual instances. It means that all virtual instances in the tree constitute a number of virtual subtrees. Keeping in mind our dispatching algorithm it is easy to see that it can get along with only a root instance of each virtual subtree. That's why the tree is referred to as the virtual hierarchy tree. No doubt, it takes much less memory to store virtual hierarchy tree instead of whole instance tree. However, note that hierarchical indices must be assigned under assumption that all instances from instance tree present in virtual hierarchy tree (see Figure 3 and Figure 4).


Figure 4. Compact virtual hierarchy tree



Related Overhead

Although the approach described above represents very substantial improvement for any flat DRC system, it has a number of more or less obvious drawbacks. First, it is necessary to build, store and maintain virtual hierarchy tree and hierarchical references, which consumes some computing time. Second, it requires the data structures of polygon and segment to be extended to contain hierarchical reference for polygons with CHR and DHR respectively, which increases amount of memory occupied by these structures. Third, the hierarchy info inheritance technique may lead to appearance of so called fictive vertices in polygons. Sometimes, when some layer generation operation is performed two edges of different polygons lie on the same line and should be merged into single edge of resultant polygon. But if these edges have different hierarchical references the merging should be avoided to preserve inherited hierarchical info. The vertex that separates such edges is called the fictive vertex (see Figure 5). In DRC algorithms based on scan-line technique [3, 4] fictive vertices sometimes are replaced with fictive edges of zero length.


Figure 5. Fictive vertices



Still another problem is layer generation operations of RESIZE group. These operations transform input polygons into new ones which may differ very substantially from their originals. It complicates the implementation of hierarchy info inheritance in such operations, especially when RESIZE operations with some non-trivial join styles are used.



Although this approach cannot turn a flat DRC system into fully hierarchical one, it enhances the effectiveness of DRC if flat system must be used. On small and medium size designs a flat DRC system with hierarchical error report feature can successfully compete with any hierarchical DRC system, which is proven by our experimental results.



  1. Chip navigation in Expert. TCAD Driven CAD. Volume 8, Number 9, September 1997, pp. 3-5.
  2. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ulman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
  3. V. Feinberg. Geometrical problems of VLSI computer graphics Radio i Sviaz, Moscow, 1987.
  4. Application of Scan Line Methodology to Perform Metric Operations in DRC. Simulation Standard. Volume 8, Number 12, December 1997, pp. 7-9.