Discrete relaxation method for contact layer decomposition of DSA with triple patterning

Block copolymer directed self-assembly (DSA) is a simple and promising candidate next-generation device fabrication technology, which is low-cost as complement with multi-patterning for contact layer patterning. In this paper, we consider the contact layer mask and template assignment problem of DSA with triple patterning lithography of general layout. To address this problem, first we construct a weighted conflict grouping graph, in which edges with negative weights are introduced, then a discrete relaxation based mask assignment problem is proposed. The integer linear program (ILP) formulation of the discrete relaxation problem is solved for obtaining a lower bound on the optimal value of this problem. In order to improve the lower bound, some valid inequalities are introduced to prune some poor relaxation solutions. At last, the obtained discrete relaxation solution is transformed to a legal solution of the original problem by solving a template assignment problem on the layout graph, which provides an upper bound on the optimal value of the original problem. Experimental results and comparisons show the effectiveness and efficiency of our method. In addition, under the discrete relaxation theory, the quality of our experimental results can be evaluated by the obtained upper and lower bounds. Specifically, the gap between the obtained upper and lower bounds is 0 for most of the sparse benchmarks, and the average gap is 0.4% for dense benchmarks.