李興權(quán)，吳莉莉，朱文興

(1. 閩南師范大學數(shù)學與統(tǒng)計學院，福建 漳州 363000; 2. 福州大學離散數(shù)學研究中心，福建 福州 350108)

0 引言

隨著特征之間的間距縮小和節(jié)點數(shù)量的增加，超大規(guī)模集成電路的版圖制造越來越困難[1]. 目前學術(shù)界和工業(yè)界公認的最有前景的制造技術(shù)是嵌段共聚物定向自組裝(directed-self-assembly，DSA)和極端紫外光刻[2]. 其中DSA最適合用于制造分布密集的通孔層[3]. 為了通過DSA對通孔層進行刻印制造，通常需要使用引導槽來輔助形成通孔[4]. 使用一些單孔的引導槽可以來制造稀疏結(jié)構(gòu)的通孔. 但對密集結(jié)構(gòu)，太近的單孔引導槽之間會產(chǎn)生沖突[5]. 為了減少沖突，本研究將一些短距離內(nèi)的通孔放在某個多孔引導槽中組合制造[6]，但是復雜且不規(guī)則形狀的引導槽將會產(chǎn)生更大的重疊成本[7]. 因此，在引導槽分配時，應考慮引導槽的成本. 此外，對于非常密集的通孔層版圖，由于一些沖突錯誤，通過單重圖樣光刻制造的電路版幾乎是不合格的. 因此，本研究考慮多重圖樣光刻的DSA技術(shù)(triple patterning lithography with DSA，TPL-DSA)是一個可靠的選擇. 同樣地，對于TPL-DSA技術(shù)而言，其關(guān)鍵問題是掩模版和引導槽的分配[8-9]. 本研究總結(jié)了不同尺寸的豎直和水平引導槽成本的一般規(guī)則，并構(gòu)建了加權(quán)沖突分組圖，研究一個緊致的整數(shù)線性規(guī)劃模型，接著引入一些有效的不等式剪枝掉一些不良的解進行加速求解.

1 DSA引導槽分配問題

為了用定向自組裝技術(shù)制造通孔，通常需要先采用傳統(tǒng)的光刻技術(shù)刻印出引導槽[3]. 對于稀疏結(jié)構(gòu)，

通孔之間的間距足夠大，通孔可以放在單孔引導槽中制造. 但對于密集的結(jié)構(gòu)，通孔之間的間距太小而導致不能通過單孔引導槽制造，需要將相近的幾個通孔放到某個多孔引導槽制造. 多孔引導槽的類型理論上可以是任何形狀的[8]. 然而，復雜的引導槽可能會引入較大的重疊消除成本，并且預期的通孔可能無法正確制造[7]. 為了得到較好的通孔制造效果，本研究只考慮豎直和水平形狀的引導槽. 對于豎直或水平引導槽，不同孔數(shù)的引導槽具有不同的成本[9]. 本研究總結(jié)了三個關(guān)于豎直和水平引導槽成本的規(guī)則.

規(guī)則1孔越多的引導槽，成本越高；

規(guī)則2k個孔被包含在一個引導槽中，或者k+1個孔被包含在幾個引導槽中，前者的成本要小于后者的成本之和；

規(guī)則3k個孔被包含在一個引導槽中，或者k個孔被包含在幾個引導槽中，前者的成本要大于后者的成本之和.

規(guī)則1是由于具有更多孔的引導槽更難以控制光刻變化； 規(guī)則2是由于后一種情況涉及更多的通孔，并可能產(chǎn)生更多的制造錯誤； 規(guī)則3是由于包含k個孔的一個引導槽比包含k個孔的其他幾個引導槽更難控制光刻變化[8-10].

令dc min為最小沖突間距，dg min為最小分組間距，dg max為最大分組間距，對于上述表示法dg min

給定通孔層版圖，垂直和水平引導槽集，三個掩模版M1，M2，M3，沖突數(shù)與引導槽成本之間的權(quán)重參數(shù)β=0.01. 將所有通孔分配給掩模版和可用的單孔、 多孔引導槽. 其中每個通孔只能分配給三個掩模版中的一個，并且僅分配給一個引導槽，此外一個引導槽中的幾個通孔必須分配到同一掩模版. 該問題的目標是為了最小化|C|+β×T_cost，其中cij∈C表示通孔i和j之間的沖突，|C|是沖突的總數(shù)量，T_cost是使用的引導槽的總成本.

