Geometrical design rules, or just design rules as they are known more commonly, are layout restrictions that ensure that the manufactured circuit will connect as desired with no shortcircuits or open paths. The rules are based on known parameters of the manufacturing process, to ensure a margin of safety and to allow for process errors. For example, some nMOS processes require metal wires to be no less than 6 microns wide, as narrower wires could break when manufactured, leaving an open circuit. Similarly, the minimum distance between two metal wires is 6 microns, to prevent fabrication inaccuracies from causing the wires to touch. In some processes the design rules are very complex, involving combinations of layers in specific configurations. Designrule checking (DRC) is the process of checking these dimensions.
Recently, it was proposed that all design rules could be simplified so that checking would be easier, and uniform scaling of layout would work [Mead and Conway]. Rather than design rules being specified in absolute distances such as microns, they would be given in terms of a relative and scalable unit called lambda (). For nMOS design, a metal wire must be 3 wide, and unconnected wires must be kept 3 apart. When is 2 microns, this is equivalent to the previous rule. Since integer multiples of are easiest to use [Lyon], many real designrule sets are approximated when converted to rules. The advantage of this relaxation of the rules is that, when process fabrication allows smaller geometries, the design can easily scale simply by changing the value of . Although layer sizes do not actually scale linearly, the design rules contain tolerances to allow for many scales. This is because the rules are based on practical relationships between process layers that hold true at most scales.
The earliest attempts at designrule checking were based on an algebra of polygons [Baird; Crawford]. This algebra consists of polygonsize adjustment and set operations on the polygon boundaries. For example, the six operations merge, bloat, and, or, xor, and touch can be used to find designrule violations [Crawford]. Merging combines overlapping polygons on the same layer into one that contains the union of their areas. Bloating expands all polygons on a layer by a specified distance from their center. And, or, and xor are interlayer operations that find the intersection, union, and exclusive areas of two different layers and produce resulting polygons on a third layer. Touch finds all polygons on one layer that adjoin or intersect polygons on another layer.
FIGURE 5.4 Polygon operations for designrule checking: (a) Original polygons (b) Bloated polygons (originals are dotted) (c) Intersection of bloated polygons (violation). 
Figure 5.4 shows an example of using this method to detect a spacing error. The merged polygons are bloated by onehalf of the minimum spacing and then anded with each other to find any overlap. Algebraically, the error polygon is derived as:
error  =  bloat  (  poly1,  minspace  )  bloat  (  poly2,  minspace  )  
Implementation of polygonbased designrule checking requires the availability of intermediate layers that can hold temporary results of the algebra. When run incrementally to check new polygons, these operations can run without consuming excessive time or space. However, when an entire layout is checked at once, the intermediate layers can use a large amount of storage. In addition, polygon intersection can be very time consuming when all the polygons on a layer must be checked. For this reason, many techniques exist to speed the polygon comparison process.
Boundingbox values, stored with each polygon, can be used to eliminate quickly those polygons that should not be considered. However, even with this information it is necessary to compare all polygons when searching for overlap. A better method is one that breaks the layout into a grid of polygon subsets [Crawford; Bentley, Haken and Hon]. Each polygon need be checked against only those in its immediate grid area. As the number of grid lines increases, the number of polygons in a grid subset decreases and the neighborhood of a polygon becomes faster to check. However, polygons that cross or are near grid lines must be included in multiple grid subsets and this redundancy becomes more expensive as the grid becomes finer. At the limit, the grid lines are as fine as the minimum unit of design and the data structure becomes a bitmap of the layout. Since the extremes of this grid scheme are not effective, it is important to find a good value of grid spacing that optimizes time and space. Bentley, Haken, and Hon found that for designs that have n boxes, a grid size of n × n is best.
Another method of comparing neighboring polygons sorts the edges along one axis. If, for example, all polygons are sorted by their left edge, then the layout can be effectively scanned from left to right. This is done by moving a vertical scan line horizontally across the layout and maintaining a working set of polygons that intersect this scan line (see the shaded polygons in Fig. 5.5). As the scan line advances, new polygons are added to the working set and old ones are removed. If the polygons are presorted, they can be efficiently paged from disk and large designs can be represented with a small amount of memory. When the set is initially formed, all pairs of polygons must be compared, but as the scan line advances, each new polygon need be compared only to the others already in the set. To enhance efficiency further, the scan line can be made to advance a variable distance, always stopping at polygon edges. This is possible because no polygons will be added to or deleted from the working set if the scan line moves to a position that does not border a polygon. The sorted list of polygons can act as a source of coordinates for the advancement of the scan line. 

