TWI708140B - 用以驗證設計規則檢查疊組之測試佈局的自動產生技術 - Google Patents

Abstract

一種用以驗證一設計規則檢查疊組(DRC deck)之測試佈局的自動產生之電腦實施方法。該方法包含接收一第一佈局包含由多個多邊形參數界定的一或多個多邊形形狀。接收設計規則包含於多邊形參數上的不等式限制。一第二佈局係藉將數值之一隨機變化施加到該第一佈局之該等多邊形參數中之至少一者計算。一第三佈局之計算方式係經由改變該第二佈局之該等多邊形參數之值直到，相對於由該等限制界定的該等參數邊界中之一或多者，該等多邊形參數之一個別鬆弛為最小化為止。該第三佈局可儲存作為候選者測試佈局。

Description

用以驗證設計規則檢查疊組之測試佈局的自動產生技術 發明領域

本文揭示係有關於用於積體電路之設計驗證的電腦輔助測試，及更特別係有關於用以驗證設計規則檢查疊組之測試佈局的自動產生技術。

發明背景

設計規則檢查(DRC)乃電子設計自動化(EDA)的一塊，DRC被用來判定一積體電路的佈局設計是否滿足稱作為設計規則的一串列之推薦參數。由於典型積體電路中電路部件的複雜及層數故，DRC處理典型地使用CAD軟體或更明確言之DRC軟體執行。DRC軟體的一實例為由明導圖形公司(Mentor Graphics®)出品的Calibre®。典型地，設計規則為專用於一特定製程且可載明例如某些幾何形狀及連接性限制以確保有足夠邊際來考慮製程中的變異度。針對特定製程的一集合之設計規則稱作為DRC疊組、DRC執行集合、或規則疊組。典型DRC疊組可包括跑數百個至數千個設計規則檢查的指令。舉例言之，DRC疊組可包含指 令語言輸入檔案，其指示一處理器如何在界定表示欲製造的一積體電路的多邊形形狀之一佈局設計檔案上執行該等設計規則檢查。

為了驗證DRC疊組的具體實施，需要一集合的測試佈局包含預期合格通過設計規則檢查的個案-所謂「合格個案」，及預期未能通過設計規則檢查的個案-所謂「不合格個案」。舉例言之，如果期望測試設計規則的某個要求(限制)是否被正確實施，則產生針對該要求的至少一個不合格個案及至少一個合格個案是有用的。但因如同參數值的組合數目般，在一設計規則檢查中邊緣及形狀特徵的有效拓樸結構之數目隨著其數目而極其快速成長，須瞭解測試佈局或圖案量可能變成過大。測試佈局的手動產生受到產生佈局工作者的想像力、專門技術、及勤勉程度所限。據此，期望使用電腦而自動化產生測試佈局。

舉例言之，美國專利案第8,875,064號描述自動設計規則檢查(DRC)測試個案的產生，其中該方法包括提取於一積體電路設計中的錯誤記號的座標，使用該等座標產生一錯誤多邊形，在設計中選擇接觸該錯誤多邊形的多邊形，識別包圍該等經選取的多邊形之一矩形，及基於涵括於該矩形內部的該設計資料而產生一測試個案。不幸地，已知方法仰賴積體電路設計中的錯誤記號，其可能不適用以覆蓋一特定DRC疊組的該等規則。

據此，期望改良用以驗證一DRC疊組的測試佈局的自動產生，特別用以提供與檢查DRC疊組特別相關的測 試佈局。

發明概要

本文揭示之一個面向提出一種用以驗證一設計規則檢查(DRC)疊組之測試佈局的自動產生之電腦實施方法。舉例言之，DRC疊組包含用以驗證電路設計與一經擇定製程之依從性的設計規則檢查。該方法包含接收包含由多個多邊形參數界定的一或多個多邊形形狀的一第一佈局。例如，該等一或多個多邊形形狀表示於一電路設計的一或多層中之電路部分。該方法包含接收設計規則，包含於該等多邊形參數上之一或多個限制。例如，該等限制取決於該等限制是否被滿足而針對該等參數之可行性與不可行性區域間之多邊形參數界定參數邊界。該方法包含藉由施加數值之一隨機變化給該第一佈局的該等多邊形參數中之至少一者而計算一第二佈局。該方法包含藉由改變該第二佈局的該等多邊形參數之值直到該等多邊形參數相對於該等參數邊界中之一或多者的一個別鬆弛為最小化為止而計算一第三佈局。該方法包含儲存該第三佈局作為用以驗證該DRC疊組的一候選者測試佈局。例如，取決於是否滿足設計規則，候選者測試佈局可儲存為合格個案或不合格個案。

目前認知當測試佈局係以排他方式產生時，此等佈局的數目可成指數地增加到無法工作的該點。另一方面，當測試佈局係以受控方式產生時，諸如限制其數目， 例如對某個空間或寬度限制範圍時，可能遺漏了重要的合格及不合格個案，結果導致受測設計規則的覆蓋率不良。使用本方法，原則上可能以隨機方式排他地產生佈局，但其中隨機佈局隨後被優化成用於測試設計規則所最關注的該等佈局。全部可能的佈局及拓樸結構的該集合可以隨機方式有效地重複取樣，及在優化之後，只有關注的佈局被加至該測試佈局集合，原因在於其以最小邊際(鬆弛)通過或未通過設計規則檢查。此種方法優於仰賴單獨隨機產生方法的一項優點為其利用相當少數的測試佈局已能獲得良好覆蓋率。此種方法優於仰賴單獨優化方法的一項優點為其針對先前未曾設想的佈局，隨機取樣也可增加覆蓋率。再者，覆蓋率隨著程式的運行時間而增加，及若有足夠時間則可趨近於百分之百。當然，較大覆蓋率暗示較大數目的測試佈局，但如同使用單獨基於隨機產生之方法，該數目將不會「爆炸」。

