Layout method and system for multi-patterning integrated circuits

A non-transitory computer readable storage medium encoded with computer program instructions, such that when the computer program instructions are executed by a computer, the computer performs the method comprising:

• (a) generating, in the computer, a graph of a layout of at least a region in a layer of an integrated circuit (IC), where the layer is to have a plurality of circuit patterns to be patterned using at least three photomasks, the graph including nodes representing circuit patterns within the layout, the nodes connected to one another by edges representing respective separations between adjacent ones of the circuit patterns, wherein the separations are smaller than a threshold distance;
• (b) identifying, as an independent node, any of the nodes within the graph which is included in a respective single odd loop of the graph;
• (c) identifying, as a safe independent node, any said independent node not closer than a threshold distance from any other one of said independent nodes in another odd loop of the graph representing the layout of the layer of the IC;
• and
• (d) modifying the layout of the layer of the IC, if the graph representing the circuit patterns in the layout includes any odd loop without any safe independent node, so that after the modifying, each odd loop in a graph of the modified layout has at least one safe independent node.

A system comprising:

• a special purpose computer configured to generate a graph of a layout of at least a region in a layer of an integrated circuit (IC), where the layer is to have a plurality of circuit patterns to be patterned using at least three photomasks, the graph including nodes representing circuit patterns within the layout, the nodes connected to one another by edges representing respective separations between adjacent ones of the circuit patterns, wherein the separations are smaller than a threshold distance;
• the computer configured to identify, as an independent node, any of the nodes within the graph which is included in a respective single odd loop of the graph;
• the computer configured to identify, as a safe independent node, any said independent node not closer than a threshold distance from any other one of said independent nodes in another odd loop of the graph;
• the computer configured to identify if the graph representing the circuit patterns in the layout includes any odd loop without any safe independent node, and
• the computer including a layout editor for modifying the layout of the layer of the IC, so that that after the modifying, each odd loop in a graph of the modified layout has at least one safe independent node.