• / 15
  • 下載費用:30 金幣  

基于分解成本最小化和合法化的三圖樣光刻布局分解方法.pdf

摘要
申請專利號:

CN201510394778.X

申請日:

2015.07.08

公開號:

CN105022872A

公開日:

2015.11.04

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):G06F 17/50申請日:20150708|||公開
IPC分類號: G06F17/50 主分類號: G06F17/50
申請人: 福州大學
發明人: 朱文興; 李興權
地址: 350108福建省福州市閩侯縣上街鎮大學城學園路2號福州大學新區
優先權:
專利代理機構: 福州元創專利商標代理有限公司35100 代理人: 蔡學俊
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510394778.X

授權公告號:

||||||

法律狀態公告日:

2018.03.16|||2015.12.02|||2015.11.04

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

本發明涉及一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,該方法將三圖樣光刻布局分解問題分成兩個階段求解,首先將初始圖樣布局圖轉化為無向圖,然后采用圖縮減方法來縮小問題規模;第一階段采用一個松弛優化模型對圖樣進行染色,第二階段考慮引入縫合將一個圖樣分割成多個子圖樣的方式來消除盡可能多的沖突,實現最終染色。本發明的三圖樣光刻布局分解方法分解合理,高效快速,分解結果好。

權利要求書

權利要求書
1.  一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,其特征在于包括以下步驟:
步驟S1:將布局圖轉化為無向圖;
步驟S2:采用圖縮減方法刪除點,并將其存儲;
步驟S3:所述步驟S2中的圖縮減方法第一步為刪除度小于3的點;
步驟S4:所述步驟S2中的圖縮減方法第二步為刪除內含點;
步驟S5:所述步驟S2中的圖縮減方法第三步為求解連通分支;
步驟S6:重復所述步驟S3-步驟S5三次,產生多個連通分支;
步驟S7:采用面沖突投影方法檢查每個點所代表的圖樣是否為沖突圖樣;
步驟S8:對所有點賦權,沖突圖樣的點賦權為1,對非沖突圖樣的點賦權為α=0.1;
步驟S9:采用非線性0-1整數規劃模型求解點帶權的連通分支子圖的3染色解;
步驟S10:對每一個未染色點代表的圖樣用縫合插入算法進行判斷或插入縫合;
步驟S11:對所述步驟S10中沒有縫合可插入的圖樣所在的連通分支用回溯方法得到另一個更好的3染色解,返回所述步驟S10,直到該連通分支沒有合法的松弛染色解;
步驟S12:對所述步驟S3與步驟S4中刪除的點進行染色。

2.  根據權利要求1所述的一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,其特征在于:所述步驟S1的具體實現方式為:把布局圖根據最小染色間距規則表示為無向沖突圖G(V,E),其中V=(v1,v2,...,vn)表示布局圖中的圖樣集合,E={e1,e2,…,en}表示邊集;所述最小染色間距規則為如果兩個圖樣之間的間隙小于mincs,則所述兩個圖樣之間有一條邊,其中mincs是一個常數,表示最小染色間隙;對于三圖樣光刻分解問題,給定一個二維的布局板,布局板中包含了n個不重疊的圖樣,圖樣之間有一定的間隙,且每個圖樣pi(i=1,2,...,n)的幾何結構為直角多邊形,ai為其面積,則兩個圖樣pi和pj之間的間隙為:

其中(xi,yi),(xj,yj)分別是pi和pj的坐標;根據圖樣之間的間隙d(pi,pj)和最小染色間隙mincs,可以構造出無向沖突圖G(V,E)。

3.  根據權利要求1所述的一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,其特征在于:所述步驟S3中計算所有連通分支的所有點vi(i=1,2,...,n)的度di,刪除所有度di<3的點vi,并將其存儲到刪除點集合RV中。

