Rectilinear covering method with bounded number of rectangles for designing a VLSI chip

A method for creating a rectilinear non-convex polygonal output representative of a component used to build a VLSI circuit chip from a plurality of points corresponding to a plurality of components of the chip includes: covering the plurality of points with a set of rectangles; creating a Voronoi diagram for the set of rectangles; forming a nearest neighbor tree for the Voronoi diagram; connecting a selected set of the rectangles corresponding to the nearest neighbor tree into a non-convex rectilinear polygon; and applying the non-convex rectilinear polygon to build the VLSI chip.

FIELD OF THE INVENTION

The present invention relates to the design and manufacturing of Very Large Scale Integrated chips and, more particularly, to a method of configuring partitions for locating different circuits or other operational areas of the chip.

BACKGROUND AND RELATED ART

Very Large Scale Integrated (VLSI) chips include many electronic components (e.g., transistors, resistors, diodes, and the like) interconnected to form multiple circuit components (e.g., gates, cells, memory units, arithmetic units, controllers, decoders, and the like). The electronic and circuit components of the VLSI chip are jointly referred to as “components.”

A conventional VLSI circuit includes multiple layers of wiring (wiring layers) that interconnect the electronic and circuit components. For instance, VLSI chips are fabricated with metal or polysilicon wiring layers (collectively referred hereinafter as metal layers) that interconnect the electronic and circuit components. Common fabrication models use five or more metal layers. Wiring in each metal layer is laid out in a rectilinear or orthogonal manner so that each wire segment is parallel to either the X or Y axis.

Design engineers design VLSI chips by transforming the circuit description of the VLSI circuits into a geometric representation, referred to as layout using electronic design automation (EDA) applications. These applications provide sets of computer based tools for creating, editing, and analyzing the integrated circuit (IC) design layouts.

The layouts are created using geometric shapes representing different materials and devices of the ICs. For instance, EDA tools commonly use rectangular lines to represent wire segments interconnecting the IC components. The tools handle electronic and IC components as geometric objects of varying shapes and sizes. For sake of simplicity, geometric objects will henceforth be shown as rectangular blocks. A “circuit module” refers to the geometric representation of the electronic or IC components. Generally, the EDA applications designs typically handle circuit modules having pins on their sides, the pins making the necessary connections to the interconnect lines.

A net defines a collection of pins that need to be electrically connected. A list or subset of all the layout nets is referred to as a netlist. Thus, a netlist specifies a group of nets which, in turn, specifies the interconnections between the pins.

FIG. 1is an illustrative example of a conventional IC layout100. As shown, the layout includes five circuit modules105,110,115,120, and125with pins130-160. Four interconnect lines165-180connect the modules to their pins. Additionally, three nets specify the interconnections between the pins. Pins135,145, and160define a three-pin net, while pins130and155and pins140and150, respectively, and define a pair of two pin nets. As shown inFIG. 1, the circuit module (e.g.,105) can be provided with a plurality of pins of multiple nets.

The IC design process entails various operations. Some of the physical-design operations that EDA applications used to create IC layouts include: (1) circuit partitioning, which partitions a circuit if the circuit is too large for a single chip; (2) floor planning, that finds the alignment and relative orientation of the circuit modules; (3) placement, that determines more precisely the positions of the circuit modules; (4) routing, which completes the interconnects between the circuit modules; (5) compaction, which compresses the layout to decrease the total IC area; and (6) verification, which checks the layout to ensure that it meets design and functional requirements.

Routing is an essential operation of the physical design cycle. It is generally divided into two phases: global routing and detailed routing. For each net, global routing generates a “loose” route (also referred to as path or routing area) for the interconnect lines connecting the pins of the net. The “looseness” of the global route depends on a particular global router used. After creating the global routes, the detailed routing creates specific individual routing paths for each net.

