一種用于雙成像光刻中的版圖分解算法

魏晗一，陸偉成

（復(fù)旦大學(xué) 專用集成電路與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，上海201203）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 對(duì)1個(gè)多邊形的分解（Ⅰ）Fig.4 Fracture of a polygon（Ⅰ）

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

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

圖7 對(duì)1個(gè)多邊形的分解（Ⅳ）Fig.7 Fracture of a polygon（Ⅳ）

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

2 算 法

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

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

圖8顯示了帶斜角多邊形中被這2個(gè)限制所排除的情況:2條斜邊相鄰，或斜角是銳角.圖中使用頂點(diǎn)和與之相連的邊表示帶斜角多邊形的一部分.在邊一側(cè)的陰影表明位于多邊形內(nèi)部.邊使用有向線段表示，因?yàn)楸疚乃惴俣ǘ噙呅卧诜纸馇耙呀?jīng)經(jīng)過一種預(yù)處理，使得遍歷代表多邊形的頂點(diǎn)點(diǎn)集時(shí)，所得到的有向閉環(huán)是逆時(shí)針方向.在本文接下來的部分中將多次使用類似圖8的表示方法.

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

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

根據(jù)參考域D所包含的象限不同，可以把優(yōu)角a的位置分為4種情況.由于本文算法中對(duì)這4種情況下的分解過程極其相似，所以下文僅針對(duì)參考域D包含第一象限的情況，即如圖9所示的情況進(jìn)行描述，其他3種情況的分解可以通過類比得到.分解的基本原理是在優(yōu)角位置處產(chǎn)生切線，將其分解為2個(gè)角，相應(yīng)地將當(dāng)前的多邊形分解為2個(gè)多邊形.由于切線只能是與坐標(biāo)軸平行的直線，而優(yōu)角的2條邊里必有1條是直邊，因此每次分解相當(dāng)于使優(yōu)角減去90°或180°，直至將所有優(yōu)角都分解為鈍角、90°直角、平角的組合時(shí)，分解完畢.根據(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個(gè)限制所排除的情況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）在分解時(shí)則又會(huì)出現(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ù)對(duì)a2進(jìn)行分解，即對(duì)原優(yōu)角a進(jìn)行第二次分解.在下文中可知，由于在當(dāng)前優(yōu)角a和參考邊r位置關(guān)系的7種情況中大多數(shù)都將引入交疊，在當(dāng)前優(yōu)角a滿足270°＜a＜360°時(shí)，在進(jìn)行1次分解后往往產(chǎn)生的2個(gè)多邊形中有1個(gè)仍舊存在優(yōu)角，需要進(jìn)行第二次分解，類似圖11（b）的情況.顯然地，a有1條豎直方向直邊的情況可以通過類比得到.

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

記邊m所在直線為l，如果N?l，由當(dāng)前點(diǎn)N向邊l作垂線，交于垂點(diǎn)A.

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

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

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

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

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

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

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

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

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

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

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

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

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

輸出:代表分解后的圖形的集合的頂點(diǎn)點(diǎn)集V和Vadd.

步驟1:遍歷V中每個(gè)頂點(diǎn)；

步驟2:如果找到1個(gè)優(yōu)角a（及當(dāng)前點(diǎn)N）；

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

圖19顯示了分別當(dāng)圖18的兩種算法處理情況下的子版圖間發(fā)生相同偏移產(chǎn)生覆蓋誤差時(shí)的情況.子版圖間的偏移同時(shí)包括x方向和y方向.由圖19（a）所示，由于不引入交疊，子版圖間產(chǎn)生很小的偏移也會(huì)導(dǎo)致原版圖圖形發(fā)生多處斷開，如圖中圈中所示部分，多處斷開將對(duì)版圖功能產(chǎn)生很大影響；而圖19（b）本文算法的情況下，由于引入了不小于版圖工藝尺寸大小的交疊部分，在子版圖發(fā)生偏移時(shí)能夠維持版圖圖形的形狀不發(fā)生斷開，將能夠有效地解決因覆蓋誤差導(dǎo)致的圖形斷開問題，降低覆蓋誤差對(duì)雙成像光刻技術(shù)的影響.表1列出了對(duì)于兩個(gè)實(shí)際的版圖，使用不同的分解算法進(jìn)行版圖分解、顏色分配和圖形合并后，薄片的數(shù)目.由表1可見，使用單方向分解算法時(shí)，將產(chǎn)生大量薄片；不引入交疊的算法（在不允許交疊的前提下的本文算法）也會(huì)產(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°直角和鈍角的多邊形，以實(shí)現(xiàn)分解后的圖形不存在薄片為前提，以減少顏色分配后的沖突總數(shù)為目標(biāo)，主要通過在可接受的時(shí)間復(fù)雜度下減少分解后切線總長(zhǎng)度，同時(shí)引入交疊.引入交疊消除薄片的產(chǎn)生，同時(shí)解決由于覆蓋誤差引起的圖形斷開問題，并減少分解后的矩形數(shù)目，不僅減少?zèng)_突總數(shù)，也簡(jiǎn)化版圖降低制造成本.通過實(shí)驗(yàn)驗(yàn)證該算法正確實(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]黃惠萍，陸偉成，付 強(qiáng)，等.基于延遲合并嵌入的帶障礙的時(shí)鐘樹布線算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，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ī)生成算法[J].計(jì)算機(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.