4.  根據權利要求1所述的一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,其特征在于:所述步驟S4中給定圖G(V,E),對于每對點vi,vj∈V有 且其中A(vi),A(vj)表示vi和vj的相鄰點構成的集合; 表示vi的相鄰點集包含在vj的相鄰點集中,則稱vi被包含在vj中,即vi為內含點;所述步驟S4的具體包括以下步驟:
步驟S41:對得到的每一個連通子圖Gc(V,E)計算并存儲vi(i=1,2,...,n)的相鄰點到集合A(vi);
步驟S42:選擇一個未被標記的點判斷所有與不相鄰的點vj,即 是否存在A(vj),(j≠ik),使得如果存在,則從Gc(V,E)中刪除點及其相連邊,并將其存儲到RV;否則標記已判斷完畢;
步驟S43:更新Gc(V,E),返回步驟S43,直到所有的點都被判斷完畢;
遍歷每個點i∈V,判斷它是否被某個與i不相鄰的頂點所包含,如果是,則點i將被刪除,存到刪除點集合RV。

5.  根據權利要求1所述的一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,其特征在于:所述步驟S5采用廣度優先搜索BFS方法求解其連通分支,對于不同的連通分支,染色解相互無關,只需獨立求解每個連通分支的染色解。

6.  根據權利要求1所述的一種基于分解成本最小化和合法化的三圖樣光刻布局 分解方法,其特征在于:所述步驟S7中采用的面沖突投影方法用以判別圖樣pi和pj是否沖突的,所述面沖突投影方法的具體實現方式如下:對于圖樣pi(i=1,2,...,n),其沖突區域regi是一個二維圓角矩形,所述圓角矩形的邊界到圖樣pi邊界的距離為mincs,即

其中坐標(xi,yi)是圖樣pi邊界上的點;所述步驟S7具體包括以下步驟:
步驟S71:對所述步驟S6得到的每一個連通子圖Gc(V,E)所對應的圖樣布局圖,計算所有圖樣pi(i=1,2,...,n)的沖突區域regi;
步驟S72:選擇一個未被標記的圖樣判斷上是否存在一區域使得在所述區域上有三個或多于三個相鄰圖樣的沖突區域 重疊相交;如果是,則進入所述步驟S73;否則進入所述步驟S74;
步驟S73:判斷圖樣與總共l+1點構成的生成子圖是否為3不可染的;如果是,則標記圖樣為沖突圖樣;否則進入步驟S74;
步驟S74:標記為非沖突圖樣,返回步驟S72,直到所有圖樣被檢查。

7.  根據權利要求1所述的一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,其特征在于:所述步驟S9采用非線性0-1整數規劃模型求解點帶權的連通分支子圖的3染色解,用以最小化未染色的點的權值之和,約束條件為有邊相連的兩個點不被分配同一種顏色,用C1,C2,C3分別表示顏色類點集合1,2,3和R4表示未染色點的集合,則可以得到優化模型:


其中wi為點vi的權重;
將優化模型(3)轉化為非線性0-1整數規劃模型:


用分支定界方法求解非線性0-1整數規劃模型(4)可以得到染色解C1,C2,C3,R4。

8.  根據權利要求1所述的一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,其特征在于:所述步驟S10引入沖突矩形,圖樣pi上由相鄰圖樣pj造成的沖突矩形,即包含pi∩regj區域的最小外接矩形rtgi←j;所述步驟S10具體包括以下步驟:
步驟S101:在未染色點集R4中選擇一個圖樣pi;
步驟S102:計算由pi的所有相鄰圖樣造成pi上的沖突矩形,將其存儲到pi的沖突矩形集Rtgi;
步驟S103:對pi的沖突矩形集Rtgi中的每個沖突矩形的四條邊,延長這四條邊至圖樣pi的邊界,生成的邊為割邊,將其存儲至割邊集CSEi;
步驟S104:判斷割邊集CSEi中的每條割邊是否同時滿足條件1,條件2以及條件3;如果滿足,則該割邊為候選縫合,將其存儲至候選縫合集CSi;
步驟S101:返回所述步驟S101,直到R4中的所有圖樣pi(i=1,2,...,m)都判斷完畢;
其中所述步驟S104中的條件1,條件2以及條件3分別為:
條件1:圖樣pi被割邊分割后產生的兩個子圖樣pi1和pi2的最小尺寸都大于最小圖樣尺寸minfs;
條件2:割邊不在圖樣pi的拐角處;
條件3:圖樣pi被割邊分割后產生的兩個子圖樣pi1和pi2,pi1和pi2的相鄰圖樣的顏色不多于2種,即pi1和pi2可以被染色且不會產生沖突。