Design automation of complex VLSI chips is often associated to a lengthy design turnaround time which, in turn, increases the time-to-market introduction. Two reasons for the large turnaround time problem include: slowness of the algorithms caused by large problem sizes (e.g., hundreds of millions of circuits and nets on a chip), and the large number of iterations between different algorithms requiring convergence to an acceptable level.

Current design tools are presently reaching the limit of their efficiency and speed as the number of circuit components such as transistors, diodes, capacitors, resistors, and the like, increase exponentially, and the complexity of their connectivity increases geometrically in term of the number of components.

A conventional approach towards improving the speed of VLSI design-automation algorithms is known as partitioning. Partitioning helps developers of the VLSI design automation tools to optimize the design parameters within each partition locally. Circuit netlists can be modeled as hypergraphs partitioned using various heuristics that are known to give good results, both in terms of runtime and quality of results.

In the geometric design of the VLSI chip, it is customary to represent circuit components such as terminals, connector corners and vias as a set of points in the X-Y plane. An example of the set of points is shown inFIG. 2A. Numeral201illustrates a terminal, and200, a collection of points. The point set representation of geometric circuits allows the tool developer to concentrate on the underlying geometric relationship among different components rather than their synthetic connectivity relationship as determined by the circuit designer. An example of a net based on the points ofFIG. 2Ais referenced inFIG. 2Bby numeral210, consisting of 34 smaller rectangles, such as215.

A major critical issue for any type of partitioning in the development of VLSI design automation algorithm is directed to the chip real estate. Since the number of components is very large and the space they occupy is always at a premium, it becomes necessary to minimize the total area of the partitions. Normally, there exists an upper bound on the number of such partitions that can be used to solve a particular problem since, as the number of partitions increases, the complexity of the algorithm(s) increases with it. The number of partitions may be determined by the designer on the basis of design constraints.

The conventional optical microlithography process in semiconductor fabrication, also known as the photolithography process, includes duplicating desired circuit patterns onto semiconductor wafers for an overall desired circuit performance. The desired circuit patterns can be represented as opaque, complete and semi-transparent regions on a template commonly referred to as a photomask. In an optical microlithography, patterns on the photomask template are projected onto a photoresist coated wafer by way of optical imaging through an exposure system.

The continuous advancement of VLSI chip manufacturing technology to meet Moore's law of shrinking device dimensions in a geometric progression has spurred the development of Resolution Enhancement Techniques (RET) and Optical Proximity Correction (OPC) methodologies in the optical microlithography. The latter is the method of choice for chip manufacturers for the foreseeable future due to its high volume yield in manufacturing and past history of success. However, the ever shrinking device dimensions combined with the desire to enhance circuit performance in the deep sub-wavelength domain require complex OPC methodologies to ensure the fidelity of mask patterns of the printed wafer.

In spite of significant advances in several forms of RET, the iterative Model-Based Optical Proximity Correction (MBOPC) has established itself as the method of choice for compensating the mask shapes for lithographic process effects. Conventional MBOPC tools include shapes on the mask design (henceforth referred to as the mask) typically defined as polygons. A pre-processing step is performed by dividing the edges of each mask shape into smaller line segments. At the heart of the MBOPC tool is a simulator that simulates the image intensity at a particular point, which is located at the center of each line segment. The segments are then moved back and forth, i.e., outwardly or inwardly from the feature interior from their original position on the mask shape at each iteration step of the MBOPC. The iteration stops as a result of the modification of the mask shapes when the image intensity at the pre-selected points matches a threshold intensity level within a tolerance limit.

While the quality of the OPC may improve as the number of segments increases, the efficiency of the MBOPC tool may decrease as the number of segments it simulates and iterates over in each iterative step increases. The number of segments, in turn, depends on the number of edges in each mask shape. Therefore, it is desirable that segments that are corrected are only those that are needed to obtain the desired lithographic quality.

While the model based OPC can be described as an optimization of mask shapes, another method known as source optimization is directed to optimizing the shape of the source pixels to improve the fidelity of the wafer shapes. The combined effect of the source and the mask optimization of the MBOPC is also known as the Source Mask Optimization (SMO).

