[發明專利]一種化學機械拋光工藝啞元填充方法

有效

• 申請號: 200910055196.3
• 申請日: 2009-07-22
• 公開（公告）號: CN101964001A
• 公開（公告）日: 2011-02-02
• 發明（設計）人: 曾璇;周海;嚴昌浩;陶俊;馮春陽
• 申請（專利權）人: 復旦大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 包兆宜

1.一種化學機械拋光工藝啞元填充方法，其特征在于包括如下步驟：

步驟1：輸入待填充的版圖、給定版圖金屬密度的上下界、版圖上允許啞元填充的可行區域以及近似精度ε；

步驟2：將最小化啞元金屬數目的啞元填充問題轉化成一種特殊的覆蓋線性規劃問題；

步驟3：應用完全多項式時間近似算法FPTAS求解最小啞元填充問題。

2.如權利要求1所述的方法，其特征在于：步驟2所述將最小化啞元金屬數目的啞元填充問題轉化成一種特殊的覆蓋線性規劃問題是基于固定的r-劃分模式，通過如下步驟：

步驟2.1：以固定的r-劃分模式劃分所述版圖區域；

步驟2.2：將最小化啞元金屬數目的啞元填充問題表示成標準的線性規劃問題，其中優化目標為總的啞元金屬密度最小化，即代表總的啞元填充數目最少，約束條件為填充后窗口金屬密度應在給定的窗口金屬密度下界L和上界U之內，并且網格的啞元金屬密度應小于給定的可允許填充的啞元金屬密度上界slack；

步驟2.3：通過把加到窗口密度上的上界U加到窗口內的每個網格密度上，上述線性規劃問題轉化成一種特殊的覆蓋線性規劃問題，其中優化目標依舊為總的啞元金屬密度，約束條件轉化為填充后窗口的啞元金屬密度應大于給定的窗口密度下界上和窗口原有金屬密度的差值，并且網格的啞元金屬密度應既小于給定的可允許填充的啞元金屬的密度上界slack又小于給定的窗口密度上界U和網格原有金屬密度的差值。

3.如權利要求1所述的啞元填充方法，其特征在于：步驟3所述應用完全多項式時間近似算法FPTAS求解最小啞元填充問題包含兩層迭代，即外層迭代和內層迭代，包括如下子步驟：

步驟3.1：對完全多項式時間近似算法FPTAS進行初始化；

步驟3.2：外層迭代開始，如果所有網格內總的啞元金屬密度已經大于外層迭代終止變量θ，則外層迭代結束，算法結束，輸出優化結果；如果所有網格內總的啞元金屬密度小于外層迭代終止變量θ，則增加內層迭代控制變量α，并進入下一步驟；

步驟3.3：內層迭代開始，如果待填充窗口p的相對啞元金屬密度大于內層迭代控制變量α，表明算法滿足約束，內層迭代結束，轉入步驟3.7；如果待填充窗口p的相對啞元金屬密度小于內層迭代控制變量α，表明算法不滿足約束，則進入下一步驟；

步驟3.4：選擇屬于待填充窗口并且啞元密度還未達到密度上限的網格作為待填充網格；

步驟3.5：根據網格密度代價函數和近似精度，來確定待填充網格的啞元密度增加量，對待填充窗口p內所有待填充的網格進行啞元金屬填充；

步驟3.6：重新選擇所有浮動窗口中具有最小相對密度ρ(p)/b(p)的窗口p，作為待填充窗口，然后轉到步驟3.3；

步驟3.7：內層迭代結束，算法存儲最優結果，然后轉到步驟3.2。

4.如權利要求1或3所述的啞元填充方法，其特征在于：所述步驟3.1的對完全多項式時間近似算法FPTAS進行初始化通過如下步驟：

步驟3.1.1：網格內啞元金屬密度x初始化；

步驟3.1.2：外層迭代終止變量θ初始化為θ＝1；

步驟3.1.3：初始化內層迭代控制變量α，0＜α＜1；

步驟3.1.4：算法初始化x^*＝x，α^*＝α，x^*和α^*分別用來存儲算法最優的網格內啞元金屬密度的變量和獲得此最優值時的內層迭代控制變量，并作為算法最終結果輸出。