Color balancing aware double patterning

In electronic design automation, the problem of double patterning lithography (DPL) can be formulated as follows. Two features of a layout should be assigned different colors if their spacing is less than the minimum coloring spacing. Because only two colors are used in DPL, a layout may contain a pattern which cannot be assigned a color. To resolve the conflict, a stitch is used to split a feature into two parts and then the two parts can be assigned different colors. However, stitches will cause yield loss. Moreover, a balanced coloring will lead to better patterning quality. In brief, the focus of DPL is the reduction of conflicts and stitches and the balance of colors. In this paper, we propose an integer linear programming (ILP)-based algorithm to address the DPL problem with graph theory. Because it is time-consuming to generate a solution for a whole layout with ILP, we extract faces from the conflict graph which is used to represent a layout. Thus, an ILP formulation for face is proposed. Finally, these faces are merged according to the negotiation on the quality of solution. Experimental results show that, compared to the method without considering the balance of color, our algorithm can generate solutions with 15% less area difference averagely with the same quality of conflicts and stitches. Moreover, compared to the previous algorithm of layout decomposition, our algorithm can reduce the number of conflicts by 29%, the number of stitches by 12% averagely.