Another approach to polygonal designrule checking is to simplify the geometry so that the distance calculations can be quickly done. For example, if the corners of all polygons are rounded, then nonManhattan distances are easier to calculate. Even simpler is the reduction of a design to a collection of variablewidth lines [Piscatelli and Tingleff]. This notion is especially useful for printedcircuit board designrule checking since the boards have only wires and no components. A threepart algorithm determines first whether two lines are at all close, then whether they intersect, and finally whether lines are too close but not connected. In this algorithm, a line from (x_{0}, y_{0}) to (x_{1}, y_{1}) is represented parametrically as:
One observation that is often made about designrule checking is that its process is similar to that of node extraction [Losleben and Thompson]. For example, the threepart algorithm can also do node extraction by following intersections of wires. When wires are too close, they are considered to connect. If two different signals of a layout end up connected, then an electricalrule violation has occurred. On printedcircuit boards, complete node extraction is done by using this information in combination with the interlayer drill holes to propagate network paths to all layers [Kaplan].
An alternative to using polygon algebra is the raster method of designrule checking [Baker and Terman]. This is similar to the raster method of node extraction, in which a small window is used to examine the design uniformly. Every position of the window examines a different configuration and matches it against a set of error templates. If, for example, metal wires must be 3 apart, then a 4 × 4 window that matches either of the templates in Fig. 5.6 will indicate a designrule violation. In these templates, the "?" character indicates that any combination of layers may be present and the "M" and " " (blank) require metal and empty layers. Although these templates do not cover all configurations of the error, they will be passed over every location in the layout and will therefore eventually find the errors. Two templates are needed to handle the horizontal and vertical orientations of the geometry. Notice that this method works best with manhattan geometry because nonManhattan polygons must be converted to stairstepped grid points, which requires more complex error templates. For 45degree angles, there is only a modest increase in the number of templates [Seiler], but for arbitrary angles, the problem becomes very difficult. 

There are a number of problems with the raster method of designrule checking. The time spent comparing error templates with windows can be excessive, especially if the templates are numerous and the window is large. It is only by using simplified designrules, in which the largest spacing is 3 and all distances are integers, that a window as small and manageable as 4 × 4 can be used. With a window this small, all templates for one layer can be referenced directly through a table that is 2^{4×4} = 65,534 entries long [Baker and Terman]. Another problem with this rasterbased analysis is that it suffers from tunnel vision and can miss information that helps to clarify a particular configuration. This causes extraneous errors to be reported. For example, since the window cannot see global connectivity, it cannot understand that two points may approach each other if they connect elsewhere. When faced with the choice of reporting too many errors or too few, most designrule checkers fail on the side of inclusion and let the designer ignore the spurious complaints.
The advantages of rasterbased designrule checking are that it is a simple operation and that it takes little space. The simplicity of this method has led to hardware implementations [Seiler]. The saving of space is based on the fact that raster data can be produced from polygons in scanline order and then the data can be destroyed when the window has passed [Wilmore]. Thus, for a 4 x 4 window, only four scan lines need to be kept in memory. In addition, the representation can be further compacted by having the unit squares of the raster be of variable size according to the spacing of polygon vertices in the original layout [Dobes and Byrd]. These essential bitmaps (see Fig. 5.7) have more complex templates with rules for surrounding spacing but they save much memory because they represent the layout in a virtual grid style. 

The polygon approach to designrule checking takes too much space and the raster approach has too narrow a view to be effective, but there are other ways to check geometric spacing. The Lyra designrule checker [Arnold and Ousterhout] checks the corners and intersections of polygons against arbitrary spacing rules (see Fig. 5.8). Since checking is done only where the geometry changes, the scope of a corner is equivalent to a 2 × 2 window on an essential bitmap. However, the spacing rules that are applied to each corner can examine arbitrarily large areas that would exceed a fixedwindow capability, even when using essential bit maps. 

