Generalized Convexity Approach to Cell Boundary Shape Approximation


Using generalizations of the convexity concept, an approach is described for approximating polygonal domain by simplifying its geometric shape. The problem arises in IC layout design as part of the hierarchical approach to design rule checking and device/subcircuit extraction implemented in Silvaco's Expert and Savage CAD tools. Appropriate functions are based on algorithm of polynomial time complexity obtained for computing a generalized- convex approximation with a prior constraints on the number of vertices of the resulting domain. The quality of approximation is evaluated as area increase with respect to the original domain. This increase is minimized by solving a certain extremum combinatorial problem.


Problem Statement and Model Description

With the increase of the complexity of modern ICs it is impossible to achieve a speed-up of chip layout verification without taking cell hierarchy into consideration while designing. This is the case, e.g., for design of a DRC subsystem. It is a nice idea to localize checks within a cell or between a cell instance and its parent cell instance in chip's hierarchy, both to speed-up the checks and to avoid error report multiplication. However this idea works well only for ideal hierarchies with clearly separated cells. Unfortunately, the latter is not the case in real designs. Quite often cells from the same hierarchy level overlap, (e.g., to ensure connectivity). These overlap areas deliver pathological cases for DRC checks, for device extraction, and for any other hierarchy- based analysis tools.

A possible way to eliminate, or at least, minimize pathologies is to minimize these cell overlaps. A possible approach is to redefine the notion of the cell shape. Usually the shape of cell is considered to be a minimal rectangular box enclosing all objects of the cell. However quite often such box is not densely populated by cell's objects near its boundary. Therefore one might want to consider the cell shape to be the boundary of the union of regions constituting the cell. With this approach cell overlap will be reduced to an absolute minimum. A drawback of such definition is increased complexity as compared with box shape that would lead to slowing down various search-based operations. Therefore the goal is to find a trade-off between the complexity of the shape and the degree to which this cell shape approximates the actual area occupied by the cell.

The idea of approximating complicated geometric objects by those that a are of less complicated shape and easier to describe is the basis of many algorithms of computational geometry finding their multiple applications in image processing, pattern recognition, computer graphics, and, of course, VLSI layout design automation. The approximation of a set X of n-dimensional space Rn by a set H is called an outer approximation, if X is contained in H. The sets X and H are assumed to be measurable, and the quality of approximation is judged from the value of the approximation density meas(X)/ meas(H), called , where "meas" is the Lebesgue measure.

The classical convex hull is an example of an outer approximation which simplifies the shape of an object and performs better than the minimal bounding box in terms of approximation density. However for many classes of geometric objects important in practice the usage of classical convexity for this purpose gives poor results. Moreover, VLSI geometries are often characterized by so-called isothetic domains, the boundary of which is formed by segments parallel to the coordinate axes. the use of a conventional convex hull for domains of this kind violates the isotheticity condition.

These factors make classical convexity very difficult to use and force us to turn to wider classes of outer approximations considered in literature. A suitable class for the approximation of isothetic objects is orthoconvex objects, where orthoconvexity is convexity with respect to coordinate axes [1].

The widest and, therefore, most preferable class in the sense of density of approximation, S-convexity [2] was investigated.

Let us consider some formal definitions.

D1. An isotetic set (I-set) is a subset of Euclidian plane E2 that can be represented as a finite union of axi-oriented rectangles, which might be degenerate (Figure 1.)
D2. An isotetic domain (I-domain) D is an I-set that can be represented in the form of a finite union of non-degenerate rectangles.
D3. The R-hull (denoted by RH[D]) of the I-domain D is the minimum axi-oriented rectangle (with respect to inclusion) containing D.
D4. The sider U of the I-domain D is the maximum rectangle contained in RH[D]-interior[D] having a non-empty intersection with the boundary of RH[D]
D5. S-hull (denoted by SH[D]) of the I-domain D is the isotetic domain obtained by removing all its siders from the R-hull of the I-domain D (Figure 2).

Figures 1-4. Non-rectangular cell shapes generated by Expert.


It is readily seen that the S-hull satisfies the convexity axioms. Therefore, S-convex hulls are defined with help of equation SH[D]=D.

The problem of optimal simplification of cell boundary shapes is in computing the S-convex approximation of highest density with number of vertices bounded by or reasonable constant r. Let us denote this approximation by SH[D,r] (Figures 3 and 4).

It was discovered that this original geometric problem is reduced to a particular discrete extremal problem, for which an algorithm based on dynamic programming was constructed.

The estimation of the complexity of the algorithm takes O(rN) operations what is acceptable for practiced designs.


[1]	Rawlins G.J.E. and Wood D. Ortho-convexity and its generalizations, 
	in: Computational Morphology, 137-152. Elsevier, 1988.

[2]	Azarenok A., Martynchik V., Metelskii N. Computation of Generalized 
	Convex Approximations, in: Comp. Maths. Phys., Vol. 33, No. 12, 
	pp. 1641-1651. Elsevier, 1994.