Scalable Multiple Patterning Layout Decomposition Implemented by a Distribution Evolutionary Algorithm ¹¹1This work was supported in part by the National Key R& D Program of China (2021ZD0114600).

To address the MPLD problem,the layout is represented by a decomposition graph (DG) consisting of a set of nodes $V$ and two sets of edges, $CE$ and $SE$, which contain the conflicting edges and stitch edges, respectively [34]. Accordingly, the goal of MPLD is to assign nodes of $V$ with $k$ colors, trying to achieve a nice trade-off between the numbers of conflict and stitch, respectively defined by

and

Then, minimization of conflicts and stitches can be formulated as

where $\alpha$ is the weight parameter, set as $0.1$ in this paper [32]. For cases $k=2,3,4$, problem (3) corresponds to the DPLD problem, the TPLD problem and the QPLD problem, respectively.

As presented in OpenMPL [31, 32], the work flow of MPLD starts with generation of the decompositon graph $G$. Then, size of graph $G$ is reduced by the graph simplification operations, and candidate stitches are inserted to get a modified conflicting graph $G^{\prime}$. Before addressing the layout decomposition, $G^{\prime}$ is further simplified to a reduced graph $G^{\prime\prime}$. Establishing an optimization model for $G^{\prime\prime}$, one can employ a selected optimization algorithm to get the colored graph $G^{\prime\prime}$. At last, the decomposition result of layout can be obtained by recovering the coloring result of $G^{\prime\prime}$ to that of the original conflicting graph $G$. Details of the framework of OpenMPL are referred to [31, 32].

OpenMPL incorporates an ILP approach, an SDP approach and a flexible exact cover-based approach as three alternative routines of MPLD. To improve the efficiency of layout decomposition, we proposed to address it by a distribution evolutionary algorithm based on a population of probability models (DEA-PPM) [33], and get the work flow of layout decomposition illustrated in Fig. 1.

The framework of DEA-PPM for GCPs is presented in Algorithm 1 [33]. It is implemented based on a distribution population $\mathbf{Q}(t)=(\mathbf{q}^{[1]}(t),\dots,\mathbf{q}^{[np]}(t))$ and a solution population $\mathbf{P}(t)=(\mathbf{x}^{[1]}(t),\dots,\mathbf{x}^{[np]}(t))$, where $\mathbf{x}^{[i]}(t)$ corresponds to $\mathbf{q}^{[i]}(t)$ one by one for all $i\in\{1,\dots,np\}$. For $k$-colroing of a decompostion graph $G$, DEA-PPM first initializes the distribution population $\mathbf{Q}(0)$ and the solution population $\mathbf{P}(0)$, and color $G$ by the iterative loop illustrated by Lines 6-12 of Algorithm 1.

The iterative loop attempts to obtain the optimal $k$-coloring assignment of $G$ by simultaneously evolving the distribution population $\mathbf{Q}(t)$ and the solution population $\mathbf{P}(t)$. In order to obtain the enhanced global exploration, it first performs orthogonal exploration on $\mathbf{Q}(t)$ to obtain $\mathbf{Q}^{\prime}(t)$. Then, it generates an intermediate solution population $\mathbf{P}^{\prime}(t)$ and performs a refinement process on $\mathbf{P}^{\prime}(t)$ to obtain $\mathbf{P}(t+1)$.

Additionally, $\mathbf{Q}^{\prime}(t)$ is refined to obtain $\mathbf{Q}(t+1)$, and the contents of the loop body are repeatedly executed, updating $\mathbf{x}^{*}_{G}$ until termination condition 1 is met. While numbers of conflicts and stitches are optimized to zero or the maximum number of iterations is reached, the iteration process is ceased and it outputs the corresponding $k$-coloring assignment of $G$. Details of the DEA-PPM is referred to Ref. [33].

Because the MPLD problem minimizes the number of stitches as well as that of the conflicts, model (3) of MPLD is slightly different with that of the GCP. Accordingly, the refinement process of DEA-PPM, presented in Algorithm 2 is slightly modified to accommodate the MPLD problem well.

As presented in Algorithm 2, the iteration budget of while loop is set as $6$ in this research. Each iteration of the while loop starts with a multi-parent greedy partition crossover (MGPX) and a tailored tabu search (TS), and ends with update of the solutions $\mathbf{p}_{1}$, $\mathbf{p}_{2}$ and $\mathbf{x}^{*}_{G}$. The MGPX is referred to Ref. [33], and the TS process is presented in Algorithm 3. The TS process for all $\mathbf{x}\in\mathbf{P}$ starts with initialization of the tabu list $\mathbf{T}$, which is a $k\times n$ matrix where element $T_{jv}$ represents the tabu level of coloring vertex $v$ with color $j$. Then, an iterative process is performed to improve the quality of $\mathbf{x}$ and to update the tabu list $\mathbf{T}$.

