Color balancing for triple patterning lithography with complex designs

With the minimum feature size keeps shrinking, there are increasing dificulties to print these small features using one exposure (LE) or double exposures (LELE). To resolve the inherent physical limitations for current lithography techniques, triple patterning lithography (LELELE) has been widely recognized as one the most promising options for 14/10nm technology node. For triple patterning lithography (TPL), the designers are more interested in finding a decomposition with none of the three masks overwhelms the other. This color balancing issue is of crucial importance to ensure that consistent and reliable printing qualities can be achieved. In our previous work,18 a simple color balancing scheme is proposed to handle designed without stitches, which is not capable of handling complex designs with stitches. In this paper, we further extend the previous approach to be able to simultaneously optimizing the number of stitches and balancing the color usage in the three masks. This new approach is very eficient and robust, and guarantees to find a color balancing decomposition while achieving the optimal number of stitches. For the largest benchmark with over 10 million features, experimental results show that the new approach achieves almost perfect color balancing with reasonable runtime.