2 TPL-DSA掩模版和引導槽分配的整數(shù)線性規(guī)劃求解

2.1 構(gòu)造沖突分組圖

給定版圖，對于靠太近的一些通孔，需要分配到不同的掩模版中或者組合在一個引導槽中制造. 如果兩個通孔i和j的距離在dg min和dg max之間，并且i和j分布在垂直或水平線上，則組合在一起，并稱其為二元組. 此外，本研究將所有通孔稱為單元組，然后將所有二元組和單元組統(tǒng)稱為多元組. 圖1(a)顯示單元組和二元組. 上面的多元組可以看作圖中的頂點，而在這些頂點之間有一些邊. 本研究定義如下沖突分組圖.

定義1沖突分組圖CGG1(V，Ec，Eg，Eo，Wv，Wv)是無向圖，其中V是頂點集，v∈V是多元組，Ec是沖突邊的集合，Eg是分組邊的集合，Eo是重疊邊的集合.Wv是頂點權(quán)重的集合，Wv是邊權(quán)重的集合.

由分組邊連接的多元組可以組合成引導槽，如圖1(b)所示. 如果多元組i和j彼此重疊，則兩者之間存在重疊邊oeij∈Eo.

圖1 多元組與由多元組組合而成的引導槽Fig.1 Comparison of the costs of different templates

在CGG1中，如果V中兩個多元組i和j之間的距離小于dc min，則存在沖突邊ceij∈Ec. 如果兩個多元組i和j之間的距離(i和j至少有一個是二元組)在dg min和dg max之間，并且i和j在垂直或者水平線中，則在兩者之間存在分組邊geij∈Eg. 顯然，Eg?Ec.

在CGG1中，wiv∈Wv是多元組i的權(quán)重，并且wije∈We是多元組i和j的邊ceij∈Ec的權(quán)重.wiv和wije的權(quán)重規(guī)則分別見公式(1).wiv∈Wv和wije∈We的這些權(quán)重規(guī)則旨在擬合目標函數(shù).

(1)

圖2給出了一個沖突分組圖CGG1的示例. 圖2(a)是具有五個通孔的版圖，其CGG1如圖2(b)所示，這里s1～s5是單元組，對應于通孔c1～c5；d1～d3是二元組，其中d1包括通孔c1和c2，d2包括通孔c2和c3，d3包括通孔c4和c5. 黑線是沖突邊，綠線是分組邊，紅線是重疊邊.

圖2 沖突分組圖Fig.2 Conflict grouping graph

圖3 不同引導槽的成本比較Fig.3 Comparison of the costs of different templates

2.2 整數(shù)線性規(guī)劃模型

為了表示Eo中重疊邊之間的約束，首先通過Eo中的重疊邊獲得推導出CGG1的子圖EDG1(V′，Eo)的邊. 圖2(c)顯示了圖2(b)中CGG1的EDG1(V′，Eo). 然后將找到V′中每個頂點的所有可能的最大團Ct，設S是最大團Ct的集合. 如圖2(c)所示，找到五個最大團C1，C2，…，C5. 必須注意的是，找到圖的最大團是NP困難問題. 幸運的V′中點的數(shù)目和每個頂點的度數(shù)都不大.

令0～1變量xim表示V中被分配給掩模m(m=1，2，3)的頂點i，給出整數(shù)線性規(guī)劃模型P1如下：

(2)

s.t.xim+xjm≤1+cij(?eij∈Ec，m=1，2，3)

(3)

(4)