本方法可產生解決方案或佈局，其經偏置以便用於測試該等設計規則時更加有用。舉例言之，關注的個案可以是根據限制與要求值的偏差達不多於1單位(最小網格距離)的一空間的個案。須瞭解與要求值有較大偏差的個案產生極少的或無額外覆蓋率，因而可安全地忽略不計。依據本文揭示之一個面向，藉由朝向接近被視為測試所關注的接近一限制的邊界者而偏置測試佈局的選擇，所產生的測試佈局之數目被最小化。針對此等邊界個案，邊緣位置的小量改變，典型地為1單位的改變，可能造成受測面向有 根本差異。舉例言之，若該面向為最小距離要求，邊緣的兩次移動達1單位可變更要求狀態從滿足最小鬆弛，到確切依從性，到不滿足具有最小鬆弛的要求。

於隨機化多邊形參數中，發現藉由涵括拓樸隨機化以及距離隨機化兩者，可有效達成特別關注的個案。於拓樸隨機化中，多邊形形狀的邊緣之數目或順序可經變更，表示可能適用不同的設計規則。舉例言之，取決於兩個形狀係並排排列或重疊排列，距離檢查可能不同。於距離隨機化中，多邊形形狀的邊緣可相對於限制的邊界改變距離，其可能導致在拓樸結構內部查找不同的邊界個案。距離變化也可導致合格個案及不合格個案間的交叉，兩者皆為測試設計規則所關注者。此外，拓樸變化或距離變化間之選擇本身可經隨機化來有效地取樣關注的佈局之數目，亦即針對不同限制合格/不合格的邊界個案。為了快速探索在不同拓樸結構中之候選者測試佈局，較佳地係朝向拓樸隨機化的選擇而偏置隨機選擇。

當最小化鬆弛時，發現較佳聚焦在某個拓樸結構內部的距離最小化。藉此方式，能防止當最小化時不同的設計規則開始起作用。舉例言之，多邊形參數可被阻止交叉用於拓樸結構保留之限制的一邊界。最小化參數的鬆弛例如可透過加上所謂鬆弛變數而將不等式限制轉換成等式進行，所謂鬆弛變數就此為場優化問題所已知。舉例言之，限制可配方成一鬆弛變數，其為參數值的函數。舉例言之，若鬆弛變數為正，如此表示限制係被滿足(可行性區域)。典 型地，若鬆弛變數為負，如此表示限制係不被滿足(不可行性)。然而，於本方法中此等不可行性區域也可以是不合格個案的關注的測試佈局。藉由最小化鬆弛變數的絕對值，參數可經修改用以查找在合格或不合格間的交叉的任一側上的一測試佈局。典型地，透過多個鬆弛變數之最小化，一佈局可朝向一關注的(分界線)測試優化。為了在合宜測試佈局上的快速覆蓋率，發現較佳係首先給定順位用以最小化最低初始鬆弛。也可以從低至高的順序處理其它鬆弛變數，例如在先前鬆弛變數被最小化之後判定。至於額外限制，於最小化下一個鬆弛變數中，優異地能將任何先前鬆弛變數固定在其最低值。

該程序可經迭代用以產生多個測試佈局而來測試任何數目的設計規則之面向。藉由追蹤新查找的佈局與先前查找的相同佈局間之比，可做出知情決策，若覆蓋率被視為足夠則是否中止迭代。舉例言之，若少於10%所產生的佈局係與先前產生的佈局有獨特差異，則可判定已探索實質百分比之有用的佈局。候選者佈局也可經過濾以維持只有獨特相關個案，例如測試設計規則的任一項組合的合格及不合格只有一次。舉例言之，具有一合格個案及一不合格個案的一對佈局，其中該等佈局彼此的差異極小，可被關注確切測試一設計規則的分界線個案。舉例言之，藉不同邊緣位置偏移器合格個案可與不合格個案差異達一個網格(最小值)距離。

用於各次迭代可接收一新種子佈局，或可使用相 同種子。新種子佈局也可基於先前查找的佈局。如此具有優點為先前查找的佈局已屬分界線個案，因而藉由改變一個參數值，新佈局也接近一或多個限制的邊界中之至少部分的機會增高。藉由使用前次查找的佈局作為下次迭代的種子，該等佈局可由通過參數空間的一隨機路徑查找，例如就不同拓樸結構而言該路徑可從初始種子佈局進一步行進。當然組合也屬可能。取決於查找新獨特佈局的成功率，也可能從先前查找的佈局偏置一種子佈局的選擇。舉例言之，若就查找進一步獨特測試佈局而言某個種子佈局為排他，則種子佈局可經偏置成較不常出現。

本文揭示之第二面向提出一種用以驗證一設計規則檢查(DRC)疊組之測試佈局的自動產生之電腦系統，該電腦系統包含一記憶體及耦合至該記憶體之一或多個處理器，其中該記憶體含有一集合的指令，其當由該等一或多個處理器執行時，造成該等一或多個處理器執行包含如此處描述之方法中之一或多者的操作。

本文揭示之第三面向提出一種以一電腦程式編碼的非暫態電腦可讀取媒體，該電腦程式包含一集合的指令，其當由一或多個電腦執行時，造成該等一或多個電腦執行包含如此處描述之方法中之一或多者的操作。

須瞭解本方法及系統可應用於最終導致積體電路的製造之設計及製造方法。於一項應用中，本文揭示提出一種驗證一DRC疊組之方法，包含如此處描述之測試佈局的自動產生及使用該等測試佈局驗證該DRC疊組。於又 一項應用中，本文揭示提出一種驗證一電路設計之方法，包含如此處描述之DRC疊組的驗證及使用該已驗證之DRC疊組檢驗證該電路設計。於又一項應用中，本文揭示提出一種製造一電路之方法，該方法包含如此處描述之電路設計的驗證及製造該已驗證的電路設計。須瞭解藉由DRC疊組的驗證，DRC疊組更值得信賴用以有效地驗證電路設計，可導致電路製造上的良率增高。

