魏晗一，陸偉成

（復(fù)旦大學(xué) 專用集成電路與系統(tǒng)國家重點實驗室，上海201203）

隨著半導(dǎo)體技術(shù)的迅速發(fā)展，集成電路制造工藝已逼近22nm，并邁向更小尺寸和更高集成度.現(xiàn)時版圖中的圖形尺寸和圖形間距，相對于現(xiàn)有工藝的光刻波長顯得過小，光刻時光波將發(fā)生衍射，導(dǎo)致光刻后圖形產(chǎn)生較大失真.由于以極端遠紫外線光刻技術(shù)（extreme ultraviolet，EUV）為代表的下一代光刻工藝無論是在可應(yīng)用的技術(shù)節(jié)點方面還是在量產(chǎn)能力方面都還未能滿足業(yè)界需求［1］，因此現(xiàn)有的193nm光刻工藝仍將被繼續(xù)使用［2］.現(xiàn)在，雙成像光刻（double patterning，DP）技術(shù)是解決光刻后的圖形畸變問題和提高光刻準確度的最有效的解決方案之一［3］.雙成像光刻技術(shù)將原版圖合理地劃分為2個子版圖，使得每1個子版圖中的圖形間距（pitch）相當于原版圖中圖形間距的2倍，圖形密度相當于原版圖密度的通過分別使用2個掩模版進行2次光刻，將大幅度提高光刻后圖形的準確度［4］.在雙成像光刻技術(shù)中，需要先進行版圖分解（layout fracturing），即將版圖中的多邊形（polygon）圖形分解為更簡單的圖形的集合.在1個版圖中，多邊形圖形大多數(shù)是直角多邊形（rectilinear polygon），即所有邊都是水平或豎直方向，并與坐標軸平行（axis－parallel）的多邊形，如圖1所示；也有少數(shù)多邊形包含部分斜邊和斜角，在本文中將它們稱為帶斜角多邊形（polygon with slant angles），如圖2所示.然后對分解后的圖形進行顏色分配（coloring）.稱間距小于給定的最小間距的兩個圖形之間產(chǎn)生了沖突（conflict），如圖1中的圈中部分所示，需要給它們分配不同的顏色，表示它們將被分配在不同的子版圖［5］中.版圖分解工作是必須的，因為版圖中的圖形會存在自相沖突（self－conflict）的情況，如圖1所示；另外，版圖分解通過將版圖中復(fù)雜的多邊形分解為更簡單的圖形的集合，如矩形（rectangle）和不規(guī)則四邊形（trapezoid）等，將簡化后續(xù)的顏色分配工作.在顏色分配結(jié)束后，一些被分配為相同顏色的圖形可以重新被合并為多邊形，減少圖形數(shù)目從而簡化版圖，同時減少切線（stitch）數(shù)目從而降低覆蓋誤差（overlay error）和線端縮短（line－end shortening）所導(dǎo)致的額外制造成本［6］.在超大規(guī)模集成電路（Very Large Scale Integration，VLSI）領(lǐng)域，有許多研究關(guān)注將多邊形分解為更簡單的圖形的集合，如在帶障礙的時鐘樹中，通過將版圖中的直角多邊形障礙分解成矩形，在布線時只需考慮簡單的矩形障礙，從而減小了布線算法的復(fù)雜度［7］.直角多邊形分解算法根據(jù)是否允許分解后的圖形間彼此存在交疊（overlap）部分而分為覆蓋（cover）算法和切割（partition）算法兩類.在前人的研究中，主要有兩類分解目標，一類是使分解后切線總長度最短[8]，僅在切割算法中出現(xiàn)；另一類是使分解后矩形總數(shù)最少[9，10]，在覆蓋算法和切割算法中均存在.

1種簡單直觀并且被業(yè)界廣泛采用的版圖分解算法是單方向多邊形切割算法[11]，該算法應(yīng)用到雙成像光刻技術(shù)中時會產(chǎn)生2個問題，如圖3所示.

1）版圖在分解后產(chǎn)生寬度小于版圖工藝尺寸的圖形，稱之為“薄片”（sliver）.如果經(jīng)過顏色分配和合并工作后的圖形依然屬于薄片，會導(dǎo)致重要尺寸誤差（critical dimension error），給掩膜和光刻帶來很大挑戰(zhàn)，如圖3中圈中所示.

2）在經(jīng)過顏色分配和合并后，版圖中仍舊存在大量沖突，有關(guān)這1點將在下文通過實驗具體說明.

顯然地，將單方向多邊形切割算法應(yīng)用在雙成像光刻技術(shù)并不合理.

文獻[12]提出了1種使用射線－線段選擇（ray－segment selection）的版圖分解算法，近似最優(yōu)地使分解后薄片總數(shù)最少，但仍舊未消除薄片.

