Multiple patterning method for semiconductor devices

1. A method of fabricating an integrated circuit (IC), comprising the steps of:

providing a layout of the IC, the layout having a set of IC features;

deriving a graph from the layout, the graph having vertices connected by edges, the vertices representing the IC features, and the edges representing spacing between the IC features;

selecting vertices for merging, which includes placing all vertices that satisfy a merging condition into groups, wherein the merging condition is that any two vertices within each group are not directly connected by an edge and share at least one neighboring vertex that is connected by N edges, where N is greater than two;

merging, using a computerized IC tool, the selected vertices in each of the groups, thereby reducing a number of edges connecting the neighboring vertex to be below N; and

removing a portion of the vertices that are connected by less than N edges;

repeating the steps of selecting, merging, and removing until all vertices of the graph are removed;

coloring the removed portion of the vertices with at most N colors, wherein each color corresponds to one photomask layer for lithography; and

fabricating a set of photomasks, each photomask corresponding to a subset of the IC features that are represented by vertices having a same color.

2. The method of claim 1 , wherein the step of merging includes modifying the layout by adding a virtual indicator to the layout, the virtual indicator designating that IC features represented by the selected vertices are to be assigned to a single photomask layer.

3. The method of claim 2 , wherein the virtual indicator is an assistant feature that is disposed in the modified layout and between IC features represented by the selected vertices, and wherein the assistant feature does not appear on a photomask.

4. The method of claim 2 , wherein the virtual indicator is a coloring marker in a reference layer of the modified layout.

5. The method of claim 2 , wherein the virtual indicator includes a text associated with IC features represented by the selected vertices.

6. The method of claim 1 , wherein the removing of the portion of the vertices also removes edges that are connected to the removed portion of the vertices.

7. The method of claim 1 , wherein each of the selected vertices is connected by N edges to other vertices.

8. A method of fabricating an integrated circuit (IC), comprising:

providing a layout of the IC, the layout having a set of IC features; and

decomposing, using a computerized IC tool, the set of IC features into N subsets of IC features such that each of the N subsets is assigned to a respective photomask layer for lithography, wherein N is greater than two,

wherein the decomposing includes:

deriving a graph from the layout, the graph having vertices connected by edges, the vertices representing the IC features, and the edges representing spacing between the IC features;

removing a portion of the vertices that are connected by less than N edges;

selecting vertices for merging, which includes grouping all vertices that satisfy a merging condition into groups, wherein the merging condition is that any two vertices within each group are not directly connected by an edge, and share at least one neighboring vertex that is connected by N edges;

merging the vertices within each group (selected vertices), thereby reducing a number of edges connecting the neighboring vertex to be below N;

repeating the removing, the selecting, and the merging until all vertices of the graph are removed; and

fabricating a set of photomasks, each photomask corresponding to one of the subsets of the IC features.

9. The method of claim 8 , wherein the removing of the portion of the vertices includes:

coloring the portion of the vertices with at most N colors, wherein each color corresponds to one photomask layer.

10. The method of claim 8 , wherein the merging of the selected vertices includes inserting a virtual indicator to the layout, the virtual indicator designating that IC features represented by the selected vertices are to be assigned to a single photomask layer.

11. The method of claim 10 , wherein the virtual indicator is an assistant feature that is disposed between two IC features represented by the selected vertices, and wherein the assistant feature appears in the layout but does not appear on a photomask.

12. The method of claim 11 , wherein the assistant feature partially covers the two IC features represented by the selected vertices.

13. The method of claim 11 , wherein the assistant feature fully covers the two IC features represented by the selected vertices.

14. The method of claim 10 , wherein the virtual indicator is one of: a coloring marker in a reference layer of the layout, and a text associated with IC features represented by the selected vertices.

15. A method of fabricating an integrated circuit (IC), comprising:

providing a layout of the IC, the layout having a set of IC features;

checking, using a computerized IC tool, if the set of IC features are suitable for multiple patterning with N photomask layers for lithography, wherein N is greater than two,

wherein the checking includes:

deriving a graph from the layout, the graph having vertices connected by edges, the vertices representing the IC features, and the edges representing spacing between the IC features that are smaller than a threshold;

removing a portion of the vertices that are connected by less than N edges, wherein the removing includes coloring the portion of the vertices with at most N colors, wherein each color corresponds to one photomask layer;

selecting vertices, which includes placing all vertices that satisfy a merging condition into groups, wherein the merging condition is that any two vertices within each group are not connected by an edge, and share at least one neighboring vertex that is connected by N edges;

merging the selected vertices within each group, thereby reducing a number of edges connecting the neighboring vertex to be below N, wherein the merging includes inserting a virtual indicator to the layout, the virtual indicator designating that IC features represented by the selected vertices are to be assigned to a single photomask layer; and

repeating the removing, the selecting, and the merging until all vertices of the graph are removed; and

fabricating N photomasks, each of the N photomasks corresponding to one of the colors.

16. The method of claim 15 , wherein the virtual indicator is an assistant polygon disposed between two IC features represented by the selected vertices.

17. The method of claim 15 , wherein each of the selected vertices is connected by N edges to other devices.