100-109‧‧‧步驟

B1-6‧‧‧邊界

c‧‧‧限制

D‧‧‧最小容許距離

F‧‧‧不合格區域

H1‧‧‧高度

L、L1-9、L2’‧‧‧佈局

La-c‧‧‧候選者測試佈局

Ld‧‧‧電路設計

Ld’‧‧‧經驗證的電路設計

Lm‧‧‧經製造的電路

Lx‧‧‧測試佈局

P‧‧‧合格區域

P1-2‧‧‧多邊形形狀

R1-2‧‧‧設計規則

S1-3‧‧‧鬆弛

X0-3、Y0-3‧‧‧邊緣座標

W1‧‧‧寬度

△W12、△W34‧‧‧隨機變化

本文揭示之裝置、系統及方法的此等及其它特徵、面向、及優點從後文詳細說明部分、隨附之申請專利範圍、及附圖將變得更為明瞭，附圖中：圖1A示意地例示於一參數空間產生測試佈局的一路徑；圖1B示意地例示於一測試佈局的產生期間的中間佈局；圖2A示意地例示於通過設計規則的第一隨機產生佈局中之兩個多邊形形狀；圖2B示意地例示於優化後自圖2A的隨機佈局推衍的一第一測試佈局；圖3A示意地例示針對未通過設計規則的第二隨機產生佈局中之兩個多邊形形狀；圖3B示意地例示於優化後自圖3A的隨機佈局推衍的一第二測試佈局；圖4A示意地例示於通過設計規則的但具有與圖2A不同 的拓樸結構的第三隨機產生佈局中之兩個多邊形形狀；圖4B示意地例示於優化後X自圖4A的隨機佈局推衍的一第三測試佈局；圖5A藉由描繪第一多邊形形狀及第二多邊形形狀的角隅點的不同位置示意地例示候選者測試佈局；圖5B示意地例示候選者測試佈局；圖6A示意地例示一設計規則實例；圖6B示意地例示用於驗證圖6A之該設計規則的具體實施之測試佈局；圖7A示意地例示一設計規則的另一實例；圖7B示意地例示用於驗證圖7A之該設計規則的具體實施之測試佈局；圖8示意地顯示包含用以產生測試佈局之一方法的流程圖；圖9示意地顯示測試佈局如何用於驗證一設計規則檢查疊組(DRC deck)的實例。

較佳實施例之詳細說明

除非另行界定否則此處使用的全部術語(包括技術及科學術語)具有與由熟諳技藝人士常見瞭解在詳細說明部分及附圖的脈絡中讀取的相同意義。於某些情況下，眾所周知的裝置及方法之詳細說明可被刪除，以免遮掩了本系統及方法之描述。如此處使用，除非上下文另行明白指示否則單數形「一(a)」、「一(an)」及「該」意圖也包括 複數形。術語「及/或」包括相關聯的列舉項目中之一或多者的任何及全部組合。須瞭解術語「包含」及/或「包含有」載明所述特徵的存在，但不排除一或多個其它特徵的存在或添加。須瞭解當描述結構或組件間之連結時，除非另行陳述否則此種連結可直接建立或經由中間結構或組件建立。附圖中，系統及組件的絕對尺寸及相對尺寸可經誇大以求清晰。實施例可參考本發明之可能理想化的實施例及中間結構的示意及/或剖面例示描述。於詳細說明部分及附圖中，相似的元件符號係指全文中相似的元件。

圖1A示意地例示由兩個參數H1及W1跨距的一參數空間。如此處描述的佈局之隨機化及優化例如可由通過多邊形參數的參數空間之一路徑例示。圖1B示意地例示根據針對不同佈局L1至L3的多邊形參數H1及W1的不同值之一多邊形形狀P1。

根據於圖1A中例示的實施例，參數空間被分割成合格區域「P」(白色背景)及不合格區域「F」(影線圖案)。在參數空間裡落入於合格區域「P」內的一點滿足了設計規則R1及R2的限制C之組合。在參數空間裡落入於不合格區域「F」內的一點不滿足設計規則R1及R2中之一或多者。舉例言之，設計規則R1、R2可等於或為更大型設計規則檢查集合的一子集或欲驗證的DRC疊組，亦即對此將產生一測試佈局。

根據於圖1B中例示的實施例，於本個案中，參數係指於一佈局中多邊形P1的高度H1及寬度W1。根據設計 規則R1，多邊形P1的寬度須為0.01至0.04或大於0.10。設計規則R2為類似但針對多邊形P1的高度H1。須注意設計規則可包含多個限制「C」的邏輯或布林組合。符號「&」係指不同的限制要求間之布林「及AND」運算，而符號「|」係指不同的限制要求間之布林「或OR」運算。設計規則R1及R2也可由布林運算元組合，例如要求R1 AND R2兩者皆滿足。

根據一個面向，本文揭示提出一種電腦實施方法用於驗證一DRC疊組的測試佈局的自動化產生。於一個實施例中，方法包含接收第一佈局L1，又稱種子佈局。於一個實施例中，種子佈局係以GDS格式描述，其中給定欲被變更的多邊形形狀。該等形狀的邊緣之正確位置並非極其要緊，只要其具有有效的起始拓樸結構即可。初始種子佈局本身例如可使用隨機初始參數自動化產生。另外，先前儲存的佈局可用作為種子，或初始種子可手動產生。於一個實施例中，佈局L1包含由多個多邊形參數W1、H1界定的多邊形形狀P1。舉例言之，多邊形形狀P1表示在電路設計的一或多層中之電路部分。

