Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-05-28
2001-11-27
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C324S758010, C438S017000, C438S018000
Reexamination Certificate
active
06324673
ABSTRACT:
BACKGROUND OF INVENTION
1. Field of Invention
This invention is directed to a method, apparatus and software for acceleration of design rule checking of integrated circuit mask layouts. The invention is embodied in a method for checking an integrated circuit mask layout against predetermined design rules using endpoints. The invention is also embodied in apparatus that checks an integrated circuit mask layout against predetermined design rules. The invention is also embodied in computer software that checks an integrated circuit mask layer against predetermined design rules.
2. Description of Related Art
The use of hardware for acceleration of Design Rule Checking (hereinafter “DRC”) is known in the art. Previous hardware acceleration techniques concentrate on custom-designed hardware approaches. Design rules, however, evolve with the advance of integrated circuit technology. When new layers are introduced or design rules are modified, the design rule checking hardware has to be re-designed and re-fabricated to keep up with the changes. To avoid this situation, previous approaches only accelerate universal primitives of design rule checking. On the other hand, although design rules will change and they vary between different fabrication lines, their fundamental structures are similar. A general hardware structure is required for DRC that is applicable to design rules of different fabrication processes, and this structure should be adaptable to a specific system. Unlike custom-designed hardware, configurable hardware imposes many constraints, and none of the existing hardware acceleration methods are suited for configurable DRC computing.
DRC takes, as input, a low-level description of the mask layers and features required for a particular integrated circuit design. The CAD tool on which the layout was created produces such data. The goal of DRC is to identify places in the integrated circuit design where the design rules, such as the spacing between two features or the width of a wire, have been violated. Design rules are specified in terms of a parameterized width factor, typically referred to as lambda (“&lgr;”). This parameterized width factor allows the same design rules to be used as the feature size of the process changes. In spite of this, design rules change frequently and many fabrication processes, particularly in the sub-micron domain, will have subtly different design rules.
There are two major types of design rule checking methods. Bitmap methods were widely used in early prior art methods. The layout is rasterized into a grid of square cells, with each mask layer represented by a separate bit in each cell. Bitmaps are attractive because of the simplicity of some operations such as Boolean operations (e.g., the AND function performed between two masks) and space/width checking. Many bitmap approaches are based on Baker's algorithm. Baker's algorithm uses a 3×3 window to do the checking of minimum width of 2 bits and a 4×4 window to do the checking of minimum width of 3 bits.
There are, however, disadvantages to the prior art bitmap techniques. First, bitmaps require processing a large amount of data; this, in turn, requires large amounts of memory bandwidth and high parallelism in order to produce results with acceptable performance.
The second disadvantage is that in a design system where the grid spacing (i.e., the minimum feature spacing) is much smaller than the minimum feature size, a much larger window size is required to check for width or spacing errors. This, in turn, dictates that significant time will be spent comparing error templates with windows.
Edge-based techniques, on the other hand, use edges to represent regions in each mask layer. The amount of data needed in general is reduced and is less dependent on the mask resolution. A one-dimensional systolic architecture for design rule checking for Manhattan structures has been proposed (i.e., structures with only horizontal and vertical features intersecting at ninety-degree angles). The edge files are divided into horizontal edges and vertical edges and each set is processed independently. Horizontal edges are checked for vertical width errors and horizontal spacing errors; vertical edges are checked for horizontal width errors and vertical spacing errors. The disadvantages of this approach are that it requires seemingly impractical amount of hardware and it imposes too many restrictions on input edges.
Most of the edge-based approaches, instead, use variations on scanline algorithms. Mask layer data is transformed into an edge file that contains all non-vertical edges in the mask. Each edge is described by a pair of points, (X
min
, Y
min
) and (X
max
, Y
max
), along with an orientation field indicating if the edge borders the region from above or below. Additional layer information is needed when multiple layers are handled together. The edges are sorted in a canonical order by non-decreasing order of slope within Y
min
and X
min
before processing.
A vertical scanline sweeps horizontally across the whole mask and only stops at the X-coordinates of all the edge endpoints. Edges that intersect the current scanline are then processed. This approach requires less hardware than previously discussed methods.
These prior art methods, however, suffer from several drawbacks:
(a) First, edge-based processing leads to a fairly wide data path. For Manhattan structures, at least three coordinate fields (X
min
, X
max
and Y) are required for each edge: two X-coordinates for beginning and ending points and one Y-coordinate for the edge. If each coordinate requires 18 bits, 54 bits are required to store these three coordinates. This size requirement, in turn, imposes constraints on hardware size, overall system cost and system performance.
(b) Second, when an intermediate layer (for example, the gate layer) is generated in an edge-based algorithm, its edge file is not in canonical order, since the edge with the smallest X-coordinate of its ending point is output first. Thus, an intermediate sort is needed. This intermediate sort adds complexity to the control and data flow in the hardware system and extra hardware cost for temporary storage.
(c) Third, no prior art exists that fully addresses the edge-reconciliation problem. A general method to obtain computational parallelism in DRC is to cut each mask layer into pieces and process each piece individually. This is possible both in bit-map approaches and edge-based algorithms. Spurious width/spacing errors, however, could be generated by the DRC system because some regions are split into pieces. Sewing regions back together imposes non-trivial performance degradations (especially for edge-based approaches) when the mask is divided into many small pieces.
SUMMARY OF INVENTION
The present invention has been made in view of the above circumstances and has as an object to overcome the above problems and limitations of the prior art, and has a further object to provide an integrated circuit design rule checker, capable of overcoming the above and other problems associated with the prior art.
Additional objects and advantages of the present invention will be set forth in part in the description that follows and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.
The above and other objects of the present invention are accomplished by providing a method for analysis of an integrated circuit mask layout against predetermined design rules using a scanline. The method includes the step of transforming an integrated circuit mask layout into a plurality of endpoints and sweeping a scanline through the plurality of endpoints, pausing at predetermined intervals. The sweeping of the scanline further includes decomposing the plurality of endpoints into pluralities of true points, true endpoints and old points at each of the predetermined int
Ashar Pranav
Luo Zhen
Martonosi Margaret
Princeton University
Smith Matthew
Speight Jibreel
Sughrue Mion Zinn Macpeak & Seas, PLLC
LandOfFree
Method and apparatus for edge-endpoint-based VLSI design... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for edge-endpoint-based VLSI design..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for edge-endpoint-based VLSI design... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2616304