Method, system, and storage medium for resolving coloring conflict in multi-patterning lithography

A system, comprising one or more processors and one or more programs including instructions which, when executed by the one or more processors, cause the system to:

• access a layout of an integrated circuit (IC), the layout comprising a plurality of patterns in one or more layers of the layout;
• perform a coloring operation;
• form a list comprising at least one uncolorable cell group (UCG) of the layout based on a result of the coloring operation, wherein each of the at least one UCG comprises at least one uncolorable cell;
• and
• perform a first refinement for each UCG on the list, comprising:
• performing a movement on at least one uncolorable cell of the UCG;
• determining whether the UCG is colorable;
• and
• refining the layout by accepting the movement and removing the UCG from the list in response to the UCG being determined to be colorable.

A non-transitory computer readable storage medium, comprising instructions which, when executed by a processor, performs the steps of:

• accessing a layout of an integrated circuit (IC), the layout comprising a plurality of patterns in one or more layers of the layout;
• performing a coloring operation;
• forming a list comprising at least one uncolorable cell group (UCG) of the layout based on a result of the coloring operation, wherein each of the at least one UCG comprises at least one uncolorable cell;
• and
• performing a first refinement for each UCG on the list, comprising:
• performing a movement on at least one uncolorable cell of the UCG;
• determining whether the UCG is colorable;
• and
• refining the layout by accepting the movement and removing the UCG from the list in response to the UCG being determined to be colorable.