於一個實施例中，方法包含接收設計規則R1、R2包含在多邊形參數W1、H1上的限制C。設計規則中之各者可包含在多邊形參數W1、H1上的一或多個限制C。典型地，該等限制中之至少部分為不等式限制，例如，表示為等式，其針對該等參數中之一或多者分開地或組合地界定一開放端的容許值之範圍。當然，設計規則也可包含其它 限制，例如等式限制，其可例如用來界定或消除可變的多邊形參數中之一者。

限制C可用以界定在針對多邊形參數W1、H1的一參數空間裡介於其中符合該限制的一可行性區域與其中該限制不被滿足的一不可行性區域間之個別參數邊界B1、B2(於本圖中以點虛線表示)。舉例言之，針對不等式限制(例如，A<B、A

B、A>B、A

B)，典型地在一參數空間裡有一可行性區域其中符合不等式限制藉一參數邊界而與其中該不等式限制不被滿足的一不可行性區域分開。取決於該不等式限制是否包含大於/小於符號(>或<)；或等於或大於/小於符號(

或

)，參數邊界可涵括於可行性或不可行性區域中之一者。至於另一個實例，針對不等式限制，可行性區域與參數邊界可重疊於一線上，而不可行性區域可在任何位置但參數邊界除外。

於一個實施例中，參數邊界B1、B2進一步界定為一子集，其中多邊形參數W1、H1交叉在一或多個設計規則R1、R2的合格(P)與不合格(F)間。注意個別限制「C」的可行性區域典型地與遵照一或多個設計規則的合格/不合格區域不相同。舉例言之，一區域可針對該等限制中之一者為可行(例如，W1

0.04)，而針對另一限制為不可行(例如，W1

0.10)。藉由使用邏輯「或OR」運算組合限制，任一限制的可行性區域針對於設計規則中建立的組合為可行。藉由使用邏輯「及AND」運算組合限制，該組合的區域只有在兩個限制皆被滿足時才可行。

如此，參數邊界B1、B2可根據該等設計規則中之一或多者而針對該等限制中之各者分開界定或針對其布林組合界定。於一個實施例中，參數邊界包括保留佈局中的拓樸結構(例如，邊的順序或數目)的限制。藉由針對不同類型限制中之各者界定參數邊界B1、B2，優化可涉及鬆弛的最小化，例如就有關可製造性限制及/或拓樸限制而言，兩者可界定為一設計規則的一部分。拓樸限制也可與可製造性限制分開提供，例如，其中一集合的可製造性限制係針對某個拓樸結構界定，或其它可製造性限制(例如，距離檢查)係針對不同拓樸結構自動推衍。設計規則本身也可藉布林運算元組合。舉例言之，設計規則可析取組合或合取組合。目前發現特別在欲檢查的距離邊界及在拓樸變化可能出現令人關注的測試佈局。

於一個實施例中，方法包含藉由施加一值的隨機變化△W12給第一佈局L1的多邊形參數W1中之至少一者而計算第二佈局L2。藉由一次至多隨機變化多邊形參數中之一者，在隨機化之後可能更容易再度找到優化佈局，原因在於某些情況下其它參數可能仍然為最佳，亦即接近其個別參數邊界。藉由一次隨機變化多於一個參數，可更快達成不同拓樸結構。當然全部組合皆屬可能。

於一個實施例中，多邊形參數W1中之至少一者的該值之隨機變化△W12包含基於隨機產生數目而修改多邊形參數W1。於另一或又一個實施例中，隨機變化△W12包含藉在一經預選取範圍內的一隨機數的加、減、乘、或 除多邊形參數W1的該值。於另一或又一個實施例中，經預選取範圍係基於第二佈局L2的尺標。於一個實施例中，該經預選取範圍係基於第二佈局L2與參數邊界B1、B2的鄰近性。

於一個實施例中，由於隨機變化△W12的結果，多邊形參數W1、H1被允許交叉一可行性區域與一不可行性區域間之一或多個參數邊界B1、B2，或反之亦然。換言之，第二佈局L2可具有與第一佈局L1不同的拓樸結構，例如針對該等多邊形形狀有不同邊緣之順序及/或數目。

於一個實施例中，第一佈局的隨機變化可包含拓樸隨機化(△T1)及/或距離隨機化。於拓樸隨機化中，比較第一佈局L1，一多邊形參數的隨機變化變更了於第二佈局L2中多邊形形狀P1、P2的邊緣之順序或數目。於距離隨機化中，比較第一佈局，一多邊形參數的隨機變化變更了於第二佈局中該等形狀的邊緣間之距離。於一個實施例中，於計算第二佈局L2中，自至少拓樸隨機化及距離隨機化而做出隨機選擇。

於一個實施例中，方法包含計算第三佈局L3，計算方式係經由改變第二佈局L2的多邊形參數W1、H1值直到多邊形參數W1、H1相對於參數邊界B1、B2中之一或多者的一個別鬆弛S1、S2被最小化為止。換言之，多邊形參數相對於限制的邊際被最小化。於一個實施例中，該鬆弛係經最小化而在距參數邊界的網格間隔(DRC程式之解析度)上為最大。

於一個實施例中，一限制的鬆弛S1、S2之計算方式係藉將多邊形參數W1、H1值填充入個別不等式限制，及設定鬆弛S1、S2等於該限制方程的左手邊與右手邊間之數值差。因參數可在該限制的可行性區域或不可行性區域內，故可優異地最小化鬆弛的絕對值。如此考慮參數也可在參數邊界的「錯」邊，其仍然是關注的測試佈局。

於一個實施例中，在最小化之前，計算多個限制的個別初始鬆弛S1、S2；及最小化經偏置成以最低初始鬆弛S1改變限制中的多邊形參數H1用以首先最小化最低初始鬆弛S1。於一個實施例中，鬆弛S1、S2被循序最小化，始於最低初始鬆弛S1；重新計算鬆弛；及在首先最小化之後，繼續次低鬆弛S2。

