Team 4: Integrated Circuit Layout Reconstruction
Problem Statement: Integrated Circuits are designed using a polygon representations of the wiring and transistors layers known as layout. Layout must conform to strict design rules. Typically the design rules describes the minimum width of any polygon, minimum spacing between adjacent polygons, directionality (normally only vertical or horizontal runs are allowed) and corner angles (normally only 90 degrees). Multiple wiring layers are common, with modern ICs having as many as ten wiring levels. Different wiring layers are connected through a contact or via level. The via levels must also obey their own set of design rules on size and spacing.
The process of analyzing the design of an integrated circuit involves imaging
the various layers and then using image processing to reconstruct the layout
of the different layers. Built-in biases, both in the manufacturing process
and the analysis process prevent the reconstructed layout from being a faithful
representation of the original layout. For example, sharp corners become rounded,
line widths may either expand or contract and straight lines become roughened
with many false vertices. Typical extracted layout is shown in figure 1.
Our problem is, given the raw polygon data from image processing, how can we
as faithfully as possible recreate the original layout?
There are a number of potential errors that must be avoided in any reconstruction
scheme including: creation of shorts between adjacent polygons, creation of
a break or open in an existing polygon, creation of self intersecting polygons,
creation of via opens (a break in the connection to an upper or lower layer).
The ideal algorithm should also significantly compaction the layout data by
eliminating spurious vertices.
The layout reconstruction problem has significant overlap with the general
problem of line simplification which has been extensively studied for Geographic
Information Systems (GIS). One of the first and most effective methods for line
simplification is the algorithm proposed by Douglas and Peucker in 1973.
A straightforward implementation of the algorithm runs in time O(k2) for a chain
of size k; Hershberger and Snoeyink show how to improve this to O(k log k).
This algorithm is very efficient, however it is a general line simplification
solution and not optimized to the highly specific characteristics of IC layout.
Unique features of our problem are the strict design rules governing permissible
polygon shapes as well as the constraints imposed by the via points.
 DOUGLAS, D. H., AND PEUCKER, T. K. Algorithms for the reduction of the
number of points required to represent a digitized line or its caricature. The
Canadian Cartographer 10 (1973), 112-122.
 HERSHBERGER, J., AND SNOEYINK, J. Speeding up the Douglas-Peucker line
simplification algorithm. Proc. 5th Internat. Sympos. Spatial Data Handling
(1992), pp. 134-143.