如前文所述，現(xiàn)有的版圖分解算法的目標有分解后切線總長度最短、分解后矩形總數(shù)最少和分解后薄片總數(shù)最少，然而，現(xiàn)有的版圖分解算法在雙成像光刻技術(shù)中不適用，有關(guān)這1點將在下1部分中具體說明.更為重要的是，分解后的圖形中不存在工藝無法接受的薄片是能夠正確進行雙成像光刻的前提.現(xiàn)有的版圖分解算法中，切割算法在分解后往往會產(chǎn)生薄片.

另外，文獻[12]不允許分解后的圖形間存在交疊，認為交疊部分在光刻時會發(fā)生過度曝光.但是文獻[13]指出，交疊在雙成像光刻中是可以接受的，并且如果分解后的圖形間有交疊部分，能夠解決光刻時由于覆蓋誤差引起的圖形斷開問題.文獻[14]進一步通過實驗證明足夠的交疊部分能夠消除兩次光刻的覆蓋誤差所導(dǎo)致的圖形失真的影響，并且當掩膜版同時沿x和y2個方向發(fā)生偏移（mask bias）時交疊能夠起到穩(wěn)定圖形寬度的作用.可見分解后的圖形間存在交疊是可以接受的，并且將有利于雙成像光刻技術(shù)，而目前用于雙成像光刻中的版圖分解算法并沒有引入交疊.

本文提出1種新的版圖分解算法，用于雙成像光刻技術(shù)，實現(xiàn)分解后的圖形不存在薄片并解決光刻時由于覆蓋誤差引起的圖形斷開問題的前提，以減少顏色分配后的沖突總數(shù)為目標，主要通過在可接受的時間復(fù)雜度下減短分解后切線總長度，同時引入交疊.其中引入交疊將帶來的優(yōu)勢是:1）消除薄片的產(chǎn)生；2）解決光刻時由于覆蓋誤差引起的圖形斷開問題；3）減少分解后的矩形數(shù)目，從而既能夠減少沖突總數(shù)，又能夠簡化版圖.

1 與現(xiàn)有算法比較

接下來將通過使用本文算法和現(xiàn)有的各種算法分別對版圖中常見的一些多邊形例子進行分解的情況進行比較，說明本文的版圖分解算法優(yōu)勝的方面.在下文的圖中，虛線表示切線，陰影表示分解后圖形間的交疊部分.顯然地，和切割算法相比，本文算法通過引入交疊，在絕大部分情況中使分解后相連（connect）的圖形在相連處有互相交疊的部分，首先能夠解決光刻時由于覆蓋誤差引起的圖形斷開問題.

圖4顯示了使用本文算法和另兩種現(xiàn)有算法對同1個多邊形分解后的情況.可見在這個例子中，圖4（a）單方向多邊形切割算法[11]和圖4（b）分解后切線總長度最短的多邊形切割算法[8]都產(chǎn)生了光刻工藝所無法接受的薄片，如圖4圈中所示，并且分解后矩形總數(shù)較多，將會增加沖突數(shù)目和版圖制造成本；而圖4（c）本文算法通過引入交疊:1）消除薄片的產(chǎn)生，確保版圖符合光刻工藝要求；2）盡量減短分解后切線總長度，從而減少沖突數(shù)目；3）實現(xiàn)矩形總數(shù)最少，在減少沖突數(shù)目的同時也簡化了版圖，降低制造成本.

在圖5多邊形分解的例子中，圖5（a）分解后矩形總數(shù)最少的多邊形切割算法[10]將產(chǎn)生較長的切線和“窄長”（narrow）的矩形，窄長矩形在進行后續(xù)的顏色分配工作時會導(dǎo)致產(chǎn)生更多的沖突，并且窄長矩形往往也是薄片，如圖5（a）圈中所示；而圖5（b）本文算法雖然產(chǎn)生更多數(shù)目的矩形，但是消除了窄長矩形（薄片）的產(chǎn)生，大大減短了切線長度，從而減少沖突數(shù)目.

如圖6的例子所示，圖6（a）分解后矩形總數(shù)最少的多邊形覆蓋算法大多數(shù)允許分解后有交疊部分的矩形之間互相“穿透”（piercing）[9]，不僅產(chǎn)生較長的切線總長度，并且由于交疊部分太大，產(chǎn)生的矩形尺寸很大，在進行顏色分配時會產(chǎn)生更多的沖突，更為重要的是，當交疊部分太大時，將原版圖劃分為2個子版圖并沒有有效地增加圖形間距和降低版圖密度，顯然不適用于雙成像光刻技術(shù)；而圖6（b）本文算法分解后切線總長度較短，并且大大減少了分解后圖形間交疊部分的面積，從而減少沖突數(shù)目，更適用于雙成像光刻.

