A novel layout decomposition algorithm for triple patterning lithography

While double patterning lithography (DPL) has been widely recognized as one of the most promising solutions for the sub-22nm technology node to enhance pattern printability, triple patterning lithography (TPL) will be required for gate, contact, and metal-1 layers which are too complex and dense to be split into only two masks, for the 15nm technology node and beyond. Nevertheless, there is very little research focusing on the layout decomposition for TPL. The recent work [16] proposed the first systematic study on the layout decomposition for TPL. However, the proposed algorithm extending a stitch-finding method used in DPL may miss legal stitch locations and generate conflicts that can be resolved by inserting stitches for TPL. In this paper, we point out two main differences between DPL and TPL layout decompositions. Based on the two differences, we propose a novel TPL layout decomposition algorithm. We first present two new graph reduction techniques to reduce the problem size without degrading overall solution quality. We then propose a stitch-aware mask assignment algorithm, based on a heuristic that finds a mask assignment such that the conflicts among the features in the same mask are more likely to be resolved by inserting stitches. Finally, stitches are inserted to resolve as many conflicts as possible. Experimental results show that the proposed layout decomposition algorithm can achieve around 56% reduction of conflicts and more than 40X speed-up compared to the previous work.