As part of the development CAD for design rule checks (DRC), it is necessary to use logical operations on orthogonal polygons that form the layout of an integrated circuit. Such operations as union, intersection, subtraction are performed over layers that contain orthogonal polygons. These operations are subject to stringent execution time requirements. The traditional representation of polygons in the form of bitmaps does not provide a quasi-linear dependence of time on the processed data size and requires development of new algorithms and polygon representation approaches. This paper contains a description of a modified sweeping line obscuring algorithm that achieves O(N log N) time. The algorithm uses three properties of the polygon: the separation of inner region from outer region by the edge, the belonging of edges to the set of either vertical or horizontal edges, and dissection of the layer plane into rectangular fragments which belong to either inner or outer region of the polygon. Procedures of input polygon contour representations that are dissected into sets of vertical and horizontal edges are described. As a result of performing logical operations, polygon edges of the resulting layer are formed. These edges, in turn, are converted into contour representations. The results of a computational experiment confirming the nature of the time dependences determined theoretically are presented. We propose the structure of a software system for DRC, built with the use of programming languages C++ and Lua. CAD, DRC, logical operations, orthogonal rectangles, polygons, sweeping line modified ORCID: 0000-0001-8238-0665 (M. Godovitsyn); 0000-0003-4584-9414 (J. Zhivchikova); 0000-0003-1415-7511 (N. Starostin); 0000-0003-
The IC designing main task is obtaining a workable crystal layout, which will be used to create a template for fabrication. Before transferring the designed solutions to production, it is important to perform a cycle of obtained layout verification [1]. Verification is understood as a set of checks which successful passing provides the possibility of correct chip production on the particular manufacturing enterprise equipment and it’s correspondence to the established parameters. Such checks include: design rule checking, layout versus schematic checking, electrical rule checking, parasitic extraction, etc.
The first stage of verification (DRC) consists in checking the layout for accordance with the design rules, which are described by the system of norms, restrictions, rules and procedures regulating permissible mutual arrangement of topological elements and topological structures, taking into account design features and possibilities of technological process.
2021 Copyright for this paper by its authors.
There are two phases in almost any verification procedure: the first one is the search of topological elements and specific areas, the last one is the check for design rules compliance directly.
Layout verification is usually performed using specialized CAD software. The most popular one is Calibre DRC [2,3], developed by the American company Mentor Graphics, purchased in 2017 by Siemens. There is a particularly acute question about the development of domestic CAD with similar functionality to Calibre DRC at present. Such program could solve several problems at once, including independence from foreign manufacturers, own distribution and licensing conditions. A domestic CAD program can comply with the Russian manufacturer’s and customer’s norms and rules for integrated circuits.
This paper focuses on describing the developed algorithms to perform logical operations (union, intersection, subtraction) with layers containing orthogonal polygons. These logical operations are actively used at the stage of search for topology elements and specific areas. Moreover procedures for device recognition in the IC layout are implemented on their basis [4]. The algorithms that implement logical operations are subject to strict requirements on computational costs, which in terms of time and memory should not exceed quasi-linear estimates.
We consider the integrated circuit layout, which is described by a set of orthogonal polygons. An orthogonal polygon is understood as a flat polygon with a boundary in the form of an orthogonal polyline, consisting of straight segments parallel to one of the axes of the crystal plane only [6]. The whole set of layout polygons is distributed in layers. A topological layer is understood as a set of pairwise non-intersecting orthogonal polygons. Any polygon key characteristic is belonging to a particular topological layer.
Depending on the presence of "holes" in the inner region of a polygon, it’s boundary can be singleconnected or multi-connected. Figure 1 shows examples of orthogonal polygons: a) simplest rectangles; b) polygon with a single connected boundary; c) polygon with a complex single connected boundary; d) polygon with a multi-connected boundary formed by "holes" in the polygon inner region.
Conceptually, the verification procedures consist in recognition, search, separation of topology elements into specialized layers which various metrics are computed for and the obtained values are checked for compliance with norms and restrictions for. Any inconsistencies with the rules detected in the layers get into the verification reports, which serve as a basis for the subsequent error correction in the layout.
The basic mechanism for recognition, searching and selecting topology elements are the logical operations. The list of logical operations used to verify the norms of the design rules is given in Table 1. Each of the above operations takes two polygon layers as input. The result of a logical operation is a new layer containing a set of polygons. Figure 2 shows examples of the logical operations over two polygons result.
It is proposed to describe the polygon by the coordinates of the polyline nodes (boundary nodes). Such a representation will be called contour representation, which is de facto standard representation for the layout at the verification stage [7]. In contour representation any topological layer is described by simple enumeration of all contours that form polygon boundaries. Each contour begins with an arbitrary starting node and ends with a finite node, which always coincides with the starting node. Such a representation is compact - the memory cost depends linearly on the number of nodes or edges of the layer contours.
Note that contour representation allows for variation in the input data representation: first, variation
is possible in the choice of contour start nodes; second, any contour can be bypassed in two directions;
third, variation is apparent in specifying the contour order in the enumeration. As an illustration, let us
give an example of the polygon in Figure 3, which admits many variations of contour representation;
for example, let us give two of them:
1: (
Thus, the procedure for calculating the layer inner regions can be represented as the following scheme:
Procedure "A" 1. Initial data: is an ordered set of horizontal edges; 2. Take = ∅; 3. If is empty, then exit; 4. From we extract edges with minimum value; 5. Form – half-intervals describing the boundaries of the polygon for a given ; 6. Compute = XOR ; 7. Take = ; 8. Go to item 3.
If we take into account that we can use implementations of algorithms based on the classical interval tree [11] as functions providing work with half-intervals, then the computational complexity of this procedure in memory and in time is estimated as ( ), where – is the number of horizontal edges of layer polygons.
Returning to the problems of contour representation, we note that the presented scheme has the following features. First, it does not depend on the variability in the representation of initial data (not a contour, but a reordered set of edges is fed to the input). Second, it provides consistent computation of polygon regions with acceptable (quasi-linear) computational costs. 4. Generalized procedures for calculating the results of logical operations with layers
As noted above, the logical operation input is two layers described in the contour representation. The result of a logical operation is a new layer also described in the contour representation. The problem with contour representation is that the result of logical operations requires information not about the boundaries, but about the polygon inner regions. This problem has been solved using the procedure "A", presented in detail in the previous paragraph. Let us show how to construct on its basis a generalized algorithm for calculating the result of various logical operations with two layers.
The main idea consists in synchronous parallel calculation of the first and second layers inner regions on the basis of procedure "A". In doing so for each case of "sweeping" line displacement there are calculation of layer inner regions, execution of logical operation and calculation of the final layer inner regions, calculation of transitions (correspond to polygon boundaries) from inner regions to outer ones and vice versa from outer to inner ones, formation of polygon boundaries.
Here is the procedure "B" for calculating the result of a logical operation in the form of horizontal boundary edges of the final layer polygons.
= ∅ – horizontal edges of the resulting layer; 7. If = 1, then 3. If | 1| + | 2|=0, then exit;
Compute
= min{ 1, 2};
Procedure «B» 1. Initial data: 2. Take: 1 2 1 is an ordered set of horizontal edges of the layer 1; 2 is an ordered set of horizontal edges of the layer 2; = ∅ – intervals of the inner region of layer 1 above the sweeping line; = ∅ – intervals of the inner region of layer 2 above the sweeping line; = ∅ – intervals of the inner region of resulting layer above the sweeping line; d. Take b. Form semi-intervals 1
;
Compute 1 = 1 XOR d. Take b. Form semi- intervals 2
; Compute 2 = 2 XOR 1 2 = 1; = 2; 12. Take 13. Go to item 3.
= ; for horizontal edges.
Procedure «C» 1. Initial data: 2. Take: 1 2
Note that the result of Procedure "B" is the set H of horizontal edges of the resulting polygon. Let us give the procedure "C" for obtaining vertical edges, which is similar in its essence to the procedure = ∅ – intervals of the inner region of layer 1 to the right of the sweeping line; = ∅ – intervals of the inner region of layer 2 to the right of the sweeping line; = ∅ – intervals of the inner region of resulting layer to the right of the sweeping line 9. Calculate the result of a logical operation = 10. Compute
= XOR polygon-result of the logical operation; 11. Transform semi-intervals into edges and include them in the set . 1
OPERATION 2
; – the set of semi-intervals corresponding to the boundaries of the 1 is an ordered set of vertical edges of the layer 1; 2 is an ordered set of vertical edges of the layer 2; = ∅ – vertical edges of the resulting layer; 3. If | 1| + | 2|=0, then exit; 7. If = 1, then
Compute
= min{ 1, 2};
a.
Extract edges with the value from 1 ; d. Take b. Form semi-intervals 1
; Compute 1 = 1 XOR 1
; 8. If = 2, then a. Extract edges with the value from 2 ; b. FCoormmpsuetem i2-in=te rv2aXls OR2
; c. 2 ; d. Take 2 = 2; 9. Calculate the result of a logical operation = 1 OPERATION 2 ; 10. Compute = XOR – the set of semi-intervals corresponding to the boundaries of the polygon-result of the logical operation; 11. Transfer semi-intervals into the edges and include them in the set . 12. Take = ; 13. Go to item 3.
It should be noted that procedures "B" and "C" are described in a generalized form - the abstract logical operation is executed in procedure items 9. Replacing the virtual logical operation "OPERATION" on the set of intervals with one of the concrete operations "OR", "AND", "NOT" or "XOR" gives the procedure of performing a concrete logical operation which provides the computation of all edges of the polygon.
Formally, the result of successive procedures "B" and "C" is not a contour representation, but only the set of all edges of the layer. To obtain contour representation it is necessary to compute all contours [8]. This problem is reduced to the well-known problem of calculating simple cycles in a graph, which can be solved by simply traversing in depth [12] the edge graph built on the found nodes and edges of layer polygons.
The computational complexity of the traversal procedure is linear with the number of edges of the layer polygons and is estimated as ( ). However, the edge graph procedure is computationally more expensive, but does not exceed the estimate as ( ) both in terms of running time and peak memory consumption [10].
As a result, we get the following scheme for calculating the result of logical operations on the layers: 1. Initial data: contour representation of layer 1 and layer 2; 2. Extract 1 and 2 horizontal edges of layer 1 and layer 2 3. Sort the elements of the sets 1 and 2 by ; 4. Perform the procedure «B», get a set of horizontal edges ; 5. Extract 1 and 2 vertical edges of layer 1 and layer 2; 6. Sort the elements of the sets 1 and 2 by ; 7. Perform the procedure «C», get a set of vertical edges ; 8. Construct an edge graph using the elements from and ; 9. Find all simple cycles in the depth of an edge graph 10. Save all found cycles to the contour representation of the final layer.
Accumulating information on the complexity of the individual steps of the algorithm, it can be noted that the overall computational complexity of the presented scheme for calculating the results of logical operations on the layers in the contour representation depends only on the number of edges of the layer polygons and is estimated as ( ) in terms of running time and memory consumption [9].
The implementation of algorithms and procedures presented in the work were included in the plugin library of functions for working with topological description layers, which, in its turn, is a part of the developed system of verification of DRC. This library is implemented in C++, using the C++17 standard. The implementation of the library involves containers from the standard library of C++ templates: vector, set, and algorithms for processing data in the containers.
The general architecture of the system of DRC is shown in Figure 5. In accordance with the architecture, the verification system includes the following components: an interpreter of the Lua language - allows to execute the program of automatic verification; a library of functions for working with layers, which contains functions for performing logical operations; a block of work with GDSII files; a block of work with the database of layers, which contains a block of work with reports.
It should be noted that the input data verification system are the GDSII file of the integrated circuit topology and the verification script. Output data are database of resulting layers and reports of verification algorithms work. Thus, the following possibilities are provided for the verification script: reading layers from the GDSII file; processing layers using functions from the library of functions for working with layers; saving layers to the layer database; saving logs and debugging information to the verification algorithm operation reports repository.
The presented architecture of the developed software provides ample opportunities in terms of expandability of the verification system functionality, which is provided by the large descriptive power of the Lua language within the imperative approach, as well as a wide range of opportunities to increase the functionality of the dynamically connected library of functions.
To test the functions of the library of operations on polygons, we have prepared test data, which is a set of coordinates of the vertices of the contours of polygons for two layers. The data were loaded into the testing application, and two Poly objects were created based on them, over which the operations of union, intersection, subtraction, and exclusive OR were performed. During the experiment, the size of the test data varied from 2000 to 40000 edges making up the contours in one layer.
Macbook Pro with an Intel Core i5 processor, 2.7 GHz, and 8 GB of memory was used for testing.
The results of time measurements for various operations are shown in Table 2, and their visualization is shown in the Figure 6.
Operation's time, sec.
The analysis of the obtained dependences allows us to assert that the estimate of the time costs of the operations corresponds to the theoretically obtained estimates. The absolute difference in the time spent on different operations can be explained by the fact that the number of resulting edges at different operations will be different, which leads to different recovery times for the resulting contours. The most time-consuming operations in this sense are OR and XOR, but the intersection operation AND is performed in the least time.
Thus, within the framework of the project on creation of a domestic CAD for DRC, a library was developed that implements logical operations on the layers that form the topological description of a chip. This library uses a modification of the sweeping line algorithm and properties of orthogonal polygons, which allowed to avoid the quadratic dependence of time on the number of edges in polygons and to achieve quasi-linear dependence both in time and memory consumed by operations. Further work on the library involves the implementation of calculations of various metrics, checks the obtained values for compliance with norms and constraints. Any detected inconsistencies with the rules in the layers will be collected in the verification reports, which serve as the basis for the subsequent correction of errors in the topology. 10. References