圖4 對1個多邊形的分解（Ⅰ）Fig.4 Fracture of a polygon（Ⅰ）

圖7是使用本文算法和另2種現(xiàn)有算法對同1個多邊形進行分解的情況.圖7（a）是文獻[15]提出的不允許交疊的矩形之間互相穿透的多邊形覆蓋算法，以分解后矩形總數(shù)最少為目標，可以看作是在覆蓋算法和切割算法之間的折中.但是在這個例子中可見，即使不允許穿透，它依然產(chǎn)生較長的切線總長度和較大尺寸的矩形，將會增加顏色分配時的沖突數(shù)目，交疊部分尺寸也依然很大；為了

在分解時不產(chǎn)生薄片，圖7（b）顯示的文獻[12]提出的減少分解后薄片數(shù)目的多邊形切割算法通過添加輔助線（auxiliary ray）幫助分解，也因此產(chǎn)生較多數(shù)目的矩形和較長的切線總長度；圖7（c）中的本文算法引入交疊，因而可以在切線總長度較短的地方進行分解而不產(chǎn)生薄片，如圖7（c）圈中所示，同時產(chǎn)生較少的矩形，從而減少沖突數(shù)目和版圖制造成本.

圖7 對1個多邊形的分解（Ⅳ）Fig.7 Fracture of a polygon（Ⅳ）

綜合上述比較可知，現(xiàn)有的版圖分解算法應(yīng)用在雙成像光刻時將產(chǎn)生的問題是:切割算法在光刻時都會由于覆蓋誤差而發(fā)生圖形斷開；其中單方向多邊形切割算法會產(chǎn)生薄片，并且會產(chǎn)生較多數(shù)目的矩形和較長的切線，增加沖突數(shù)目和版圖制造成本；分解后矩形總數(shù)最少的多邊形切割算法會產(chǎn)生薄片，并且在一些情況下會產(chǎn)生較長的切線和窄長的矩形，增加沖突數(shù)目；分解后切線總長度最短的多邊形切割算法會產(chǎn)生薄片，并且在一些情況下產(chǎn)生較多數(shù)目的矩形，增加沖突數(shù)目和版圖制造成本；分解后矩形總數(shù)最少的多邊形覆蓋算法在一些情況下會產(chǎn)生較長的切線和較大尺寸的矩形，增加沖突數(shù)目，較大的交疊部分也降低了雙成像光刻的有效性.因此，它們都不適用于雙成像光刻.本文算法消除了薄片的產(chǎn)生，解決光刻時由于覆蓋誤差引起的圖形斷開問題，在減短切線長度的同時減少矩形數(shù)目，從而減少沖突總數(shù)和版圖制造成本.

2 算 法

本文的版圖分解算法能夠?qū)Π鎴D中的直角多邊形和帶斜角多邊形進行分解.由于版圖中的圖形基本是簡單多邊形（simple polygon），本文算法也僅考慮簡單多邊形.版圖中的直角多邊形的所有邊都是與坐標軸平行的直邊，所有內(nèi)角都是直角（90°或270°）；帶斜角多邊形和直角多邊形相比，包含了部分斜邊和斜角，斜邊即與坐標軸不平行的邊.其中，根據(jù)版圖中圖形的特點，對本文考慮的帶斜角多邊形的形狀提出以下2個限制:

1）2條斜邊不相鄰，即每條斜邊的相鄰邊都是直邊；2）斜角不包括銳角，即斜角都是鈍角或優(yōu)角.

圖8顯示了帶斜角多邊形中被這2個限制所排除的情況:2條斜邊相鄰，或斜角是銳角.圖中使用頂點和與之相連的邊表示帶斜角多邊形的一部分.在邊一側(cè)的陰影表明位于多邊形內(nèi)部.邊使用有向線段表示，因為本文算法假定多邊形在分解前已經(jīng)經(jīng)過一種預(yù)處理，使得遍歷代表多邊形的頂點點集時，所得到的有向閉環(huán)是逆時針方向.在本文接下來的部分中將多次使用類似圖8的表示方法.

本文的版圖分解算法將直角多邊形分解為矩形，將帶斜角多邊形分解為矩形或所有內(nèi)角都是直角或鈍角的多邊形.由于在本文算法中，直角多邊形可以看作帶斜角多邊形的特例，所以接下來將主要針對帶斜角多邊形介紹算法，對直角多邊形使用相同的算法處理.

