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;
• refining the layout by accepting the movement and removing the UCG from the list in response to the UCG being determined to be colorable, and
• withdrawing the movement of the at least one uncolorable cell in response to the UCG, for which the cell is moved, being determined to be uncolorable.

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;
• refining the layout by accepting the movement and removing the UCG from the list in response to the UCG being determined to be colorable;
• and
• performing a second refinement for each UCG left on the list subsequent to performing the first refinement, comprising:
• selecting a UCG;
• for each selected UCG,
• selecting a cell of the selected UCG;
• relocating the selected cell of the selected UCG to a white space of the layout;
• and
• refining the layout by accepting the relocating and removing the UCG from the list in response to the selected cell and selected UCG excluding the removed cell being determined to be colorable.