
Application of Scan Line Methodology to Perform
Metric Operations in DRC
Introduction
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.
Conclusion
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.
References
- V. Feinberg
Geometrical problems of VLSI computer graphics
Radio i Sviaz, Moscow, 1987. - F. P. Preparata, M. I. Shamos
Computational geometry. An introduction
Springer-Verlag New York Inc., 1985.