在帶斜角多邊形中，所有內(nèi)角都是鈍角、90°直角或優(yōu)角.顯然地，需要在優(yōu)角位置處進行分解.本文算法所使用的名詞定義如圖9所示.當前需要分解的優(yōu)角稱為當前優(yōu)角，記作a，a的頂點稱為當前點，記作N.在當前優(yōu)角a（當前點N）處進行分解時，需要尋找多邊形中的另1條邊來參考產(chǎn)生切線，將所找到的這條邊稱為參考邊（reference segment），記作r.如果把當前點N作為原點，使用版圖的坐標方向建立1個直角坐標系，優(yōu)角a的2條邊不可能位于的區(qū)域是1個象限加上坐標軸的2個半軸，把表示這個區(qū)域的點集稱為參考域（reference domain）（不包括當前點N），記作D.在圖9中參考域D即第一象限加上x軸和y軸的正半軸，用以2條射線為邊界的陰影表示，和邊一側(cè)表示多邊形內(nèi)部區(qū)域的陰影含義不同.為了與表示多邊形的邊的直線段相區(qū)別，將兩條射線用虛線表示.本文算法所提到的邊和線，在涉及集合運算時都視為包含其上所有點的點集.在本文算法中，限定所找到的參考邊和所作的切線都只能是與坐標軸平行的直邊（線）.

根據(jù)參考域D所包含的象限不同，可以把優(yōu)角a的位置分為4種情況.由于本文算法中對這4種情況下的分解過程極其相似，所以下文僅針對參考域D包含第一象限的情況，即如圖9所示的情況進行描述，其他3種情況的分解可以通過類比得到.分解的基本原理是在優(yōu)角位置處產(chǎn)生切線，將其分解為2個角，相應(yīng)地將當前的多邊形分解為2個多邊形.由于切線只能是與坐標軸平行的直線，而優(yōu)角的2條邊里必有1條是直邊，因此每次分解相當于使優(yōu)角減去90°或180°，直至將所有優(yōu)角都分解為鈍角、90°直角、平角的組合時，分解完畢.根據(jù)優(yōu)角a的角度范圍，可以將優(yōu)角a的形狀分為3種情況:180°＜a＜270°，a＝270°，270°＜a＜360°，如圖10所示.其中（a），（c）只顯示了優(yōu)角a有1條水平方向的直邊的情況，省略了有1條豎直方向直邊的情況.

圖8 在帶斜角多邊形中被2個限制所排除的情況Fig.8 Conditions excluded by two limitations in polygons with slant angles

圖10的優(yōu)角a形狀的3種情況中，圖10（a）由于帶斜角多邊形形狀限制2），切線只能是豎直方向（如果a有1條豎直方向直邊，則切線只能是水平方向），分解后a＝a1＋a2，其中a1＝90°，90°＜a2＜180°，1次分解完畢；圖10（b）切線可以是豎直方向或水平方向，分解后a＝a1＋a2，其中a1＝90°，a2＝180°，也是1次分解完畢；圖10（c）在分解時則又會出現(xiàn)2種情況，見圖11.在圖11（a）中，切線為水平方向，分解后a＝a1＋a2，其中a1＝180°，90°＜a2＜180°，1次分解完畢；圖11（b）中，切線為豎直方向，分解后a＝a1＋a2，其中a1＝90°，180°＜a2＜270°，a2仍是優(yōu)角，需要繼續(xù)對a2進行分解，即對原優(yōu)角a進行第二次分解.在下文中可知，由于在當前優(yōu)角a和參考邊r位置關(guān)系的7種情況中大多數(shù)都將引入交疊，在當前優(yōu)角a滿足270°＜a＜360°時，在進行1次分解后往往產(chǎn)生的2個多邊形中有1個仍舊存在優(yōu)角，需要進行第二次分解，類似圖11（b）的情況.顯然地，a有1條豎直方向直邊的情況可以通過類比得到.

在優(yōu)角a處產(chǎn)生切線時，需要在多邊形中尋找參考邊.記多邊形中和參考域D有交集的直邊的集合為R，多邊形的邊的集合記為P，則R＝｛x｜x∈P，x是直邊且x∩D≠?｝.對集合R中的每一條邊m，考察當前點N和邊m之間的分解距離（fracture distance），記作d或d（N，m）.如圖12所示，分解距離定義如下:

記邊m所在直線為l，如果N?l，由當前點N向邊l作垂線，交于垂點A.

1）如果A∈m，垂點A在邊m內(nèi)，則當前點N和邊m的分解距離d（N，m）為點N和點A之間的距離，即點N和點A的縱坐標或橫坐標的差的絕對值，d（N，m）＝dy＝｜yN－yA｜或d（N，m）＝dx＝｜xN－xA｜.

2）如果A?m，垂點A在邊m外，記M為邊m的兩個頂點中離垂點A距離較近的那個頂點，當前點N和邊m的分解距離d（N，m）為點N和點M之間橫坐標之差的絕對值和縱坐標之差的絕對值中的較大值，d（N，m）＝max（dx，dy）＝max（｜xN－xM｜，｜yN－yM｜）.

