TY - GEN
T1 - Layout decomposition with pairwise coloring for multiple patterning lithography
AU - Zhang, Ye
AU - Luk, Wai Shing
AU - Zhou, Hai
AU - Yan, Changhao
AU - Zeng, Xuan
PY - 2013
Y1 - 2013
N2 - While double patterning lithography (DPL) is still in active development, triple or even quadruple patterning has recently been proposed for the next technology node. In this paper, we propose a pairwise coloring (PWC) method to tackle the layout decomposition problem for general multiple patterning lithography (MPL). The main idea is to reduce the problem to sets of concurrent bi-coloring problems. The overall solution is refined iteratively by applying a bi-coloring method for pairs of color sets per pass. One obvious advantage of this approach is that the existing DPL techniques can be reused seamlessly. Any improvement of them can directly benefit to the MPL counterpart. Moreover, we observe that with the help of the SPQR-tree graph division method, each pass can be fulfilled in nearly linear time. In addition, to prevent the solution getting stuck in the local minima, a randomized initialization strategy is incorporated. The PWC method is executed certain number of times with different randomized initial solutions, out of which the best solution is selected as output. We have implemented our method for particular triple patterning lithography (TPL). The experimental results show that compared with two recently published methods for TPL, our method can reduce the number of conflicts up to 33.2% and 44.9% respectively.
AB - While double patterning lithography (DPL) is still in active development, triple or even quadruple patterning has recently been proposed for the next technology node. In this paper, we propose a pairwise coloring (PWC) method to tackle the layout decomposition problem for general multiple patterning lithography (MPL). The main idea is to reduce the problem to sets of concurrent bi-coloring problems. The overall solution is refined iteratively by applying a bi-coloring method for pairs of color sets per pass. One obvious advantage of this approach is that the existing DPL techniques can be reused seamlessly. Any improvement of them can directly benefit to the MPL counterpart. Moreover, we observe that with the help of the SPQR-tree graph division method, each pass can be fulfilled in nearly linear time. In addition, to prevent the solution getting stuck in the local minima, a randomized initialization strategy is incorporated. The PWC method is executed certain number of times with different randomized initial solutions, out of which the best solution is selected as output. We have implemented our method for particular triple patterning lithography (TPL). The experimental results show that compared with two recently published methods for TPL, our method can reduce the number of conflicts up to 33.2% and 44.9% respectively.
UR - http://www.scopus.com/inward/record.url?scp=84893347688&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893347688&partnerID=8YFLogxK
U2 - 10.1109/ICCAD.2013.6691115
DO - 10.1109/ICCAD.2013.6691115
M3 - Conference contribution
AN - SCOPUS:84893347688
SN - 9781479910717
T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
SP - 170
EP - 177
BT - 2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers
T2 - 2013 32nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013
Y2 - 18 November 2013 through 21 November 2013
ER -