Minimum cost Layout Decomposition and Legalization for Triple Patterning Lithography
Wenxing Zhu (wxzhufzu.edu.cn)
Abstract: With the need of 16/11nm cells, triple patterning lithography (TPL) has been concerned in lithography industry. Based on a new conflict projection technique to identify conflicts, we formulate in this paper the TPL layout decomposition problem as a minimum cost coloring problem. The problem is solved in two steps. First, it is relaxed to a nonlinear 0-1 programming problem without considering stitch insertions. Second, legalization methods are introduced to legalize a solution of the nonlinear 0-1 programming problem into a feasible one. At the legalization step, we prior utilize one-stitch insertions to eliminate conflicts. A backtrack coloring algorithm is also used at this step to obtain a better coloring solution. At last, to improve scalability of our decomposition method, two graph reduction approaches are introduced. We test the decomposition method on the benchmarks C432-C7552 and S1488-S15850 with minimum coloring spacings 120nm and 100nm, respectively. Comparisons of experimental results show that our approach achieves optimal costs better than those by some state-of-the-art decomposers. Moreover, our decomposition method is faster than most of the decomposers on the tested benchmarks.
Keywords: Triple patterning lithography; layout decomposition; minimum cost coloring; legalization.
Category 1: Applications -- Science and Engineering (VLSI layout )
Entry Submitted: 06/05/2015
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|