SMO stems from the fact that light from different pixels of the source travels different distances to the wafer through the mask. The difference in traveled distances causes a phase difference in the beams of light emanating from different pixels. Differences in the phases determine how light beams interact at the wafer and mask levels. In case of constructive interferences, the light beams strengthen each other and strengthens the total effect of the light. In case of destructive interferences, the light beams weaken each other and weaken the total effect of the light. The object of SMO resides in determining the light pixels requiring to be turned on, such that the constructive interferences strengthen the effect of light where there is a need to have light on the wafer, and destructive interferences weaken the effect of light where no light is to be present thereon.

An example of a source after optimization is shown inFIG. 3by way of numeral300. A turned on pixel301is illustrated. The example illustrates only a limited number of pixels. A solution of source optimization with higher granularity of pixels is depicted inFIG. 3by numeral310.

Notwithstanding the above, it is still difficult and costly to construct a pixilated source as illustrated by, e.g.301and310(FIG. 3). An approximation of the source optimization is created by placing a filter in front of the source that approximates the ‘on pixels’. The requirement of such an approximation is that the solution pixels need to be contained within a rectilinear polygon.

The ever increasing cost of mask manufacturing and inspection and the ever increasing complexity of OPC and RET requires that the mask be correctly and accurately simulated for potential defects before the mask is manufactured. The area is generally known as Mask Manufacturability Verification or Optical Rule Checking (ORC), for which an accurate simulation is a primary concern of the ORC. This implies that the ORC simulation should not miss any real error on the mask. The cost of finding an error when the mask is actually manufactured and used for chip manufacturing is very high. Nevertheless, there are two other equally important objectives of a ORC tool. First, it needs to be done as rapidly as possible. The feedback from ORC is used for the development of OPC and RET. A fast feedback is useful to minimize the turn around time of the OPC and RET developments. Additionally, the number of few false errors should be minimized as much possible. A false error is defined as an error identified by ORC using the simulation tool, which does not happen on the wafer. Since a missed error is significantly more expensive than a false error, all the ORC tools are expected to err on the conservative side. However, since each error whether false or real needs to be checked manually, it is important that the number of false errors be minimized. If there are too many, the real errors may be missed by the manual inspection, requiring a significant amount of time to shift through all the false errors to find the real errors.

Current ORC methods tend to simulate the entire mask layout image with the most accurate geometry using conservative criteria and, further, and which have a tendency of increasing the runtime of the ORC along with the number of false errors.

The aforementioned methodology is illustrated inFIG. 4A. The input to the current art is one or more input mask layouts401created after application of one or more RET or OPC. Along with it, a target wafer image400is also provided as an input. In step402, all the target and mask shapes are subdivided into segments. In step403, a correspondence is established between each mask segment and one target shape. Next, in step404, each mask segment is simulated using a calibrated resist and optical model. The simulated wafer segment is then compared against the corresponding target segment405. If the simulated wafer segment is not contained within the tolerance of the corresponding target segment, it is reported as an error407.

The proper functioning of a chip requires strong tolerance on the printability of a wafer image. Any deviation of such tolerance are classified as an error. This is demonstrated inFIG. 4B, wherein451and452are mask layout shapes,451are the main mask shapes, and452are examples of Sub-Resolution Assist Features (SRAF) which do not print themselves but help in printing the main mask shapes451. The printed wafer image is shown as shaded shapes455. Various kinds of errors are further illustrated in the image including:461depicts a “Necking Error”, where the wafer image width becomes smaller than a pre-determined value;462depicts a “Bridging Error”, where spacing between two wafer images becomes smaller than a predetermined value;463depicts an “Edge Placement Error”, where the wafer image edge is further away than the target edge of451by a predetermined value;464depicts an “Line End Shortening Error”, where the wafer image edge at a line end is further away than the target line-end edge of451by a predetermined value;465depicts an SRAF printing error, where a portion of the SRAF prints, even though SRAFs are not expected to be printed; and466depicts additional printing errors due to diffraction effects of lighting such as side lobe printing error.

