Application of Scan Line Methodology to Perform
Metric Operations in DRC


This article describes application of the scan-line method to metric operations in DRC. This method is known to be very fast and it is widely used as a powerful engine in computational geometry algorithms including DRC algorithms [1, p.79]. We show here that the same scan-line based engine can be used for almost all DRC operations which opens very attractive possibilities for optimization of the DRC script execution process. Here we present an approach that allows us to the extend scan-line technique capabilities to make it useful for building algorithms of metric operations. The methodology described here is implemented in Savage DRC .

Formalization of Various DRC Operations as Checking of Distances between Segments

Formalization of Metric Operations
Among all DRC operations we consider those intended to check metric correlations between different objects of topology. Such operations here are referred to as metric operations. Although every topology consists of polygons we suggest to define DRC operations in terms of segments which are edges of the polygons. If we consider only basic metric operations, such as Width, InDistance and OutDistance it is easy to show that for any of them a logical condition C(s1, s2) on segments s1 and s2 could be formulated. Then such operation on some set of polygons reduces to checking of distances between segments (edges of initial polygons) which satisfy the C condition. For example, in case of metric operation Width the simplified condition C(s1, s2) could be formulated as follows: checking of distance between segments s1 and s2 is performed if and only if these segments represent internal edges of the same polygon. Here we consider the "segment" as a data structure which includes not only the pair of points but also the reference to the polygon it belongs to and the side of the segment which lies inside the polygon. Thereafter this data structure is referred to as an extended segment.

Determination of Distance between two segments
We will restrict consideration here only to those DRC operations that check the condition "distance is not less than r units". The distance between two segments s1 and s2 is defined here as length of the shortest segment that connects s1 and s2. Then, for the distance between s1 and s2 to be not less than r units it is necessary and sufficient that no point of segment s2 lies in the neighborhood of radius r around segment s1 (see Figure 1). A similar neighborhood can be easily built for entire polygon, as it equals to external part of the union of neighborhoods of its edges. It could be an internal part of the union for other DRC operations. This kind of neighborhood is most widely used by various DRC programs when it comes to the checking of metric correlations.

Figure 1. An example of defining neighborhood of a segment.


Application of Scan-Line Method in Enumeration of Segments Subject to Check

Structure of scanning algorithm
Consider the building of an algorithm that checks DRC metric correlations which is based on scan-line technique. It is known that this technique could be naturally used to build algorithms for DRC operations from Logic and Select groups [1, p.110] or for determination of all the points where polygons of topology intersect each other [1, p.85]. Therefore it can be shown that considering the initial topology as a set of extended segments it is possible to divide the algorithm of DRC operations into two distinct modules: the universal abstract algorithm of scanning of topology with horizontal line and the block of calculation of these operations. The output of the first module is the input of the latter one and the data exchange between these modules occurs at only one point in which the scanning algorithm calls the block of logic operations once for each scanning level passing there piece of information called scan-line status [2, p.11]. The scan-line status is defined as pair (y, S) consisting of vertical coordinate of scan-line and set S of all segments of topology that intersect the scan-line including those segments which lie on the scan-line with one or both of their ends (see Figure 2). Let us assume that coordinates (x1, y1, x2, y2) of every segment in set S satisfy the condition y1 < y2. Scan levels are defined by endpoints of segments and their intersection points. In order to perform DRC metric checks it is necessary to analyze information within some neighborhood of every object of topology. In our case those objects are extended segments. It is easy to see that the information that constitutes the scan-line status defined above is not sufficient for exhaustive analysis of neighborhoods of all segments from the status. Therefore it is important to find a generalization of scan-line algorithm that allows implementation of Logic or Select operation as well as metric operations. It is also important to inherit the module structure of the original algorithm to the new one.

Figure 2. Scan line status at a given moment is defined
as the set of segments intercepting the scan line.



Scan-stripe technique

The scan approach Savage employs differs from the original one only in organization of information about scan-line status. The scanning itself is carried out the same way as before. But while the original scan-line status (namely, set S) includes only those segments that intersect the line, the generalized status includes segments that have common points with a horizontal stripe which bottom border coincides with the scan-line and which width is equal to r, where r is the parameter of the metric operation. Thereafter this new status is referred to as status of scan-stripe of width r (see Figure 3). The three elements (y, r, S) describe scan-stripe status. Obviously, when r = 0 scan-stripe status coincides exactly with status of corresponding scan-line. As before, scan levels are defined by endpoints of segments and their intersection points. It is easy to demonstrate that in order to reveal for every scanning level with scan-stripe status (y, r, S) all the violations of DRC metric correlations in given topology it is sufficient to consider only neighborhoods of radius r of segments from so called subset of active segments of set S (denoted as P(S)) and check if these neighborhoods are intersected by any other segments from set S. Subset of active segments of set S consists of non-horizontal segments from S that lie inside scan-stripe with one or both of their ends:

P(S) = { (x1, y1, x2, y2) from S |
 x1 not equal x2, y < y1 < y + r  or  y < y2 < Y + r }

Figure 3. Scan stripe status at a given moment is defined
as a set of segments intercepting the scan stripe.


In particular, rule of checking some DRC metric correlation formally defined by condition C(s1, s2) with parameter r could be formulated the following way: for each segment s1 from P(S) the distance d is calculated, which is the distance from s1 to every segment s2 from S that satisfies the condition C(s1, s2), s1 not equal s2, and compare this distance d with r. Violation of relation d > r indicates that the metric correlation being checked is violated on segments s1 and s2. When r > 0 the scan-stripe status contains sufficient information to perform all required checks on segments from set S.

Options of metric operations

It is clear that most of standard geometrical options of DRC metric operations, such as "Check parallel/non-parallel segments only", "Check vertical/ horizontal segments only", "Check segments with/without projections only" can be immediately implemented within this technique, as it uses pairs of segments. Thus, in order to implement these options it is only necessary to formulate more complex condition C(s1, s2) to select segments subject to check. However, it is more difficult but also possible to implement such polygon-based options of metric operations as "Do/don't check overlapping polygons" by adding some piece of information to the extended segment data structure.It is worth to mention that certain minor extensions of data structure that represents a segment allow one to implement such DRC features asconjunctive rules or check in selected area of layout only etc.


Optimization Considerations

As mentioned above, one of the main advantages of DRC algorithms based on scan-line technique is the significant DRC script optimization possibilities it offers. Analyzing the information flow in the graph of informational dependencies of some DRC script we search for situations that allow us to make use of the following optimization methods:

  • boolean sub-formulas extraction;
  • merging of sequential operations;
  • merging of informationally independent operations.

The first one is well known optimization method that consists in finding coinciding sub-formulas within all logical formulas of given script and separating them into individual boolean operations. For instance, the sequence of formulas below:

A = (B .or. C) .and. (D .xor. E);
F = (B .or. C) .dif. G;

could be transformed by optimizer into the following sequence:

T = B .or. C;
A = T .and. (D .xor. E);
F = T .dif. G;

On the one hand, this optimization removes the unwanted repeated calculation of sub-formulas thus contributing to increase of script execution speed. On the other hand, it replaces two initial script commands with three commands that generally may lead to increase of per-operation preprocessing time which is very noticeable in scan-line method based algorithms. Experimental results show that in our scan-line method based DRC system this kind of optimization yields substantial positive effect on overall script execution speed. However, it is only useful with formula-based DRC operations, namely - operations from Logic group.

The second method of optimization employed consists in splitting the graph of informational dependencies into chains of operations which sequentially depend on each other and merging operations in every single chain into smaller number of more complex operations. The straightforward example of such optimization can be built from Logic operations: sequence of operations

A = B .or. C;
D = E .and. F;
G = A .xor. D;

is transformed by optimizer into single operation:

G = (B .or. C) .xor. (E .and. F);

which can be carried out by single scanning pass. Although the more complex operation requires longer preprocessing time, but according to our benchmarks this optimization method gives a largedecrease of script execution time by removing those excessive per-operation preprocessing stages. The most important thing is that in the DRC system that is completely based on scan-line method, not only for Logic operations but operations of any kind may be merged with each other and executed in one scan-line pass. The last simple optimization method gives considerable improvement specifically on metric operations of DRC. Informationally independent metric operations satisfying certain conditions may be executed simultaneously in one pass of a scan-line algorithm. Of course, it is applicable to Logic operations as well.



The techniques described above were thoroughly tested on real layouts in Savage. The scan-line algorithms and it proved to be reliable and effective on layouts with millions of transistors. Employment of the optimization methods we mentioned allows users to obtain up to three times DRC script performance increase in comparison with non-optimized script execution on most of practical examples.



  1. V. Feinberg
    Geometrical problems of VLSI computer graphics
    Radio i Sviaz, Moscow, 1987.
  2. F. P. Preparata, M. I. Shamos
    Computational geometry. An introduction
    Springer-Verlag New York Inc., 1985.