如果N∈l，當前點N在邊m所在直線內(nèi)，記M為邊m的兩個頂點中離當前點N距離較近的那個頂點，當前點N和邊m的分解距離d（N，m）為點N和點M之間的距離，（c）中即點N和點M的縱坐標或橫坐標的差的絕對值，d（N，m）＝dy＝｜yN－yM｜或d（N，m）＝dx＝｜xN－xM｜.

選取集合R中和當前點N分解距離最短的邊為參考邊r，即r滿足?m∈R，d（N，r）＝min（d（N，m）），其中r∈R.然后根據(jù)當前優(yōu)角a和參考邊r的位置關(guān)系進行分解.根據(jù)版圖中圖形特點和本文算法的名詞定義，可以將當前優(yōu)角a和參考邊r的所有可能的位置關(guān)系歸納為7種情況.圖13針對參考域D包含第一象限、當前優(yōu)角a有1條水平方向的直邊且270°＜a＜360°顯示了當前優(yōu)角a和參考邊r位置關(guān)系的7種情況.為方便顯示，圖13中當前優(yōu)角a未具體標明，可以通過當前點N和標明了多邊形內(nèi)部區(qū)域的a的兩條邊得到.同前文一致，虛線表示切線，陰影表示分解后圖形間的交疊部分.因為在每次分解時，都確保若遍歷這1次分解后所產(chǎn)生的2個多邊形的點集，所得到的有向閉環(huán)也是逆時針方向，所以使用有向線段表示切線，這將幫助解釋在優(yōu)角位置處的分解是如何產(chǎn)生2個多邊形的.為簡單起見，和原多邊形中的頂點相區(qū)別，圖13中因產(chǎn)生切線而新增的頂點未具體標明.特別地，如果滿足參考邊定義的邊r有多條，只需選取其中1條.圖13（c）～（g）中，當前優(yōu)角a需要和參考邊r及其鄰邊所組成的另一個優(yōu)角一起進行分解.另一個優(yōu)角的2條邊都被標明r，表示這兩條邊中任一條直邊都可以被選為參考邊.

在圖13除去（e）以外的所有情況中，首先在當前點N和參考邊r之間根據(jù)圖12（a），（b）所示的分解距離的概念作出相應(yīng)的切線，稱為主切線.主切線將原多邊形在當前優(yōu)角處切割為2個多邊形.然后，將其中1個多邊形在主切線處增加1個以主切線為1條邊的正方形部分，相應(yīng)地增加切線，使兩個多邊形之間產(chǎn)生交疊.為不破壞原圖形形狀，正方形只在當前優(yōu)角的參考域D內(nèi)產(chǎn)生.在圖13（b），圖13（d），圖13（f），圖13（g）中，當前優(yōu)角需要和另一個優(yōu)角一起分解，要求這個正方形也必須在那個優(yōu)角的參考域D′內(nèi).其中在圖13（b），圖13（d）中能夠作出同時滿足這2個要求的正方形，因此正常引入交疊；而在圖13（f），圖13（g）中無法作出這樣的正方形，因此不引入交疊.在圖13（e）中，同樣根據(jù)圖12（c）所示作出計算分解距離時所需要的邊.因為有兩種不同的作法，所以將得到四條切線.這四條切線本身就在引入交疊的條件下一起分解了當前優(yōu)角和由參考邊及其鄰邊所組成的另一個優(yōu)角，不需要作額外的切線產(chǎn)生交疊.

在當前優(yōu)角和參考邊r位置關(guān)系的7種情況下的具體分解方法，體現(xiàn)本文算法所具備的優(yōu)勢是:

1）薄片是版圖分解后所產(chǎn)生的寬度小于工藝尺寸的圖形.對于版圖中主要的直角多邊形，考察圖13（a）所示情況.在當前270°角處分解產(chǎn)生的兩個多邊形中，顯然地，根據(jù)參考邊的定義，上方不包含增加的交疊正方形的那個多邊形的寬度必然不小于交疊正方形的邊長，而由分解距離定義可知，交疊正方形的邊長不小于版圖工藝尺寸，因此上方多邊形不是薄片.類似地，下方包含交疊正方形部分的多邊形的寬度也大于交疊正方形邊長，因此也不是薄片.圖7（b）是包含圖13（a）情況的一個具體例子，由圖7可見如果不引入交疊或如文獻[12]添加輔助線進行切割，必然會產(chǎn)生薄片，而按照本文算法增加一個正方形交疊部分，會消除薄片的產(chǎn)生.圖13（b）～（d）情況類似.在圖13（e）情況中，同樣因為分解后的兩個多邊形均包含交疊正方形，因此都不是薄片，分解后消除薄片的產(chǎn)生.在圖13（f），圖13（g）情況中，因為無法引入交疊，因此會產(chǎn)生薄片，但是因為在版圖的多邊形中存在的比例極低，對本文算法的應(yīng)用造成的影響極小.對于版圖中少數(shù)的帶斜角多邊形，由于在尋找參考邊時未考慮斜邊，因此在圖13所有情況中，切線都有可能會與多邊形中的斜邊（不包括當前優(yōu)角和一起分解的另一個優(yōu)角中的斜邊）相交從而改變原多邊形形狀.如果要解決這個問題，可以通過在產(chǎn)生切線前對切線和多邊形中的斜邊進行關(guān)系檢測（相應(yīng)地增加算法時間復(fù)雜度），如果在圖13（a）～（d）情況中被檢測出發(fā)生相交的是除去主切線外的其他切線，則修改交疊部分大小，使分解后不改變原多邊形形狀；如果被檢測出發(fā)生相交的是圖13（a）～（d）情況中的主切線或圖13（e）～（g）情況中的切線，則不進行分解.由于帶斜角多邊形在版圖中比例很小，因此這個問題對本文算法的應(yīng)用造成的影響也很小.并且，通過下文的實驗可知，使用本文算法對帶斜角多邊形進行分解時，對原圖形進行的這種改變往往也有利于提高原圖形在光刻后的準確性.

