Patent ID: 8495548

Claim:
A computer implemented method for multi-patterning lithography (MPL) aware cell placement in integrated circuit (IC) design, the method comprising: performing, using an application executing using a processor and a memory in a data processing system, a global phase of cell movement of a color instance of a cell, wherein the color instance of the cell is used in the IC design from a plurality of different color instances available of the cell, wherein the global phase comprises moving the color instance of a cell from any first location in a first region the IC design to any second location in a second region the IC design, the first region having a first cost which is higher than a threshold cost and the second region having a second cost which is lower than the threshold cost, wherein the first cost is an indicator of a cumulative level of coloring conflicts between pairs of cells in the first region and the second cost is an indicator of a cumulative level of coloring conflicts between pairs of cells in the second region before moving the color instance of the cell; and performing a local phase cell movement, wherein the local phase comprises moving the color instance of the cell from a first location within a row of cells in the IC design to a second location within the row such that removing the color instance of the cell from the first location within the row and placing one of the plurality of different color instances available for the cell in the second location within the row removes a first coloring conflict between a first pair in the row without introducing a second coloring conflict between a second pair in the row, the first pair comprising the color instance of the cell and a second cell in the row, the second pair comprising the one of the plurality of different color instances available for the cell and a third cell in the row, wherein the global phase and the local phase are each performed before a final placement is produced for the IC design.