通過觀察，存在四種類型的組合可以形成不可用的引導槽，如圖4的第一、 三列的四個小圖所示. 將這些組合類型稱為不兼容結(jié)構(gòu)(incompatibility structure，IS). IS通過對邊進行分組，存在至少兩個二元組i和j連接到單元組k，并且在i和j之間沒有沖突邊或分組邊. 如果IS中的所有多元組分配給掩模版，則IS的權(quán)重總和不等于該IS中可用引導槽或沖突的最小總成本. 本研究通過舉例來說明成本的這種差異. 在圖4(a)中，IS的權(quán)重之和為0.03+0.02+0.02+0.03=0.10. 對圖4(a)中的IS，最好的分配結(jié)果是將所有多元組組合成一個T5引導槽，然后分配給掩模版，這時候這個結(jié)構(gòu)的成本等于T5引導槽的成本0.09. 那么IS的權(quán)重之和與其最小總成本之間的差距為0.01. 同樣，圖4(c)，(e)，(g)中的IS權(quán)重之和與其最低總成本之間同樣存在差距.

圖4 四種不兼容結(jié)構(gòu)與三角邊 Fig.4 Four types of incompatible structures and triangle edge

為了消除差距，本研究在這些IS中的多元組中插入三角邊，其定義為：

定義2(三角邊te) 如果存在兩個二元組i和j通過分組邊連接到單元組k，即eik∈Eg，ejk∈Eg，并且如果eij?Ec，則將eij添加到圖中并稱為三角邊. 設Et是三角邊的集合.

在圖4中，有四種類型的不兼容結(jié)構(gòu)(IS)：

1) “—”形，{eik，ejk}?Eg和{eij}?Et，并且eij的權(quán)重設置為wije=-0.01, 如圖4(b)所示;

2) “L”形，{eik，ejk}?Eg和{eij}?Et，eij的權(quán)重設置為wije=0.98，如圖4(d)所示;

3) “T”形，{eik，ejk，elk}?Eg和{eij，ejl，eil}?Et，eij和ejl的權(quán)重設置為0.98，eil的權(quán)重設置為-0.01，如圖4(f)所示;

4) “+”形，{eik，ejk，elk，ehk}?Eg和{eij，ejl，elh，ehi，eil，ejh}?Et，eij，ejl，elh和ehi的權(quán)重設置為0.98，eil和ejh的權(quán)重設置為-0.01，如圖4(h)所示. 三角邊的權(quán)重設置的詳細說明如下所示.

對于“—”形狀結(jié)構(gòu)，如果將三個多元組i，j和k分配給掩模版，則最佳分配是將該IS中的所有多元組s分配給T5引導槽，并且成本為0.09. IS中多元組的權(quán)重之和與IS的最小總成本之間的差距為0.01. 因此，eij的權(quán)重設置為-0.01(下同). 為了消除這種差距，對于“—”形狀I(lǐng)S的多元組i，j和k，為P1添加了一個新的約束如下：

xim+xkm+xjm≤2+cij(m=1，2，3)

(5)

約束條件(5)用于限制，若多元組i，j和k分配給同一個掩模版，則三角邊eij∈Et的沖突變量滿足cij=1.

“L”形結(jié)構(gòu)中多元組i，j和k分配給同一個掩模版，最佳分配是該IS中的多元組s1和d1被分配給T3引導槽，并在s1和d2之間產(chǎn)生沖突，總成本為1.08. 因此，三角邊eij的權(quán)重設置為0.98，新增約束：

xim+xkm+xjm≤2+cij(m=1，2，3)

(6)

“T”形結(jié)構(gòu)中通孔i，j，l和k分配給同一個掩模版，最佳分配是將該IS中的多元組d1，s1和d3分配給T5引導槽，并在s1和d2之間產(chǎn)生沖突，總成本是1.13. 因此，eij和ejl的權(quán)重設置為0.98，新增約束：

xim+xkm+xjm≤2+cij+cjl(m=1，2，3);xjm+xkm+xlm≤2+cij+cjl(m=1，2，3)

(7)

約束條件(7)用于限制，如果三個通孔i，j和k(或j，l和k)或四個通孔分配給同一個掩模版，則三角邊eij和ejl中至少有一個沖突變量cij或cjl等于1.

“+”形狀結(jié)構(gòu)中通孔i，j，l，h和k分配給同一個掩模版，最佳分配之一是該IS中的多元組d1，s1和d3被分配給T5引導槽和生成的兩個沖突在s1和d2之間以及s1和d4之間，總成本是2.06. 新增約束：

(8)