圖13 當前優(yōu)角和參考邊r位置關(guān)系的七種情況Fig.13 Seven conditions of location relationship between current reflex angle and reference segment r

2）分解時，在當前優(yōu)角和參考邊r位置關(guān)系7種情況中的五種中引入交疊，交疊部分是邊長為此最短分解距離的正方形.因為交疊正方形的邊長不小于版圖工藝尺寸，因此分解后的圖形間的交疊部分足夠大，在光刻時因覆蓋誤差引起圖形尺寸和位置變化時能夠保持原圖形的完整性，解決圖形斷開問題.另外2種情況圖13（f）和圖13（g）中雖然分解時不引入交疊，但是在版圖的多邊形中存在的比例極低，對本文算法的應(yīng)用造成的影響極小.

3）在所考察的集合中選取和當前點N分解距離最短的邊為參考邊r，并作出長度為此最短分解距離的切線進行分解，通過減少分解后切線總長度，使交疊部分足夠小，從而減少沖突總數(shù)，提高雙成像光刻的有效性.

4）由于版圖中的圖形大多數(shù)是直角多邊形，當圖13中的優(yōu)角都是270°直角時，在除去圖13（e）以外的6種情況中，是否引入交疊不影響分解后的矩形數(shù)目.在圖13（e）情況中，多邊形切割算法無法對這2個270°直角一起分解，因此分解后至少產(chǎn)生3個矩形，由圖4可見；而本文算法引入交疊分解后產(chǎn)生2個矩形，減少分解后的矩形數(shù)目.在帶斜角多邊形中，當前優(yōu)角a滿足180°＜a＜270°時（見圖10（a）），圖13的7種情況都是1次分解完畢，分解后矩形數(shù)目和a＝270°時相同，即和切割算法相同.當前優(yōu)角a滿足270°＜a＜360°時（見圖10（c）），圖13中除（f）外的6種情況都需要2次分解，將會增加分解后矩形數(shù)目.但是由于滿足270°＜a＜360°的優(yōu)角在版圖的多邊形中存在的比例極低，總體上，本文算法通過引入交疊，將減少分解后矩形數(shù)目，從而既能夠減少沖突總數(shù)，又能夠簡化版圖.

本文版圖分解算法的流程表示如下:

輸入:經(jīng)過預(yù)處理的代表多邊形的頂點點集V.

輸出:代表分解后的圖形的集合的頂點點集V和Vadd.

步驟1:遍歷V中每個頂點；

步驟2:如果找到1個優(yōu)角a（及當前點N）；

步驟3:對于當前優(yōu)角a，遍歷V獲取集合R，并從R中找到參考邊r；

步驟4:根據(jù)當前優(yōu)角a和參考邊r位置關(guān)系情況進行分解；

步驟5:如果分解后產(chǎn)生的多邊形在當前點N處的內(nèi)角是優(yōu)角，則繼續(xù)分解；

步驟6:回到步驟1繼續(xù)遍歷.

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

本文的版圖分解算法已用C＋＋語言在Linux平臺下實現(xiàn).多邊形由單鏈表數(shù)據(jù)結(jié)構(gòu)實現(xiàn).所有的實驗結(jié)果都是在Linux平臺下的Dell 2600PC機上運行得出的，Dell 2600PC機具有3.0GHz的XEON 3.0CPU和4GB內(nèi)存空間.

本文算法的時間復(fù)雜度是O（n2）.圖14為1個實際的版圖中多邊形數(shù)目和單個多邊形頂點數(shù)目的分布圖.由圖14中可見版圖中絕大多數(shù)多邊形的頂點數(shù)目小于18，因此在VLSI版圖處理中本文算法的計算速度是可以接受的.