於一個實施例中，多邊形參數W1、H1被防止交叉全部或部分參數邊界B1、B2，同時最小化第二佈局L2與第三佈局L3間之鬆弛S1、S2。藉此方式，可保留佈局的拓樸結構，同時仍然朝向參數邊界優化。於另一或又一個實施例中，藉最小化鬆弛而計算第三佈局L3中，多邊形參數W1、H1被阻止交叉設計規則R1、R2中之一或多者(例如，全部)的該等限制之一邊界。藉此方式，佈局不會改變特性從合格個案「P」改變成不合格個案「F」，或反之亦然。舉例言之，鬆弛變數S1、S2的最小化可能遭遇經修改的限制，阻止交叉參數邊界B1、B2。於一個實施例中，設計規則R1、R2的一或多個限制可藉由顛倒可行性區域與不可行性區域而予修改。於一個實施例中，經修改的限制係藉由反相設 計規則R1、R2的限制C中之一或多者，直到第二佈局L2的多邊形參數W1、H1滿足經修改的不等式限制為止而予推衍。

於一個實施例中，方法包含儲存第三佈局L3作為用於DRC疊組的驗證之一候選者測試佈局。舉例言之，第三佈局可儲存於記憶體內或碟片上，或任何其它可想見的本地或遠端儲存媒體上。於另一或又一個實施例中，若針對第三佈局L3的多邊形參數W1、H1值滿足全部所接收的設計規則R1、R2，則第三佈局L3係儲存為合格個案「P」，或否則儲存為不合格個案「F」。當然合格及不合格個案的分類也可於其後進行。

於一個實施例中，該方法經迭代，例如藉由取候選者測試佈局L3作為於下次迭代接收的新種子佈局。據此於第二迭代中，可包含隨機改變相同的或其它一或多個多邊形參數。舉例言之，如於圖1A中例示，佈局L4係藉H1之參數值的隨機變化△W34而從佈局L3改變。隨機化佈局L4接著藉由相對於參數邊界B3最小化鬆弛而優化成佈局L5。及此項處理程序可經迭代用以產生佈局L6至L9及其它。

此處描述之多邊形形狀可表示個別電路部分。包括電路部分的佈局資料可表示一積體電路的佈局。積體電路可包含於不同電路層的多層堆疊。佈局資料可包含於資料層中的電路部分匹配積體電路層中的實體結構。另外或此外，佈局資料可包含於推衍的資料層中之電路部分，例如得自布林組合及/或得自其它推衍，諸如實體層及結構的 OPC。電路部分例如可藉多邊形形狀而表示於佈局資料，亦即由在其周界內部形成表面的連結線段所組成的形狀。依據一個定義，圓形也可視為多邊形形狀。但從運算觀點，例如設計規則檢查法，較佳地電路部分係藉包含直線段的多邊形形狀表示，例如矩形、三角形、或其組合。藉由形狀的邊緣及/或填滿表示電路的經移轉的佈局具有分派的電氣及/或光學功能，佈局資料可界定電路部分。例如，使用遮罩及/或沈積，佈局可經移轉。沈積材料可包含例如金屬、半導體、或絕緣體。不同電路部分可包含不同材料。

圖2A示意地例示於佈局L2之第一實施例中的兩個多邊形形狀P1及P2。多邊形形狀P1及P2例如係由其個別邊緣的座標Xn及Yn(n=1,2,3,4)界定。該圖中也顯示環繞第一多邊形形狀P1的影線區，為了可製造性理由故，該影線區不應被第二多邊形形狀P2占據。

於一個實施例中，該等限制包含可製造性(DRC)限制Cm界定一或多個多邊形形狀P1、P2的邊緣X1、X2間之最短距離D，用以驗證積體電路設計與經選取的製程的依從性。於一個實施例中，該等限制包含拓樸限制Ct，界定一或多個多邊形形狀P1、P2的邊緣Y0、Y1、Y2的順序及/或數目，用以保留一或多個多邊形形狀P1、P2的相對佈局。於本實施例中，設計規則R1包含可製造性限制Cm的布林組合，其施加於由拓樸限制Ct所設定的範圍以內。於另一或又一個實施例中，(並非本設計規則R1的部分)，限制包含形狀限制，例如X1-X0>0，Y1-Y0>0，用以界定一或多個多 邊形形狀P1、P2的最小維度用於保留一或多個多邊形形狀P1、P2的存在或特性。形狀限制也可是等式限制用以設定多邊形形狀的固定維度。據此，須瞭解如此處使用，設計規則可包括例如可製造性限制、拓樸限制、及/或形狀限制的組合。也可包括其它限制。

圖2B示意地例示於優化之後自圖2A的佈局推衍的一第一測試佈局L3。

於一個實施例中，第三佈局L3的計算包含計算設計規則R1的限制的一或多個鬆弛變數S1、S2、S3呈多邊形參數Xn、Yn之函數。舉例言之，鬆弛變數可界定為一變數其加至不等式限制用以變換成等式。針對等式限制，鬆弛變數可界定為一變數其加到方程的一側以滿足該限制。據此，若已滿足了等式限制，則鬆弛可界定為零；若未滿足等式限制，亦即參數係在不可行性區域，則鬆弛可被考慮為等式限制距滿足有多遠的一度量。

於本個案下，形成設計規則R1的不等式限制中之各者係藉添加一個別變數Sn到方程的左手邊而被變換成等式方程。方程可經重排以表示鬆弛變數為該等參數的一函數，例如S1=D-(X2-X1)。取決於該等參數是否滿足該限制，鬆弛變數可以是正或負。另外，若不等式限制不滿足而被反相時，則鬆弛變數可經常性地為正。