Errors are often shown as points or small rectangles on the mask, as shown inFIG. 4B, which illustrates two kinds of errors, depicted as point sets411and412. Next, ORC localizes one type of errors within the cluster, bounding one group of errors within a bounding box, such as415(FIG. 4C) for group error411. However, the bounding box does not show a very tight bound. Indeed, group of errors411includes the errors of group412. This requires having a tighter bound on one set of errors that includes all the errors of the selected group, but which does not yet encounter too many other kinds of errors that can be simply described by a rectilinear polygon with a bounded number of edges.

In view of the aforementioned considerations, it is necessary to provide in industry a method for finding a rectilinear polygon containing a set of input points, the input points being either a set of points to be clustered as a netlist, or a set of pixilated source points, or a set of ORC errors. The rectilinear polygon needs to have a small area and at the same time it requires to be bounded by a limited number of edges. This requirement can also be defined by requiring that the rectilinear polygon be covered by a maximum k number of rectangles, where k is a user provided value.

SUMMARY

In one aspect of the invention, routing a VLSI design layout includes minimizing the area of the metal layer, minimizing the total real estate. The number of bounded rectangles increases the manufacturability through Design for Manufacturability (DFM) and Optical Proximity Correction (OPC) and reduces the number of corners to improve the OPC.

In another aspect of the invention, a set of n points is provided, with k being the uppermost bound on the number of rectangles. The object is to find p=ceil(k/2) rectangles that cover the n points, This is preferably accomplished by creating a Voronoi diagram for the p rectangles, followed by creating a Nearest Neighbor Tree based on the Voronoi diagram, and finally, by connecting the Nearest Neighbor rectangles to create a rectilinear polygon.

In still another aspect, the invention provides a method wherein input points are covered by a rectilinear polygon with the smallest area, and wherein the polygon ends covered by a maximum number of rectangles, the rectangles operating as an input parameter.

In yet another aspect of the present invention, the netlist for a given set of input terminals is represented by a set of input points, wherein the ensuing a rectilinear polygon is simple for further processing, e.g., by Optical Proximity Correction (OPC). The present invention also creates a tight bound for a group of pixilated source generated by a Source Mask Optimization (SMO) method, in which case, the output source pixels can be advantageously used as a set of input points, and having the tightly bound group of pixels forming a rectilinear polygonal source. The present invention further creates a tight bound for a group of errors generated by an ORC or Design Rules Checking method, using the output error locations as input points, the tight bound for the group of errors forming the rectilinear polygon.

In a further aspect, the invention provides a method and a system for creating a rectilinear non-convex polygonal output representation of a component used in building of a VLSI chip from a plurality of points, each of the points representing a plurality of components including: a) covering said plurality of points with a set of rectangles; b) creating a Voronoi diagram with a computer for said set of rectangles; c) forming a nearest neighbor tree for said Voronoi diagram; d) connecting a selected set of said rectangles corresponding to said nearest neighbor tree into a non-convex rectilinear polygon; and e) applying said non-convex rectilinear polygon to build said VLSI chip.

DETAILED DESCRIPTION OF DETAILED EMBODIMENTS

In describing the preferred embodiment of the present invention, reference will be made in conjunction toFIGS. 5-15, wherein like numerals refer to like features.

In accordance with one embodiment of the present invention, a flow chart is shown with reference toFIG. 5.

In step501, a set of input points n is provided, the number of input points including terminals of the netlist. In another embodiment, the number of input points includes a pixilated source generated by an SMO program. In still another embodiment, the number of input points is shown to include the errors generated by ORC or DRC programs.

In the next Step502, the n input points are first covered by p rectangles, wherein
p=ceiling(k/3).