首先使用由直角多邊形隨機生成算法[16]生成的直角多邊形例子和手工生成的帶斜角多邊形例子對本文算法的功能進行驗證.通過輸入大量的隨機生成的頂點數(shù)不同的直角多邊形例子和多個手工生成的帶斜角多邊形例子，結(jié)果顯示程序都能正確分解.圖15顯示了程序?qū)?個有1 000個頂點的直角多邊形的分解結(jié)果.圖15中分解后的圖形使用帶邊框的多邊形表示，分解后的圖形間不交疊的部分顯示為淺色，交疊的部分顯示為深色，所有有色區(qū)域的包絡(luò)即為原多邊形形狀.下文的實驗結(jié)果也使用類似的表示方法.由圖15可見程序正確地分解了復(fù)雜的直角多邊形例子.

圖14 版圖中多邊形數(shù)目±單個多邊形頂點數(shù)目分布圖Fig.14 Distribution of number of polygons－number of vertices per±polygon in layout

然后對實際版圖的部分進行分解從而驗證本文算法的功能.圖16，圖17分別為程序?qū)?個22nm工藝版圖的一部分和1個0.18μm工藝版圖的一部分進行分解的結(jié)果.由圖16可見本文算法能夠?qū)Π鎴D中的直角多邊形進行正確地分解.在圖17中，由于前文所述的原因，切線與多邊形中的斜邊相交，導(dǎo)致分解后的圖形會有超出原多邊形的部分，改變了原多邊形的形狀.但是，由于在光刻后，因為光學(xué)鄰近效應(yīng)（optical proximity effect，OPE）的影響，會發(fā)生拐角圓滑（corner rounding）現(xiàn)象，尖銳部分被“磨平”[13]，即原多邊形中的90°直角和鈍角位置處在光刻后邊界會內(nèi)縮，因此在多邊形中的90°直角和鈍角位置處增加一些超出的部分將抵消光刻的失真影響，增加光刻的準確性.在圖17中可見，對于版圖中的斜角多邊形，大部分情況下，本文算法分解后所得到的圖形在超出原多邊形的部分所在的位置處，原多邊形的內(nèi)角為鈍角，將有利于版圖光刻.并且大部分情況下超出部分足夠小，不會對版圖功能帶來影響，如圖中實線圈處所示，在少數(shù)情況下超出部分較大，對原多邊形形狀的改變將可能對版圖功能產(chǎn)生影響，如圖中虛線圈處所示，此時可以通過前文所述的對切線與斜邊進行關(guān)系檢測減少交疊部分來解決.

圖15 程序?qū)? 000個頂點的直角多邊形分解結(jié)果Fig.15 Fracturing result of one rectilinear polygon with 1 000vertices

由圖16和圖17可見，本文算法在分解后不存在薄片，交疊部分被控制在足夠小的區(qū)域，能夠保證雙成像光刻的性能.分解后相連的多邊形間都存在交疊部分，能夠解決由于覆蓋誤差引起的圖形斷開問題.圖18是對圖16（a）的版圖部分進行版圖分解和顏色分配后的結(jié)果[17]，其中圖18（a）是本文算法在不允許分解后圖形間存在交疊的前提下的處理結(jié)果，圖18（b）是本文算法的處理結(jié)果.由圖中可見，當不引入交疊時，版圖分解后的圖形中會存在大量薄片，導(dǎo)致在顏色分配后子版圖中仍舊存在薄片，如圖18（a）中的圈中所示，將給光刻帶來極大挑戰(zhàn)；而本文算法分解時通過引入交疊完全消除薄片的產(chǎn)生，因此顏色分配后的子版圖不存在薄片，可以安全地進行光刻.

圖19顯示了分別當圖18的兩種算法處理情況下的子版圖間發(fā)生相同偏移產(chǎn)生覆蓋誤差時的情況.子版圖間的偏移同時包括x方向和y方向.由圖19（a）所示，由于不引入交疊，子版圖間產(chǎn)生很小的偏移也會導(dǎo)致原版圖圖形發(fā)生多處斷開，如圖中圈中所示部分，多處斷開將對版圖功能產(chǎn)生很大影響；而圖19（b）本文算法的情況下，由于引入了不小于版圖工藝尺寸大小的交疊部分，在子版圖發(fā)生偏移時能夠維持版圖圖形的形狀不發(fā)生斷開，將能夠有效地解決因覆蓋誤差導(dǎo)致的圖形斷開問題，降低覆蓋誤差對雙成像光刻技術(shù)的影響.表1列出了對于兩個實際的版圖，使用不同的分解算法進行版圖分解、顏色分配和圖形合并后，薄片的數(shù)目.由表1可見，使用單方向分解算法時，將產(chǎn)生大量薄片；不引入交疊的算法（在不允許交疊的前提下的本文算法）也會產(chǎn)生接近原版圖多邊形1%比例數(shù)目的薄片；而本文算法消除了薄片的產(chǎn)生，避免產(chǎn)生光刻工藝無法接受的版圖，適用于雙成像光刻技術(shù).

