Method of manufacturing photo masks

Abstract

In a method of manufacturing a photo mask used in a semiconductor manufacturing process, a mask pattern layout in which a plurality of patterns are arranged is acquired. The plurality of patterns are converted into a graph having nodes and links. It is determined whether the nodes are colorable by N colors without causing adjacent nodes connected by a link to be colored by a same color, where N is an integer equal to or more than 3. When it is determined that the nodes are colorable by N colors, the nodes are colored with the N colors. The plurality of patterns are classified into N groups based on the N colored nodes. The N groups are assigned to N photo masks. N data sets for the N photo masks are output.

What is claimed is: 
     
         1 . A method of generating photo mask data for photo masks used in a semiconductor manufacturing process, the method comprising:
 acquiring a mask pattern layout in which a plurality of patterns are arranged;   converting the plurality of patterns into a graph having nodes and links, wherein each of the plurality of patterns are converted and the graph includes N pre-colored nodes that are pre-assigned to N photo masks, respectively, N being an integer equal to or more than 3;   determining whether the nodes are colorable with respect to a degree defined by a number of the links to the nodes by N colors without removing the pre-colored nodes and without causing adjacent nodes connected by a link to be colored by a same color;   when it is determined that the nodes are colorable by N colors, coloring the nodes with the N colors;   classifying the plurality of patterns into N groups based on the N colored nodes;   assigning the N groups to the N photo masks; and   outputting N data sets for the N photo masks.   
     
     
         2 . The method of  claim 1 , wherein:
 wherein the graph includes a node of which the degree is equal to or more than 1 and smaller than N, and   in the converting:
 when a minimum distance between two patterns is equal to or smaller than a threshold distance, nodes representing the two patterns are connected by a link, and 
 when a distance between two patterns is greater than the threshold distance, nodes representing the two patterns are not connected by a link. 
   
     
     
         3 . The method of  claim 2 , wherein in the determining:
 the graph is simplified by repeating a removal of a node having less than N links from the graph, and   when all nodes are removed, it is determined that the nodes are colorable by N colors.   
     
     
         4 . The method of  claim 3 , wherein:
 when all nodes are not removed, it is determined whether a remaining graph is a known N-colorable pattern, and   when it is determined that the remaining graph is a known N-colorable pattern, it is determined that the nodes are colorable by N colors.   
     
     
         5 . The method of  claim 3 , wherein:
 when all nodes are not removed, it is determined whether a remaining graph is colorable by the N colors, and   when it is determined that the remaining graph is colorable by the N colors, it is determined that the nodes are colorable by N colors.   
     
     
         6 . The method of  claim 2 , wherein:
 the plurality of patterns include one or more designated patterns,   in the determining, the graph is simplified by repeating a removal of a node having less than N links from the graph but one or more nodes corresponding to the one or more designated patterns are not removed, and   when all nodes except for one or more nodes corresponding to the one or more designated patterns are removed, it is determined that the nodes are colorable by N colors.   
     
     
         7 . The method of  claim 2 , wherein in each of the N data sets, any adjacent two patterns have a distance greater than the threshold distance. 
     
     
         8 . The method of  claim 7 , wherein in each of the N data sets, a minimum distance between any adjacent two patterns is N time the threshold distance. 
     
     
         9 . A method of manufacturing a semiconductor device, the method comprising:
 acquiring a mask pattern layout in which a plurality of patterns are arranged;   converting the plurality of patterns into a graph having nodes and links, wherein each of the plurality of patterns are converted and the graph includes N pre-colored nodes that are pre-assigned to N photo masks, respectively, N being an integer equal to or more than 3;   determining whether the nodes are colorable with respect to a degree defined by a number of the links to the nodes by N colors without removing the N pre-colored nodes and without causing adjacent nodes connected by a link to be colored by a same color, wherein the graph includes a node of which the degree is equal to or more than 1 and smaller than N;   when it is determined that the nodes are colorable by N colors, coloring the nodes with the N colors;   classifying the plurality of patterns into N groups based on the N colored nodes;   assigning the N groups to the N photo masks;   outputting N data sets for the N photo masks;   fabricating the N photo masks by using the N mask data sets;   forming a layer over a semiconductor substrate; and   patterning the layer by using the N photo masks, thereby forming patterns corresponding to the mask pattern layout into the layer.   
     
     
         10 . The method of  claim 9 , wherein in the converting:
 when a minimum distance between two patterns is equal to or smaller than a threshold distance, nodes representing the two patterns are connected by a link, and   when a distance between two patterns is greater than the threshold distance, nodes representing the two patterns are not connected by a link.   
     
     
         11 . An apparatus for analyzing a photo mask data for photo masks used in a semiconductor manufacturing process, the apparatus comprising:
 a processor; and   a non-transitory, computer-readable storage medium storing a program, the program, when executed by the processor, causes the processor to perform:
 acquiring a mask pattern layout in which a plurality of patterns are arranged; 
 converting the plurality of patterns into a graph having nodes and links, wherein each of the plurality of patterns are converted and the graph includes N pre-colored nodes that are pre-assigned to N photo masks, respectively, N being an integer equal to or more than 3; 
 determining whether the nodes are colorable with respect to a degree defined by a number of the links to the nodes by N colors without removing the N pre-colored nodes and without causing adjacent nodes connected by a link to be colored by a same color; 
 when it is determined that the nodes are colorable by N colors, coloring the nodes with the N colors; 
 classifying the plurality of patterns into N groups based on the N colored nodes; 
 assigning the N groups to the N photo masks; and 
 outputting N data sets for the N photo masks. 
   
     
     
         12 . The apparatus of  claim 11 , wherein:
 the program, when executed by the processor, further causes the processor to perform, when it is determined that the nodes are colorable by N colors:   coloring the nodes with the N colors;   classifying the plurality of patterns into N groups based on the N colored nodes;   assigning the N groups to N photo masks; and   outputting N data sets for the N photo masks.   
     
     
         13 . The apparatus of  claim 12 , wherein in the converting:
 when a minimum distance between two patterns is equal to or smaller than a threshold distance, nodes representing the two patterns are connected by a link, and   when a distance between two patterns is greater than the threshold distance, nodes representing the two patterns are not connected by a link.   
     
     
         14 . The apparatus of  claim 13 , wherein in the determining:
 the graph is simplified by repeating a removal of a node having less than N links from the graph, and   when all nodes are removed, it is determined that the nodes are colorable by N colors.   
     
     
         15 . The apparatus of  claim 14 , wherein:
 when all nodes are not removed, it is determined whether a remaining graph is a known N-colorable pattern, and   when it is determined that the remaining graph is a known N-colorable pattern, it is determined that the nodes are colorable by N colors.   
     
     
         16 . The apparatus of  claim 14 , wherein:
 when all nodes are not removed, it is determined whether a remaining graph is colorable by the N colors, and   when it is determined that the remaining graph is colorable by the N colors, it is determined that the nodes are colorable by N colors.   
     
     
         17 . The apparatus of  claim 11 , wherein:
 the plurality of patterns include one or more designated patterns,   in the determining, the graph is simplified by repeating a removal of a node having less than N links from the graph but one or more nodes corresponding to the one or more designated patterns are not removed, and   when all nodes except for one or more nodes corresponding to the one or more designated patterns are removed, it is determined that the nodes are colorable by N colors.   
     
     
         18 . The apparatus of  claim 11 , wherein in each of the N data sets, any adjacent two patterns have a distance greater than the threshold distance. 
     
     
         19 . The apparatus of  claim 18 , wherein in each of the N data sets, a minimum distance between any adjacent two patterns is N times the threshold distance. 
     
     
         20 . The apparatus of  claim 13 , wherein the mask pattern layout and the N data are in GDS-II stream format or in Open Artwork System Interchange Standard format.