約束條件(8)用于限制，如果“L”形IS中的三個通孔或“T”形IS中的四個通孔分配給相同的掩模版，則至少有一個三角邊的沖突變量等于1. 如果將“+”形IS中的五個通孔分配給同一個掩模版，則三角邊eij，ejl，elh，ehi的沖突變量cij，cjl，clh，chi中至少有兩個等于1.

接著將四種類型的IS的約束添加到P1中，那么IS中多元組權(quán)重之和與其最小總成本之間的差距的任何組合都為0. 通過求解圖2(b)中CGG1上的整數(shù)線性規(guī)劃P1，可以得到P1的最優(yōu)解，如圖2(d)所示. 這個結(jié)果沒有產(chǎn)生沖突，只產(chǎn)生一個T2孔引導槽成本，該結(jié)果的目標函數(shù)值是：

(9)

根據(jù)P1的結(jié)果可以得到最終的分配結(jié)果. 其中c1～c3由T1引導槽制造，c4～c5被分到同一個T2引導槽制造；c1，c3被分到掩模版M3中制造，c2被分到掩模版M2中制造，c4～c5被分到掩模版M1中制造.

3 實驗結(jié)果與分析

用于解決TPL-DSA掩模版和引導槽分配的整數(shù)線性規(guī)劃方法用C++編程，并在具有2.4 GHz CPU，4 GB內(nèi)存和Linux操作系統(tǒng)的個人計算機上運行. 在文獻[8]提供的基準測試中測試了本研究的方法. 通孔寬度和最小沖突間距縮放到10 nm，以反映先進技術(shù)節(jié)點的間距. 最小沖突間隔dc設置為50 nm，最小分組間距dg min和最大分組間距dg max分別設置為10 nm和40 nm，增加dc與縮小節(jié)點大小具有相同的效果. 本研究的整數(shù)線性規(guī)劃模型采用商業(yè)優(yōu)化求解器CPLEX[11]中的分枝定界方法求解. 但由于本研究的問題約束多，可以較快地得到剪枝條件，故而可以快速地終止計算； 另外整數(shù)規(guī)劃模型是根據(jù)每個聯(lián)通分支建立的，不同聯(lián)通分支之間是獨立求解的.

表1中列出了本研究方法和ASP-DAC16中方法在所有測試實例的實驗比較結(jié)果. 列“#V”中的數(shù)據(jù)是每個測試例子中的通孔點數(shù)量. 列“|C|”是得到實驗結(jié)果的沖突總數(shù). 列“T2”是得到實驗結(jié)果的T2引導槽的總數(shù)目. 列“T3”是得到實驗結(jié)果的T3引導槽的總數(shù)目. 列“T_cost”是得到實驗結(jié)果的引導槽的總成本. 列“cost”是得到實驗結(jié)果的沖突和引導槽的總成本. 列“tCPU”是得到實驗結(jié)果所花的運行時間.

從表1中的行“比例”可以看出 “ASP-DAC16”的沖突總數(shù)是本研究的方法的42倍，而且本研究的方法所得到的沖突基本是0，因為其整數(shù)規(guī)劃方法得到的沖突數(shù)目是最優(yōu). 另外，這兩個方法得到的引導槽的總成本基本相同. 最終的總成本“cost”，本研究的結(jié)果與“ASP-DAC16”相比，減少了78%. 運行時間上，整數(shù)規(guī)劃方法是“ASP-DAC’16”的3倍. 這些比較說明整數(shù)規(guī)劃方法可以得到更優(yōu)的TPL-DSA掩模版和引導槽分配結(jié)果.

表1 實驗結(jié)果比較

4 結(jié)語

本研究考慮TPL-DSA的通孔層的掩模版和引導槽分配問題. 首先，給定通孔層版圖構(gòu)造帶權(quán)沖突分組圖. 然后，根據(jù)沖突分組圖為該問題構(gòu)建了一個整數(shù)線性規(guī)劃問題. 為了獲得更好的結(jié)果，在加權(quán)沖突分組圖中引入了三角邊，從而在離散松弛問題中引入了一些有效的不等式. 最后的實驗結(jié)果表明，所得到的比當前最好的方法有較大的提高.