Improvement of a solution $\mathbf{x}$ is achieved by the promising mutations that generate promising solutions. For a vertex $v$ assigned with color $i$, a random mutation $<v,i,j>$ ($j\neq i$) is performed to assign $v$ with color $j$. While $<v,i,j>$ is not forbidden by the tabu list $\mathbf{T}$, it generates a candidate solution that would replace the coloring scheme $\mathbf{x}$. To get solutions improved as far as possible, the best promising mutation that contributes to the smallest numbers of conflicts and stitches is employed to generate the promising solution $\mathbf{y}$, by which the present solution $\mathbf{x}$ is updated if $f(\mathbf{y})<f(\mathbf{x})$.

A random mutation $<v,i,j>$ is forbidden by the tabu list if the iteration number $count$ is less than $T_{jv}$. If a solution $\mathbf{y}$ is generated by implementing $<v,i,j>$, the corresponding element of $T$ is updated by

where $count$ is the iteration number of TS, $y_{c}$ is the number of conflicts in $\mathbf{y}$, $y_{s}$ is the number of stitches in $\mathbf{y}$, and $r$ is an integer randomly sampled in $\{1,\dots,10\}$.

The iteration of TS is repeated until termination condition 2 is satisfied, that is, a solution without stitches and conflicts is obtained or the number of iterations reaches the iteration budget $5*|V|$.

As presented in [32], OpenMPL works well for TPLD of the ISCAS benchmarks, where the minimum coloring spacing $min_{cs}$ is set as 120nm for the benchmarks C432-C7552 and 100nm for the benchmarks S1488-S15850. Then, we compare the decomposition results of DEA-PPM with those of the ILP and the SDP.

The decomposition results of three algorithms are presented in Tab. 1. For the small value of $min_{cs}$, vertexes of the decomposition graph would be incident to less edges. The results demonstrate that the proposed DEA-PPM, as a stochastic optimization algorithm, can always achieve the same results as ILP with less running time. Because the SDP method addresses a continuously relaxed problem of model (3), it runs faster than ILP and DEA-PPM, but cannot always converge to the global optimal solutions at all time. Consequently, the decomposition results obtained by the SDP method are generally the same as or worse than those of ILP and DEA-PPM.

It is surprising that the standard deviation of cost is zero, which shows that all independent runs of DEA-PPM converge to the global optimal solution of model (3). Furthermore, the standard deviations of running time are collected in Fig. 3. It is demonstrated that the standard deviation of running time is ignorable for most of the benchmark layouts, except that the standard deviations of running time are about a few seconds for the cases S35392, S38584 and S15850.

To demonstrate the scalability of our proposed method for various lithography technologies, we investigate the TPLD of ISCAS benchmarks by setting the minimum coloring spacing $min_{cs}=160nm$. Because the lithography resolution is lower, there could be more conflicting edges in the layout graph, and more stitches would be inserted to get the decomposition graph colorable. Accordingly, the community structure of the decomposition graph could be fuzzier, and decomposition of the layouts is more challenging.

The experimental results collected in Table 2 show that DEA-PPM can deal well with the low-resolution TPLD problem. Compared with the ILP, DEA-PPM contributes to a decrease of more than one order of magnitude of the running time at the expense of a bit increase of the cost values. Meanwhile, the cost values optimized by DEA-PPM are much smaller than the results of SDP, while the running time of DEA-PPM is a bit greater that of SDP. The histograms illustrated in Fig. 4 show that the standard deviations of cost values are smaller than $3$, and those of running time are not more than $10$ seconds. Accordingly, DEA-PPM is also robust when applied to address the TPLD problem with $min_{cs}=160nm$.

Besides varied settings of the lithography resolution, we further test the scalability of DEA-PPM by investigating the QPLD problem, where the minimum coloring spacing is set as $200nm$ for 10 ISCAS benchmarks. The test results are listed in Table 3, and Fig. 5 illustrates the standard deviations of both cost values and running time for 10 independent runs. Since the ILP cannot address the C6288 benchmark in 1 hour, we denote the corresponding results by ‘-’.

The obtained cost values of DEA-PPM are generally better than that of SDP, and its running time is much shorter than that of ILP. It is surprising that compared with the ILP, DEA-PPM achieves better cost values on cases C432, C6288 and C7552 with much shorter running time. Although the running time of DEA-PPM is a bit longer than that of SDP, the obtained better cost values still demonstrate its competitiveness on the QPLD problem. Fig. 5 demonstrates that the standard deviations of cost value is about $0.5$ for all $10$ benchmarks, and the running time varies with standard deviations less than $5$ seconds for most benchmarks except for C3540.