The method of covering the set of input points by rectangles such that the total area of the rectangles is minimized is described in U.S. Pat. No. 6,532,578, herein incorporated by reference, wherein a method of configuring integrated circuits using a “greedy” algorithm for partitioning n points in p isothetic or orthogonal (i.e., parallel to X and Y axes) rectangles is described.

Referring now toFIGS. 6A through 6C, an embodiment of the present invention will now be described in more detail.

InFIG. 6A, a group of 10 (n=10) points601is shown that needs to be covered by p=4 rectangles. The points602are scanned horizontally and vertically. For each scan line, two rectangles are created, and a pair of rectangles with the smallest area603and604(FIG. 6B) is selected.

Still referring toFIG. 6B, rectangles603and604are further subdivided into three rectangles with the smallest area by the scan line algorithm. Rectangle603is illustrated being subdivided into605and606, and rectangle604is subdivided into rectangles607and608(FIG. 6C). The final four rectangles depicted are605,606,607, and608(FIG. 6C).

The p rectangles created in Step502are now to be connected to create the output rectilinear polygon. This is performed in steps503,504, and505.

In step,505, a Voronoi diagram is created for the set of p rectangles (Step502). The method of creating a Voronoi diagram for a set of rectangles is described in U.S. Patent Application Publication No. 2005/0202326A1, incorporated herein by reference.

Referring toFIGS. 7 and 8A, the Voronoi diagram for a set of rectangles will now be described. A set of p rectangles is defined as a tessellation of 2D space p regions so that any point within a region i is closer to rectangle i, for i=1, . . . , p than any other rectangle j, where i is different from j, where j=1, . . . , p.

InFIG. 7, a Voronoi diagram for three rectangles701,702, and703is shown. The corresponding Voronoi diagram shows the plane partitioned into three regions, viz.,710,720and730. According to the definition of Voronoi diagram, any point within region710is closer to rectangle701than rectangles702and703. Similarly, any point within region720is closer to rectangle702than rectangles701and703.

Another example of a Voronoi diagram is illustrated inFIG. 8Ashowing seven regions corresponding to seven rectangles, wherein801is a rectangle and810within a corresponding Voronoi region.

The Voronoi diagram obtained in step503(FIG. 5) is further used in Step504to obtain the nearest neighbor tree, the first step being the nearest neighbor graph shown inFIG. 8B. The nearest neighbor graph is a dual of the Voronoi diagram showing adjacent regions connected by an edge. An example of the nearest neighbor graph is shown by numeral811(FIG. 8B) corresponding to the Voronoi diagram ofFIG. 8A.

The nearest neighbor graph is used to compute the nearest neighbor tree consisting of the Minimum Cost Spanning Tree of the Nearest Neighbor Graph, which is preferably obtained using Kruskal Minimum Cost Spanning Tree algorithm. Other Minimum Cost Spanning Tree algorithm can also be used with equal success.

In the step505(FIG. 5), the nearest neighbor tree created in step504is further used to join the p rectangles created in step502.

Referring now toFIGS. 9A,9B,9C, and9D, the rectangles are joined by having them extended, such that the rectangles that are connected by the branch of a nearest neighbor tree, as shown inFIG. 8B, are considered only for joining.

InFIG. 9A, two rectangles901and902are shown overlapping their x intervals. They can be joined by extending one of the rectangles along the y direction, as illustrated by numeral912. Rectangle901is further extended to join with903. Among the two rectangles that are to be joined, the one preferably to be extended is the one whose extension has the smallest area.

InFIG. 9B, two rectangles903and904are shown with overlap in their y intervals. They can be joined by extending one of the rectangles along the x direction, shown extended by numeral934, wherein rectangle903is further extended to join with904. Once again, of the two rectangles that are to be joined, the one preferably to be chosen is the one having an extension with the smallest area.