於又一個實施例中，第三佈局L3的計算包含變更第二佈局L2的多邊形參數Xn、Yn之值朝向最小化一或多個鬆弛變數S1、S2之絕對值。須注意於本實施例中，鬆弛變 數S1不可能確切為零，原因在於如此表示根據可製造性限制Cm而交叉合格個案與不合格個案間之邊界：X2-X1>D。於L2之拓樸結構的限制以內，S1的最小值例如可以是依據設計工具的解析度之一最小網格距離。注意於此種情況下鬆弛S2及S3為倒數。於一個實施例中，鬆弛S3的最小化係受到維持先前已最小化的鬆弛S1及S2固定所限。於此種情況下，表示在由最小鬆弛S2的限制許可的範圍以內，鬆弛S3已經最小化。最小化順序可基於在未經優化佈局L2中該鬆弛的絕對值。

圖3A示意地例示於佈局L2的第二實施例中之兩個多邊形形狀P1及P2。該實施例係類似圖2A之實施例，但於此種情況下，多邊形形狀P2係落入於根據設計規則R1而距多邊形形狀P1的最小容許距離D以內。因此，設計規則R1的可製造性限制Cm不被滿足，該佈局構成不合格個案。與圖2A之另一項差異為多邊形形狀P2現在開始比拓樸限制Ct的邊界B2更接近邊界B3。

圖3B示意地例示在優化之後自圖3A之佈局推衍的一第二測試佈局L3。類似參考圖2B之描述，鬆弛變數S1、S2、S3可推衍自設計規則R1的限制。但於此種情況下，因未滿足第一限制Cm，故鬆弛變數S1加到方程右手邊。另外，若接受鬆弛變數具有負值，則鬆弛變數可加到方程左手邊。於該種情況下，例如，鬆弛變數S1的絕對值可被最小化。在鬆弛變數的最小化之後，注意多邊形P2確切駐在邊界B1，其中根據設計規則R1其仍屬測試不合格個案。於 此種情況下，多邊形P2被吸引朝向邊界B3，例如原因在於其初始較接近邊界B2之故(初始最低鬆弛)。

圖4A示意地例示於佈局L2之第三實施例中的兩個多邊形形狀P1及P2。須注意因第二多邊形形狀P2不再位在第一多邊形形狀P1旁，不同的設計規則R1’(或相同設計標準的子規則)將發揮作用。於此種情況下，設計規則R1’略為較複雜，原因在於彎曲邊界B1指示多邊形形狀間之最小距離D。由此一實施例驗證限制可包含一或多個多邊形參數的非線性項。於一個實施例中，鬆弛的最小化係藉線性或非線性優化器執行。

於一個實施例中，在拓樸限制Ct相關的鬆弛之前，可製造性限制Cm相關的鬆弛(例如，測試規則中的距離檢查)被最小化。又復，若兩個鬆弛表示式於隨機開始佈局中具有相等值，則較佳給予表示式鬆弛順位的最小絕對值。

圖4B示意地例示在優化之後自圖4A之佈局推衍的一第二測試佈局L3。於此種情況下，鬆弛變數S1經最小化直到第二多邊形形狀P2恰在邊界B1外側為止，例如達最小網格距離。在此邊界，鬆弛變數S2及S3不再能未經再度增加鬆弛變數S1或交叉邊界B1而進一步最小化，該種情況於此一個案為不容許。

圖5A藉由描繪第一多邊形形狀P1及第二多邊形形狀P2的角隅點的不同位置P2c而示意地例示候選者測試佈局Lc。候選者測試佈局Lc例如係由此處描述之方法的重複的迭代產生。圖5B示意地例示額外候選者測試佈局，其 以最小邊際包含合格及不合格個案。

於一個實施例中，所儲存的候選者測試佈局Lc經過濾而產生測試佈局Lx的一最末集合，其中該過濾包含唯有係屬一對候選者測試佈局La、Lb的部件時才接受一測試佈局，其中任何多邊形形狀的邊緣係由該對候選者測試佈局La、Lb間的至多一個最小網格距離置換，及其中該對符合設計規則R1、R2的合格P及不合格F個案。舉例言之，於圖5A中，由白圈指示的候選者測試佈局可被過濾掉，而由黑圈指示的候選者測試佈局可被保留。

圖6A示意地例示類似參考圖1A及1B討論的一設計規則R1實例。雖然該設計規則只指示寬度W，若允許該形狀旋轉90度，則也可應用至高度。

圖6B示意地例示用於驗證圖6A之設計規則的具體實施之測試佈局Lx。測試佈局Lx已經被自動整序成不合格個案在左手邊及合格個案在右手邊。舉例言之，具有多個形狀的積分佈局可用以檢查一DRC疊組，其中根據疊組的合格不合格位置之指示須符合測試佈局。

圖7A示意地例示一設計規則的另一個實例，其略為較複雜。於此一實施例中，設計規則檢查兩個輸入層的「OR」推衍層的形狀。若OR推衍層的多邊形具有T字形形狀，腿的長度大於或等於0.05，或若具有Z字形(「鋸齒」)，則佈局被視為合格通過設計規則。全部其它佈局被視為不合格個案。

於一個實施例中，該等佈局界定於多層中的多邊 形形狀，及設計規則中之一或多者係由一推衍層上的限制所界定，該推衍層為該等多層中之二或多者的邏輯組合例如AND、OR、NOT。