表1 不同分解算法處理后薄片的數(shù)目Tab.1 Number of slivers by different algorithms

本文提出一種新的版圖分解算法，應(yīng)用于雙成像光刻技術(shù)，將版圖中的直角多邊形和帶斜角多邊形分解為矩形和所有內(nèi)角都是90°直角和鈍角的多邊形，以實現(xiàn)分解后的圖形不存在薄片為前提，以減少顏色分配后的沖突總數(shù)為目標，主要通過在可接受的時間復(fù)雜度下減少分解后切線總長度，同時引入交疊.引入交疊消除薄片的產(chǎn)生，同時解決由于覆蓋誤差引起的圖形斷開問題，并減少分解后的矩形數(shù)目，不僅減少沖突總數(shù)，也簡化版圖降低制造成本.通過實驗驗證該算法正確實現(xiàn)了上述功能，比現(xiàn)有算法更適合用于雙成像光刻技術(shù).

[1]ALICE.EUV與18英寸晶圓工藝皆延遲，業(yè)界焦急與無奈[EB／OL].電子工程專輯.（2012－02－16）[2012－03－07].http:∥www.eet－china.com／ART＿8800661433＿480201＿NT＿be26a1ef.HTM.

[2]International Technology Roadmap for Semiconductors 2011Edition [R／OL].（2012－03－07）[2012－04－07].http:∥www.itrs.net／Links／2011ITRS／Home2011.htm.

[3]Dusa M，F(xiàn)inders J，Hsu S.Double patterning lithography:The bridge between low k1ArF and EUV[J].MicrolithographyWorld，2008，17（1）:2－7.

[4]Mack C.Seeing double[J].Spectrum，IEEE，2008，45（11）:46－51.

[5]Kahng A B，Park C H，Xu X，etal.Layout decomposition approaches for double patterning lithography[J].IEEETransactionsonComputer－aidedDesignofIntegratedCircuitsandSystems，2010，29（6）:939－952.

[6]Yuan K，Yang J S，Pan D Z.Double patterning layout decomposition for simultaneous conflict and stitch minimization[J].IEEETransactionsonComputer－aidedDesignofIntegratedCircuitsandSystems，2010，29（2）:185－195.

[7]黃惠萍，陸偉成，付 強，等.基于延遲合并嵌入的帶障礙的時鐘樹布線算法[J].計算機輔助設(shè)計與圖形學(xué)報，2008，20（6）:718－723.

[8]Lingas A，Pinter R，Rivest R，etal.Minimum edge length partitioning of rectilinear polygons[C]∥Proceedings of the 20th Annual Allerton Conference on Communication，Control，and Computing.Illinois，America:Allerton Retreaat Center，1982:53－63.

[9]Wu S Y，Sahni S.Covering rectilinear polygons by rectangles[J].IEEETransactionsonComputer－aided DesignofIntegratedCircuitsandSystems，1990，9（4）:377－388.

[10]Wu S Y，Sahni S.Fast algorithms to partition simple rectilinear polygons[J].VLSIDesign，1994，1（3）:193－215.

[11]Gourley K D，Green D M.A polygon－to－rectangle conversion algorithm[J].IEEEComputerGraphics andApplications，1983，3（1）:31－36.

[12]Kahng A B，Xu X，Zelikovsky A.Fast yield driven fracture for variable shaped beam mask writing[C]∥Photomask and Next－Generation Lithography Mask Technology XI.SPIE－The International Society for Optics and Photonics.Yokohama，Japan:2006:62832R.

[13]Sezginer A.Challenges in double patterning EB／OL.（2007－02－26）[2011－04－18].http:∥electronics.wesrch.com／paper－details／pdf－EL1SE14BIX144－challenges－in－double－patterning－by－apo－sezginer－cto－invarium.

[14]Wiaux V，Verhaegen S，Cheng S，etal.Split and design guidelines for double patterning[C]∥Optical Microlithography XXI.SPIE－The International Society for Optical Engineering.San Jose，CA，USA:2008:692409.

[15]Keil J M.Covering orthogonal polygons with non－piercing rectangles[J].InternationalJournalof ComputationalGeometryandApplications，1996，7（5）:473－484.

[16]沈 聰，陸偉成，魏晗一.基于解開操作的直角多邊形隨機生成算法[J].計算機工程，2011，37（6）:269－271.

[17]Luk W S，Huang H P.Fast and lossless graph division method for layout decomposition using SPQR－tree[C].Proceedings of the International Conference on Computer－Aided Design.Piscataway，N J，USA:IEEE press，2010:112－115.