FIG. 9Cshows an example of connecting rectangles for the set of rectangles shown inFIG. 8. InFIG. 9C, two rectangles905and906are shown with no overlap in either the x or y intervals (i.e., overlap along the x or y axes). Therefore, they can be joined by extending one of the rectangles in the x direction and another in the y direction. An example is shown by956, wherein rectangle905is extended in the x direction by965, and rectangle906is further extended in the y direction. Among the two rectangles to be joined, the one having the extension providing the smallest area is preferably selected.

The p rectangles that were created in step502are joined to their nearest neighbor tree to those created in step505(FIG. 5). The output is a rectilinear polygon that can be covered with k rectangles. The rectangle is then outputted in step506(FIG. 5).

Rectilinear polygon999inFIG. 10shows the final result to be outputted using the nearest neighbor graph and Voronoi diagram, in accordance with a preferred embodiment of the invention.

The output rectilinear polygon is the netlist for a given set of input terminal points.FIG. 11shows an exemplary output of netlist1122, according to an embodiment of the present invention for the set of points1101. An example of a net with a limited number of rectangles is based on points1101, referenced by numeral1122, and shown consisting of ten smaller rectangles, e.g.,1120.

In another embodiment, the output rectilinear polygon is the bounding polygon for a set of pixilated source points generated by an SMO method.FIG. 12shows an exemplary output of rectilinear polygonal source1222for the set of pixilated source points1201. The solution is shown by numeral1222(FIG. 12) for the pixilated source points1201. Rectilinear polygon1222is made of seven rectangles1220having the smallest area, and covering all the pixilated source points1201.

In still another embodiment, the output rectilinear polygon is the bounding polygon for a group of errors generated by a DRC or ORC method.FIG. 13shows an exemplary output of rectilinear cover1322for the set of ORC or DRC errors shown inFIG. 4. The rectilinear polygon1322(FIG. 13) tightly bounds the errors1301by a rectilinear cover with the smallest area, and yet sufficiently simple to comprise only five rectangles1320.

In yet another embodiment illustrated inFIG. 14, a flow chart is shown wherein a number n of points and a number k of rectangles are provided as inputs (1401). In step1402, rectangles covering the n points are used to determine the aforementioned parameter p=ceil(k/3). The rectangles are scanned along the X and/or Y axes (1403). In Step1404, the nearest neighbors are found using the aforementioned scan line method. In Step1405, the nearest neighbors are joined to create a single polygon (1405). The rectilinear polygon is then outputted (1406). For illustrative purposes, the flow chart ofFIG. 14will be applied to an illustrative example based onFIGS. 15A-15D.

The rectilinear polygons will now be shown, by jointly referring toFIG. 14andFIGS. 15A-15D, to be joined by the scan line method. Steps1401and1402are the same as those described in steps501and502(FIG. 5). In Step1403, the rectangles obtained in step1402are scanned either along the X or the Y axes (FIG. 15A), wherein seven rectangles are shown by rectangles1501and1502. InFIG. 15A, the seven rectangles are scanned by scan lines1503in the X-direction. In step1404(FIG. 14), the nearest rectangles are determined in accordance to the scan lines used in step1403. This is shown inFIG. 15B, where rectangles1501and1502are identified as being the nearest ones. In Step1405(FIG. 14), the nearest rectangles are joined to form a single rectangle, as depicted inFIGS. 15B and 15C. InFIG. 15B, rectangles1501and1502are joined by rectangle1504, the joining being the same as the one described in step505(FIG. 5). InFIG. 15C, all the joining rectangles such as1504,1505,1506are shown among the seven rectangles. In step1406, the rectilinear polygon is outputted, as shown by the rectilinear polygon1510(FIG. 15D).

The present invention can also be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which—when loaded in a computer system—is able to carry out the methods.

While the invention has been described in accordance with certain preferred embodiments thereof, those skilled in the art will understand the many modifications and enhancements which can be made thereto without departing from the true scope and spirit of the invention, which is limited only by the claims appended below.