許多設計規則於其定義中使用「推衍層」。推衍層基於布林運算及分級運算界定於佈局中於原先層以外的其它層中之形狀。例如，推衍層可以是兩個原先層的「AND」，表示本層的形狀只存在於兩個原先層中之兩個形狀重疊之處。同理，推衍層中可有形狀係由原先層中的成長或收縮形狀界定。此等運算的任何組合皆屬可能。現在顯然推衍層中之形狀可接受恰如原先形狀的拓樸變化。若涉及分級則甚至可能完全消失或合併。例如，始於過小的原先形狀，當形狀收縮時將不在推衍層產生所得形狀。本文揭示中之辦法使能獲得處理推衍層的良好方式。在種子佈局的隨機佈局變化之後，以適當方式可產生推衍層。然後針對推衍層邊緣，可以原先形狀的相同方式，做出拓樸結構保留限制。又隨後對關注的佈局之優化採取相同辦法。如此造成所得型樣於該處在推衍層上的拓樸變化也經測試，包括測試確實具有或只是沒有推衍層中的形狀。推衍層相關的拓樸結構保留方程也可以常規拓樸結構方程的相同方式優化，故也將存在有推衍層的邊界個案。

圖7B示意地例示用於驗證圖7A的設計規則之具體實施的測試佈局。須注意測試佈局之數目已相當全面性，而為手動推衍所實質上不可行。

圖8示意地顯示包含用以產生測試佈局之一方法 的流程圖。

於一個實施例中，該方法包含接收(步驟101)由多邊形參數界定的一佈局之重複的迭代；隨機改變(步驟102)至少多邊形參數之值；相對於參數邊界中之一或多者而最小化多邊形參數的一鬆弛(步驟103)；及儲存(步驟104)所得佈局作為驗證DRC疊組的又一候選者測試佈局L3。於一個實施例中，迭代的候選者測試佈局係相對於先前迭代之已儲存佈局作檢查(步驟105)，及其中若新查找的獨特測試佈局相較於先前已查找的測試佈局之數目降至低於一預設比，則中止迭代的重複。

於一個實施例中，針對在第一次迭代後的至少一個迭代，接收的佈局(於步驟100中選擇)為先前迭代最末儲存的佈局。於另一或又一個實施例中，針對在第一次迭代後的至少一個迭代，接收的佈局(於步驟100中選擇)為於第一迭代期間接收的初始佈局。於另一或又一個實施例中，針對至少一次迭代，接收101的佈局係隨機地選自於先前迭代期間儲存的候選者測試佈局Lx中之一者。

依據一個面向，本文揭示提出一種驗證一DRC疊組之方法，包含根據步驟100-106測試佈局Lx的自動化產生；及及根據步驟107使用測試佈局Lx驗證DRC疊組。依據又一個面向，本文揭示提出一種驗證一電路設計之方法，包含根據步驟100-107驗證DRC疊組；及根據步驟108使用已驗證的DRC疊組驗證電路設計Ld。依據又一個面向，本文揭示提出一種製造一電路之方法，包含根據步驟100-108 驗證電路設計Ld；及依據步驟109製造電路Lm。

本文揭示之面向例如可於測試佈局Lx的自動化產生用於驗證一DRC疊組的電腦系統具體實施。於一個實施例中，該電腦系統包含一記憶體；及耦合至該記憶體的一或多個處理器，其中該記憶體含有一集合的指令，其當由一或多個處理器執行時使得一或多個處理器執行包含如此處描述之方法之操作。

本文揭示之面向例如可於以電腦程式編碼的非暫態電腦可讀取媒體實施，該電腦程式包含一集合的指令，其當由一或多個電腦執行時使得一或多個電腦執行包含如此處描述之方法之操作。

圖9示意地顯示測試佈局Lx如何能夠用於驗證DRC疊組的實例。於一個實施例中，測試佈局Lx於步驟107接受DRC疊組用以驗證DRC疊組確實查找在區域「F」裡的全部不合格個案，而不指示在測試佈局Lx的區域「P」中的不合格個案。於一個實施例中，然後於步驟108電路設計Ld遭遇已驗證的DRC疊組。如此可導致例如電路以經修改的高度H、寬度W、及/或距離D重新設計，直到獲得經驗證的電路設計Ld’為止。於一個實施例中，經驗證的電路設計Ld’係於步驟109製造(M)導致經製造的電路Lm。可注意經製造的電路Lm可偏離設計的電路Ld’，例如藉邊緣的圓化、多邊形形狀的略微位移及/或尺寸重新標註。但偏差須在公差以內以便不影響電路功能。

從前文揭示將瞭解本方法係與「蒙特卡羅(Monte Carlo)」產生方法不同，於該處許多可能產生的測試佈局中使用有限數目的經隨機選擇的測試佈局。於測試佈局產生中，經常關注點間及/或邊緣間有限數目的距離。針對全部此等距離，可使用一定範圍的離散值，而可能的測試佈局總數將為全部此等範圍的迪卡爾乘積。因如此可能為巨大數目，故從迪卡爾乘積中隨機取數目來縮小集合。本辦法中的一個值得注意的優點為使用者無需指示關注何種距離(因而也沒有使用者忘記載入關注距離的錯誤機會)，也無需指示該範圍，原因在於全部值(若干網格上)皆經嘗試。關注情況係藉應用至各個隨機產生的佈局的優化期選擇。此處一個優點為也可經自動化，將消除遺漏關注的個案的機會。

最後，前文討論係意圖僅供例示本系統及/或方法，不應解譯為限制隨附之申請專利範圍至任何特定實施例或群組實施例。據此，說明書及附圖須以例示方式視之而非意圖限制隨附之申請專利範圍各項的範圍。於詮釋隨附之申請專利範圍中，除非另行特別陳述否則須瞭解「包含」一詞並不排除於一給定請求項中列舉的元件或動作以外的其它元件或動作的存在；在一元件前方的「一(a)」或「一(an)」等詞並不排除多個此等元件的存在；申請專利範圍中之任何參考符號並非限制其範圍；數個「構件」可由相同的或不同的項目或具體實施的結構或功能表示；所揭示之裝置或其部分中之任一者可一起組合或分開成額外部分。互異的請求項中引述某些手段的單純事實並不指示此等手段的組合無法優異地使用。更明確言之，請求項的全 部工作組合皆須考慮為特異地經揭示。

