2013 IEEE/ACM International Conference on Computer-Aided Design (ICCAD) · 2013 · 46 citations · 18 references
ComputingComputer EngineeringComputer ScienceColor TheoryDesign ComputationParallel AlgorithmsCombinatorial OptimizationGraph ColoringGraph Layout AlgorithmsLayout OptimizationDouble Patterning LayoutInitialization
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.
18
Dividing a Graph into Triconnected Components
John E. Hopcroft, Robert E. Tarjan · SIAM Journal on Computing · 1973 · 841 citations
Edward M. McCreight · SIAM Journal on Computing · 1985 · 499 citations
Layout decomposition for triple patterning lithography
Bei Yu, Kun Yuan, Boyang Zhang et al. · 2011 · 92 citations · Full text