9.  根據權利要求1所述的一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,其特征在于:所述步驟S11中回溯方法具體包括以下步驟:
步驟S1101:初始化連通分支G,要回溯的染色解X=(C1,C2,C3,R4);
步驟S1102:取子圖Gm=G/R4;
步驟S1103:用遍歷方法得到Gm的所有合法3染色解;
步驟S1104:從Gm的所有3染色解中取出一個解(C1',C2',C3'),并采用所述步驟S10中的縫插入算法進行插入縫合;
步驟S1105:如果解(C1',C2',C3',R4)滿足R4中的所有非沖突圖樣都能被插入縫合消除沖突,即那么得到回溯解X*=(C1',C2',C3',R4),輸出回溯解X*;否則,返回到所述步驟S1104;
步驟S1106:用遍歷方法得到G的所有合法解X”=(C1”,C2”,C3”,R4”),其中R4”≠R4;并計算分解成本cost(X”)=|C|+α|S|;
步驟S1101:取最小分解成本的解X”,令X*=X”,輸出回溯解X*。

10.  根據權利要求1所述的一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,其特征在于:所述步驟S12對所述步驟S3和步驟S4中刪除的點構成的集RV染色,得到最小成本的顏色;染色順序與所述步驟S3與步驟S4中被刪除的點的刪除順序相反,具體包括以下步驟:
步驟S1201:level=k,其中k為刪除點的總次數;
步驟S1202:對第level次刪除的點集RVlevel中的每個點代表的圖樣pi(1=1,2,...,|RVlevel|),計算其染第k種顏色的成本cost_ck;
步驟S1203:取使得cost_ck最小的顏色作為圖樣pi的顏色;
步驟S1204:level=level-1;
步驟S1205:返回所述步驟S1202,直到level=0。

說明書

說明書基于分解成本最小化和合法化的三圖樣光刻布局分解方法
技術領域
本發明屬于VLSI工藝制造中的光刻技術領域,特別是一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法。
背景技術
在當前的VLSI光刻制造中,集成電路規模的不斷增大及單元尺寸的不斷減小。對于22nm以下規格的單元,傳統的光刻技術已經不能滿足需求;而對于先進的極紫外光刻EUV,由于光源和材料等原因,還不能在工業上得以推廣。因此,多重圖樣光刻分解技術的提出,無疑是整個光刻發展過渡時期的良策,三重圖樣光刻技術就是這樣一種方法,對其研究可以很好的解決大規模集成電路的工藝制造瓶頸。
當前用于解決VLSI三重圖樣光刻布局分解問題的算法可分為兩大類:基于分析的分解方法和基于啟發式的分解算法。基于分析的方法一般思路是構造優化模型得到松弛解,然后將松弛解近似成可行解。這種方法可以得到比較好的分解結果,但缺點是其搜索的解空間大,求解時間長。而基于啟發式的方法的思路是用各種圖縮減技術,將問題規模縮小,再采用啟發式染色尋找較好的染色解。啟發式方法可以快速的找到解,但其方法的推廣性較差,對于不同的最小染色間隙可能無法同時適用。
現有的三重圖樣光刻分解方法存在下列一個或多個問題:(1)在計算沖突投影時只采用線投影而不是面投影,實際上面投影才是沖突投影的真正反映;(2)不能發現局部沖突(native conflict),局部沖突的發現對于問題是很重要的一步,它可以大大的減少解空間的搜索;(3)縫合(stitch)的位置不是局部最優的,好的縫合位置可以減少分解成本。因此,為了得到更好的分解結果,用面投影代替線投影作為沖突投影,在染色前先發現局部沖突,和找到一個局部最優的縫合位置的算法是很有必要的。
發明內容
有鑒于此,本發明的目的是提供一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,該方法分解合理,高效快速,分解結果好。
本發明采用以下方案實現:一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,包括以下步驟:
步驟S1:將布局圖轉化為無向圖;
步驟S2:采用圖縮減方法刪除點,并將其存儲;
步驟S3:所述步驟S2中的圖縮減方法第一步為刪除度小于3的點;
步驟S4:所述步驟S2中的圖縮減方法第二步為刪除內含點;
步驟S5:所述步驟S2中的圖縮減方法第三步為求解連通分支;
步驟S6:重復所述步驟S3-步驟S5三次,產生多個連通分支;
步驟S7:采用面沖突投影方法檢查每個點所代表的圖樣是否為沖突圖樣;
步驟S8:對所有點賦權,沖突圖樣的點賦權為1,對非沖突圖樣的點賦權為α=0.1;
步驟S9:采用非線性0-1整數規劃模型求解點帶權的連通分支子圖的3染色解;
步驟S10:對每一個未染色點代表的圖樣用縫合插入算法進行判斷或插入縫合;
步驟S11:對所述步驟S10中沒有縫合可插入的圖樣所在的連通分支用回溯方法得到另一個更好的3染色解,返回所述步驟S10,直到該連通分支沒有合法的松弛染色解;
步驟S12:對所述步驟S3與步驟S4中刪除的點進行染色。
進一步地,所述步驟S1的具體實現方式為:把布局圖根據最小染色間距規則表示為無向沖突圖G(V,E),其中V=(v1,v2,...,vn)表示布局圖中的圖樣集合,E={e1,e2,…,en}表示邊集;所述最小染色間距規則為如果兩個圖樣之間的間隙小于mincs,則所述兩個圖樣之間有一條邊,其中mincs是一個常數,表示最小染色間隙;對于三圖樣光刻分解問題,給定一個二維的布局板,布局板中包含了n 個不重疊的圖樣,圖樣之間有一定的間隙,且每個圖樣pi(i=1,2,...,n)的幾何結構為直角多邊形,ai為其面積,則兩個圖樣pi和pj之間的間隙為:
d(pi,pj)=min(xi-xj)2+(yi-yj)2---(1)]]>
其中(xi,yi),(xj,yj)分別是pi和pj的坐標;根據圖樣之間的間隙d(pi,pj)和最小染色間隙mincs,可以構造出無向沖突圖G(V,E)。
進一步地,所述步驟S3中計算所有連通分支的所有點vi(i=1,2,...,n)的度di,刪除所有度di<3的點vi,并將其存儲到刪除點集合RV中。
進一步地,所述步驟S4中給定圖G(V,E),對于每對點vi,vj∈V有且其中A(vi),A(vj)表示vi和vj的相鄰點構成的集合; 表示vi的相鄰點集包含在vj的相鄰點集中,則稱vi被包含在vj中,即vi為內含點;所述步驟S4的具體包括以下步驟:
步驟S41:對得到的每一個連通子圖Gc(V,E)計算并存儲vi(i=1,2,...,n)的相鄰點到集合A(vi);
步驟S42:選擇一個未被標記的點判斷所有與不相鄰的點vj,即 是否存在A(vj),(j≠ik),使得如果存在,則從Gc(V,E)中刪除點及其相連邊,并將其存儲到RV;否則標記已判斷完畢;
步驟S43:更新Gc(V,E),返回步驟S43,直到所有的點都被判斷完畢;
遍歷每個點i∈V,判斷它是否被某個與i不相鄰的頂點所包含,如果是,則點i將被刪除,存到刪除點集合RV。
進一步地,所述步驟S5采用廣度優先搜索BFS方法求解其連通分支,對于不同的連通分支,染色解相互無關,只需獨立求解每個連通分支的染色解。
進一步地,所述步驟S7中采用的面沖突投影方法用以判別圖樣pi和pj是否沖突的,所述面沖突投影方法的具體實現方式如下:對于圖樣pi(i=1,2,...,n), 其沖突區域regi是一個二維圓角矩形,所述圓角矩形的邊界到圖樣pi邊界的距離為mincs,即
regi={(x,y)||(x-xi)2+(y-yi)2<mincs}---(2)]]>
其中坐標(xi,yi)是圖樣pi邊界上的點;所述步驟S7具體包括以下步驟:
步驟S71:對所述步驟S6得到的每一個連通子圖Gc(V,E)所對應的圖樣布局圖,計算所有圖樣pi(i=1,2,...,n)的沖突區域regi;
步驟S72:選擇一個未被標記的圖樣判斷上是否存在一區域使得在所述區域上有三個或多于三個相鄰圖樣的沖突區域 重疊相交;如果是,則進入所述步驟S73;否則進入所述步驟S74;
步驟S73:判斷圖樣與總共l+1點構成的生成子圖是否為3不可染的;如果是,則標記圖樣為沖突圖樣;否則進入步驟S74;
步驟S74:標記為非沖突圖樣,返回步驟S72,直到所有圖樣被檢查。
進一步地,所述步驟S9采用非線性0-1整數規劃模型求解點帶權的連通分支子圖的3染色解,用以最小化未染色的點的權值之和,約束條件為有邊相連的兩個點不被分配同一種顏色,用C1,C2,C3分別表示顏色類點集合1,2,3和R4表示未染色點的集合,則可以得到優化模型:
minΣvi&Element;R4wis.t.(vi,vj)&NotElement;E,vi,vj&Element;Ck(k=1,2,3)---(3)]]>
其中wi為點vi的權重。
將優化模型(3)轉化為非線性0-1整數規劃模型:
minΣi&Element;Vwi(1-xi1)(1-xi2)s.t.xi1+xi2+xj1+xj23&ForAll;eij&Element;E-xi1+xi2-xj1+xj21&ForAll;eij&Element;Exi1-xi2+xj1-xj21&ForAll;eij&Element;E(xi1,xj2)&Element;{0,1}×{0,1}&ForAll;i&Element;V---(4)]]>
用分支定界方法求解非線性0-1整數規劃模型(4)可以得到染色解C1,C2,C3,R4。
進一步地,所述步驟S10引入沖突矩形,圖樣pi上由相鄰圖樣pj造成的沖突矩形,即包含pi∩regj區域的最小外接矩形rtgi←j;所述步驟S10具體包括以下步驟:
步驟S101:在未染色點集R4中選擇一個圖樣pi;
步驟S102:計算由pi的所有相鄰圖樣造成pi上的沖突矩形,將其存儲到pi的沖突矩形集Rtgi;
步驟S103:對pi的沖突矩形集Rtgi中的每個沖突矩形的四條邊,延長這四條邊至圖樣pi的邊界,生成的邊為割邊,將其存儲至割邊集CSEi;
步驟S104:判斷割邊集CSEi中的每條割邊是否同時滿足條件1,條件2以及條件3;如果滿足,則該割邊為候選縫合,將其存儲至候選縫合集CSi;
步驟S101:返回所述步驟S101,直到R4中的所有圖樣pi(i=1,2,...,m)都判斷完畢;
其中所述步驟S104中的條件1,條件2以及條件3分別為:
條件1:圖樣pi被割邊分割后產生的兩個子圖樣pi1和pi2的最小尺寸都大于最小圖樣尺寸minfs;
條件2:割邊不在圖樣pi的拐角處;
條件3:圖樣pi被割邊分割后產生的兩個子圖樣pi1和pi2,pi1和pi2的相鄰圖樣的顏色不多于2種,即pi1和pi2可以被染色且不會產生沖突。
進一步地,所述步驟S11中回溯方法具體包括以下步驟:
步驟S1101:初始化連通分支G,要回溯的染色解X=(C1,C2,C3,R4);
步驟S1102:取子圖Gm=G/R4;
步驟S1103:用遍歷方法得到Gm的所有合法3染色解;
步驟S1104:從Gm的所有3染色解中取出一個解(C1',C2',C3'),并采用所述步驟S10中的縫插入算法進行插入縫合;
步驟S1105:如果解(C1',C2',C3',R4)滿足R4中的所有非沖突圖樣都能被插入縫合消除沖突,即那么得到回溯解X*=(C1',C2',C3',R4),輸出回溯解X*;否則,返回到所述步驟S1104;
步驟S1106:用遍歷方法得到G的所有合法解X”=(C1”,C2”,C3”,R4”),其中R4”≠R4;并計算分解成本cost(X”)=|C|+α|S|;
步驟S1101:取最小分解成本的解X”,令X*=X”,輸出回溯解X*。
進一步地,所述步驟S12對所述步驟S3和步驟S4中刪除的點構成的集RV染色,得到最小成本的顏色;染色順序與所述步驟S3與步驟S4中被刪除的點的刪除順序相反,具體包括以下步驟:
步驟S1201:level=k,其中k為刪除點的總次數;
步驟S1202:對第level次刪除的點集RVlevel中的每個點代表的圖樣pi(1=1,2,...,|RVlevel|),計算其染第k種顏色的成本cost_ck;
步驟S1203:取使得cost_ck最小的顏色作為圖樣pi的顏色;
步驟S1204:level=level-1;
步驟S1205:返回所述步驟S1202,直到level=0。
本發明將對點的分割和圖的3染色問題松弛為非線性0-1整數規劃問題,進而用修正分枝定界算法得到高效實用的分解結果。布局分解方法的基本思想是直接把沖突和縫合同時考慮到三重圖樣光刻分解,會使得問題解空間變的很大,不利于求解,而本發明提供的方法是先將問題松弛成只考慮沖突的優化問題,解空 間指數級的減少;再對得到的最優松弛解進行合法化成可行解。運用兩步驟的分解思想,可以得到一個解空間大大減小,性能優越的布局分解方法。
相較于現有技術,本發明的有益效果是:(1)采用一種新的非沖突圖樣刪除方法。(2)給出一個識別局部沖突的充分條件,用于布局分解。(3)采用離散松弛的思想,將原問題的解空間規模大大縮小,并用改進的分枝定界方法得到最優離散松弛解。(4)在縫合插入時考慮最優的插入位置,便于解決沖突。經與ISCAS-85&89的比較實驗,結果表明本發明的三重圖樣布局分解方法,尤其對于圖樣密集的實例而言,是很有效的。
附圖說明
圖1是本發明基于分解成本最小化和合法化的三圖樣光刻布局分解方法的流程圖。
圖2是本發明一具體實施例的布局圖。
圖3是本發明一具體實施例的布局圖的分解染色結果。
具體實施方式
下面結合附圖及實施例對本發明做進一步說明。
本實施例提供一種基于分解成本最小化和合法化的三圖樣光刻布局分解方法,將三圖樣光刻布局分解問題分成兩個階段求解。首先將初始圖樣布局圖(pattern layout)轉化為無向圖G(V,E),然后采用圖縮減方法來縮小問題規模,第一階段采用一個松弛優化模型對圖樣(patterns)進行染色(coloring),第二階段考慮引入縫合(stitch)將一個圖樣分割成多個子圖樣的方式來消除盡可能多的沖突(conflict),實現最終染色;如圖1所示,具體包括以下步驟:
步驟S1:將布局圖轉化為無向圖;
步驟S2:采用圖縮減方法刪除點,并將其存儲;
步驟S3:所述步驟S2中的圖縮減方法第一步為刪除度小于3的點;
步驟S4:所述步驟S2中的圖縮減方法第二步為刪除內含點;
步驟S5:所述步驟S2中的圖縮減方法第三步為求解連通分支;
步驟S6:重復所述步驟S3-步驟S5三次,產生多個連通分支;
步驟S7:采用面沖突投影方法檢查每個點所代表的圖樣是否為沖突圖樣;
步驟S8:對所有點賦權,沖突圖樣的點賦權為1,對非沖突圖樣的點賦權為α=0.1;
步驟S9:采用非線性0-1整數規劃模型求解點帶權的連通分支子圖的3染色解;
步驟S10:對每一個未染色點代表的圖樣用縫合插入算法進行判斷或插入縫合;
步驟S11:對所述步驟S10中沒有縫合可插入的圖樣所在的連通分支用回溯方法得到另一個更好的3染色解,返回所述步驟S10,直到該連通分支沒有合法的松弛染色解;
步驟S12:對所述步驟S3與步驟S4中刪除的點進行染色。
在本實施例中,如圖1中102部分所示,所述步驟S1的具體實現方式為:把布局圖根據最小染色間距規則表示為無向沖突圖G(V,E),其中V=(v1,v2,...,vn)表示布局圖中的圖樣集合,E={e1,e2,…,en}表示邊集;所述最小染色間距規則為如果兩個圖樣之間的間隙小于mincs,則所述兩個圖樣之間有一條邊,其中mincs是一個常數,表示最小染色間隙;對于三圖樣光刻分解問題,給定一個二維的布局板,布局板中包含了n個不重疊的圖樣,圖樣之間有一定的間隙,且每個圖樣pi(i=1,2,...,n)的幾何結構為直角多邊形,ai為其面積,則兩個圖樣pi和pj之間的間隙為:
d(pi,pj)=min(xi-xj)2+(yi-yj)2---(1)]]>
其中(xi,yi),(xj,yj)分別是pi和pj的坐標;根據圖樣之間的間隙d(pi,pj)和最小染色間隙mincs,可以構造出無向沖突圖G(V,E)。
在本實施例中,如圖1中104部分所示,所述步驟S3中計算所有連通分支的所有點vi(i=1,2,...,n)的度di,刪除所有度di<3的點vi,并將其存儲到刪除點集合RV中。
在本實施例中,如圖1中105部分所示,所述步驟S4中給定圖G(V,E),對于每對點vi,vj∈V有且其中A(vi),A(vj)表示vi和vj的相鄰點構成的集合;表示vi的相鄰點集包含在vj的相鄰點集中,則稱vi被包含在vj中,即vi為內含點;所述步驟S4的具體包括以下步驟:
步驟S41:對得到的每一個連通子圖Gc(V,E)計算并存儲vi(i=1,2,...,n)的相鄰點到集合A(vi);
步驟S42:選擇一個未被標記的點判斷所有與不相鄰的點vj,即 是否存在A(vj),(j≠ik),使得如果存在,則從Gc(V,E)中刪除點及其相連邊,并將其存儲到RV;否則標記已判斷完畢;
步驟S43:更新Gc(V,E),返回步驟S43,直到所有的點都被判斷完畢;
遍歷每個點i∈V,判斷它是否被某個與i不相鄰的頂點所包含,如果是,則點i將被刪除,存到刪除點集合RV。
在本實施例中,如圖1中106部分所示,所述步驟S5采用廣度優先搜索BFS方法求解其連通分支,對于不同的連通分支,染色解相互無關,只需獨立求解每個連通分支的染色解。
在本實施例中,如圖1中107部分所示,所述步驟S7中采用的面沖突投影方法用以判別圖樣pi和pj是否沖突的,所述面沖突投影方法的具體實現方式如下:對于圖樣pi(i=1,2,...,n),其沖突區域regi是一個二維圓角矩形,所述圓角矩形的邊界到圖樣pi邊界的距離為mincs,即
regi={(x,y)||(x-xi)2+(y-yi)2<mincs}---(2)]]>
其中坐標(xi,yi)是圖樣pi邊界上的點;所述步驟S7具體包括以下步驟:
步驟S71:對所述步驟S6得到的每一個連通子圖Gc(V,E)所對應的圖樣布局圖,計算所有圖樣pi(i=1,2,...,n)的沖突區域regi;
步驟S72:選擇一個未被標記的圖樣判斷上是否存在一區域使得在 所述區域上有三個或多于三個相鄰圖樣的沖突區域 重疊相交;如果是,則進入所述步驟S73;否則進入所述步驟S74;
步驟S73:判斷圖樣與總共l+1點構成的生成子圖是否為3不可染的;如果是,則標記圖樣為沖突圖樣;否則進入步驟S74;
步驟S74:標記為非沖突圖樣,返回步驟S72,直到所有圖樣被檢查。
在本實施例中,如圖1中111部分所示,所述步驟S9采用非線性0-1整數規劃模型求解點帶權的連通分支子圖的3染色解,用以最小化未染色的點的權值之和,約束條件為有邊相連的兩個點不被分配同一種顏色,用C1,C2,C3分別表示顏色類點集合1,2,3和R4表示未染色點的集合,則可以得到優化模型:
minΣvi&Element;R4wis.t.(vi,vj)&NotElement;E,vi,vj&Element;Ck(k=1,2,3)---(3)]]>
其中wi為點vi的權重。
將優化模型(3)轉化為非線性0-1整數規劃模型:
minΣi&Element;Vwi(1-xi1)(1-xi2)s.t.xi1+xi2+xj1+xj23&ForAll;eij&Element;E-xi1+xi2-xj1+xj21&ForAll;eij&Element;Exi1-xi2+xj1-xj21&ForAll;eij&Element;E(xi1,xj2)&Element;{0,1}×{0,1}&ForAll;i&Element;V---(4)]]>
用分支定界方法求解非線性0-1整數規劃模型(4)可以得到染色解C1,C2,C3,R4。
在本實施例中,如圖1中112部分所示,所述步驟S10引入沖突矩形,圖樣pi上由相鄰圖樣pj造成的沖突矩形,即包含pi∩regj區域的最小外接矩形rtgi←j;所述步驟S10具體包括以下步驟:
步驟S101:在未染色點集R4中選擇一個圖樣pi;
步驟S102:計算由pi的所有相鄰圖樣造成pi上的沖突矩形,將其存儲到pi的沖突矩形集Rtgi;
步驟S103:對pi的沖突矩形集Rtgi中的每個沖突矩形的四條邊,延長這四條邊至圖樣pi的邊界,生成的邊為割邊,將其存儲至割邊集CSEi;
步驟S104:判斷割邊集CSEi中的每條割邊是否同時滿足條件1,條件2以及條件3;如果滿足,則該割邊為候選縫合,將其存儲至候選縫合集CSi;
步驟S101:返回所述步驟S101,直到R4中的所有圖樣pi(i=1,2,...,m)都判斷完畢;
其中所述步驟S104中的條件1,條件2以及條件3分別為:
條件1:圖樣pi被割邊分割后產生的兩個子圖樣pi1和pi2的最小尺寸都大于最小圖樣尺寸minfs;
條件2:割邊不在圖樣pi的拐角處;
條件3:圖樣pi被割邊分割后產生的兩個子圖樣pi1和pi2,pi1和pi2的相鄰圖樣的顏色不多于2種,即pi1和pi2可以被染色且不會產生沖突。
在本實施例中,如圖1中114部分所示,所述步驟S11中回溯方法具體包括以下步驟:
步驟S1101:初始化連通分支G,要回溯的染色解X=(C1,C2,C3,R4);
步驟S1102:取子圖Gm=G/R4;
步驟S1103:用遍歷方法得到Gm的所有合法3染色解;
步驟S1104:從Gm的所有3染色解中取出一個解(C1',C2',C3'),并采用所述步驟S10中的縫插入算法進行插入縫合;
步驟S1105:如果解(C1',C2',C3',R4)滿足R4中的所有非沖突圖樣都能被插入縫合消除沖突,即那么得到回溯解X*=(C1',C2',C3',R4),輸出回溯 解X*;否則,返回到所述步驟S1104;
步驟S1106:用遍歷方法得到G的所有合法解X”=(C1”,C2”,C3”,R4”),其中R4”≠R4;并計算分解成本cost(X”)=|C|+α|S|;
步驟S1101:取最小分解成本的解X”,令X*=X”,輸出回溯解X*。
在本實施例中,如圖1中116部分所示,所述步驟S12對所述步驟S3和步驟S4中刪除的點構成的集RV染色,得到最小成本的顏色;染色順序與所述步驟S3與步驟S4中被刪除的點的刪除順序相反,具體包括以下步驟:
步驟S1201:level=k,其中k為刪除點的總次數;
步驟S1202:對第level次刪除的點集RVlevel中的每個點代表的圖樣pi(1=1,2,...,|RVlevel|),計算其染第k種顏色的成本cost_ck;
步驟S1203:取使得cost_ck最小的顏色作為圖樣pi的顏色;
步驟S1204:level=level-1;
步驟S1205:返回所述步驟S1202,直到level=0。
根據以上方法,可將圖2的布局圖進行分解染色,結果如圖3所示。
以上所述僅為本發明的較佳實施例,凡依本發明申請專利范圍所做的均等變化與修飾,皆應屬本發明的涵蓋范圍。

關 鍵 詞:
基于 分解 成本 最小化 合法化 圖樣 光刻 布局 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:基于分解成本最小化和合法化的三圖樣光刻布局分解方法.pdf
鏈接地址:http://www.rgyfuv.icu/p-6353690.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
山东11选5中奖结果走势图