Figure 5.9 illustrates the Lyra design rules. Once again, the rule is that no two metal wires may be closer than 3 apart. A template is compared to any corner that has the specified configuration and, if it matches, Lyra checks the associated rule, which tests the vicinity of the corner. In some situations, the matching of a template indicates a designrule violation and no rule need be applied. Null rules then suffice to flag the error. 

When applying the templates, Lyra uses special code for efficiency. Lyra uses a tabular approach in which the corner configuration is indexed into a set of dispatch tables to determine which rules apply. In addition, all rotations of the template must be checked. A simple compiler produces the templates and rules from higherlevel designrule descriptions and automatically handles different template orientations. Although Lyra uses only Manhattan geometry, it would be feasible to extend this corner approach to nonManhattan checking by including cornerangle ranges in the template.
If designrule checking can be done with syntactic methods, then it is not unreasonable to apply traditional syntaxchecking techniques used in compilers. In particular, it is possible to do designrule checking by following state diagrams [Eustace and Mukhopadhyay]. Since compilerstate machines work on onedimensional data, a designrule checkingstate machine must be modified to have two entries for state selection so that it can look in two orthogonal directions. Thus, for a 13state machine, there are 13^{2} table entries to account for all combinations of the states in two orthogonal directions. Figure 5.10 shows a state table for the 3 metalspacing rule. Starting in state 0, the vertical (V) and horizontal (H) neighbor states are examined along with the presence or absence of metal. This determines the state for the current point and flags errors (E).
FIGURE 5.10 Statebased designrule checking. 
Producing state diagrams for design rules can become very complex. What is needed is a compiler that produces the state tables from higherlevelrule specifications. With such a facility, designrule checking can be done in such a simple manner that it can be easily implemented in hardware. Augmentation of the state table to include memory would reduce table size with only a modest increase in statemachine complexity. This totally stateoriented approach is a generalization of the Lyra technique in that both methods use rules for handling layerchange points. However, with enough states, the stateoriented method can also handle global information between change points.
Hierarchy is an important factor in simplifying design and is therefore useful in simplifying design analysis. Besides speeding the process, the use of hierarchy can make error messages more informative by retaining knowledge of the circuit structure. If two instances of a cell are created in similar environments, then it should not be necessary to check the contents of both of them. Hierarchical designrule checking has been used to eliminate those polygons that are redundant in a layout [Whitney]. A precheck filter removes all but one instance of a cell and leaves only those combinations of cell intersections that are unique. This same technique has been used in node extraction by reducing a cell to its external connection geometry and examining the contents only once to assign network labels [Chao, Huang, and Yam]. The extracted network can be hierarchically structured, which may be useful to other tools [Newell and Fitzpatrick]. In fact, many analysis tasks can be improved by hierarchically examining a circuit so that only one instance of a cell and its overlap is considered [Hon].
Care must be taken to ensure that instances of a cell eliminated from the check have identical environments of geometry at higher levels of the hierarchy. For example, a piece of layout placed arbitrarily across a cell may have varying effects on the design rules of identical subcells farther down the hierarchy. In regular and wellcomposed hierarchies, a hierarchical designrule checking filter eliminates much of the layout and vastly speeds checking. Restricted design styles, such as those that do not allow cell overlap, will make hierarchical checking most efficient [Scheffer]. However, in poorlycomposed hierarchies, the filter can spend more time looking for unique instance configurations than would be spent in a nonhierarchical check.
A simpler use of hierarchy in speeding designrule checking is the use of cell location to restrict the search for a polygon's neighborhood [Johnson; Shand]. Since cell instances provide bounding boxes for their contents, this information can be used to eliminate entire cells and their subcells from consideration. Where cells overlap, checking recurses through their contents, using boundary information to find neighboring polygons quickly. Shand also uses this scheme for node extraction. Thus it can be seen that hierarchy, in combination with good search methods, speeds designrule checking and other analysis tasks.
Previous  Table of Contents  Next  Static Free Software 