Optimization Online


Minimum cost Layout Decomposition and Legalization for Triple Patterning Lithography

Wenxing Zhu (wxzhu***at***fzu.edu.cn)
Xingquan Li (982670199***at***qq.com)
Ziran Zhu (406187567***at***qq.com)

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
Entry Accepted: 06/05/2015
Entry Last Modified: 01/06/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society