B1-6‧‧‧參數邊界

c‧‧‧限制

F‧‧‧不合格個案

H1‧‧‧高度

L1-9‧‧‧佈局

P‧‧‧合格個案

R1-2‧‧‧設計規則

S1-2‧‧‧鬆弛參數

W1‧‧‧寬度

△W12、△W34‧‧‧隨機變化

Claims (17)

1. 一種用以驗證設計規則檢查(DRC)疊組之測試佈局的自動產生之電腦實施方法，該方法包含：接收包含由多個多邊形參數界定的一或多個多邊形形狀的一第一佈局，其中該等一或多個多邊形形狀表示於一電路設計的一或多層中之電路部分；接收包含於該等多邊形參數上之限制的設計規則，其中各個限制界定在針對該等多邊形參數的一參數空間裡介於其中符合該限制的一可行性區域與其中該限制不被滿足的一不可行性區域間之一個別參數邊界；藉由施加數值之一隨機變化給該第一佈局的該等多邊形參數中之至少一者而計算一第二佈局；藉由改變該第二佈局的該等多邊形參數之值直到該等多邊形參數相對於該等參數邊界中之一或多者的一個別鬆弛為最小化為止而計算一第三佈局；及儲存該第三佈局作為用以驗證該DRC疊組的一候選者測試佈局。
2. 如請求項1之方法，其中於計算該第二佈局中，從至少下列項目中做出一隨機選擇：一拓樸隨機化，其中相較於該第一佈局，一多邊形參數之一變化改變了該第二佈局中之該等多邊形形狀的邊緣之順序或數目；或一距離隨機化，其中相較於該第一佈局，一多邊形 參數之一變化改變了該第二佈局中形狀的邊緣間之一距離。
3. 如請求項1-2中任一項之方法，其中該等多邊形參數被阻止與該等參數邊界的至少一子集交叉，同時最小化該鬆弛以便從該第二佈局獲得該第三佈局。
4. 如請求項1-2中任一項之方法，其中該第三佈局之該計算包含：呈該等多邊形參數之一函數計算該等設計規則之該等限制的一或多個鬆弛變數；及朝向最小化該一或多個鬆弛變數之一絕對值來變更該第二佈局的該等多邊形參數之該等值。
5. 如請求項1-2中任一項之方法，其中：在最小化之前，計算多個限制之個別初始鬆弛；及該最小化經偏置來用最低初始鬆弛改變該限制中的該等多邊形參數，以首先最小化該最低初始鬆弛。
6. 如請求項1-2中任一項之方法，其包含下列各者之重複的迭代：接收由該等多邊形參數界定的一佈局；隨機改變該等多邊形參數中之至少一值；相對於該等參數邊界中之一或多者，最小化該等多邊形參數之一鬆弛；及儲存所得之該佈局作為又一候選者測試佈局。
7. 如請求項1-2中任一項之方法，其中一迭代的該候選者測試佈局係對已儲存的先前迭代的佈局作檢查，及其中 若新找出的獨特測試佈局之數目相較於先前已找出的非獨特測試佈局降至低於一預設比，則中止迭代的該重複。
8. 如請求項1-2中任一項之方法，其中在多次查找及儲存候選者測試佈局之迭代之後，所儲存的候選者測試佈局經過濾來產生測試佈局之一最終集合，其中該過濾包含唯若一測試佈局非為一接近成對候選者測試佈局的一部分則拒絕該測試佈局，其中一多邊形形狀的一邊緣至多位移在該接近成對候選者測試佈局間之一個最小網格距離，及其中該接近成對候選者測試佈局包含該等設計規則之一合格及不合格個案兩者。
9. 如請求項1-2中任一項之方法，其中針對至少一個迭代，被接收的該第一佈局係隨機從一先前迭代期間儲存的該等候選者測試佈局中之一者選出。
10. 如請求項1-2中任一項之方法，其中該等佈局界定出多層中之多邊形形狀，及該等設計規則中之一或多者係由在一推衍層上的限制界定，該推衍層為該等多層中之二或更多者的一布林組合。
11. 如請求項1-2中任一項之方法，其中該等限制包含了界定該一或多個多邊形形狀的邊緣間之最小距離的可製造性限制，用以驗證積體電路設計與一選定製程的依從性，其中該參數邊界指出該等設計規則之一合格區域與不合格區域間之一交叉。
12. 如請求項1-2中任一項之方法，其中該等限制包含了界 定該一或多個多邊形形狀的邊緣之一順序及/或數目的拓樸限制，用以保留該一或多個多邊形形狀的一相對佈局，其中該參數邊界指出該等多邊形形狀的不同拓樸結構間之一交叉。
13. 如請求項1之方法，其中該隨機變化係基於一隨機生成數。
14. 如請求項1之方法，其中該隨機變化包含藉由在一預選定範圍內選出的一隨機數來對該多邊形參數的一值進行加、減、乘、或除法運算。
15. 如請求項14之方法，其中該預選定範圍係基於該第二佈局的一尺度、或該第二佈局與一個別參數邊界的鄰近度。
16. 一種用以驗證設計規則檢查(DRC)疊組之測試佈局的自動產生之電腦系統，該電腦系統包含：一記憶體；及耦合至該記憶體之一或多個處理器，其中該記憶體含有一組指令，該等指令在由該一或多個處理器執行時，致使該一或多個處理器執行包含如請求項1至15中任一項之方法的操作。
17. 一種編碼有電腦程式的非暫態電腦儲存媒體，該電腦程式包含一組指令，該等指令在由一或多個電腦執行時，致使該一或多個電腦執行包含如請求項1至15中任一項之方法的操作。

Images