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

有效

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

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

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

步驟2：將最小化啞元金屬數目的啞元填充問題表示成標準的線性規劃問題；

步驟3：應用動態增加網格內啞元金屬密度的啟發式算法求解啞元填充問題。

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

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

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

3.如權利要求1所述的啞元填充的啟發式方法，其特征在于：步驟3所述應用動態增加網格內啞元金屬密度的啟發式算法求解啞元填充問題包含一個迭代過程，包括如下5個子步驟：

步驟3.1：對啟發式算法進行初始化；

步驟3.2：算法迭代開始，如果待填充窗口p的金屬密度大于給定的金屬密度下限L，迭代結束，算法結束，輸出網格內啞元金屬填充結果；如果待填充窗口p的金屬密度小于給定的金屬密度下限L，則進入下一步驟；

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

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

步驟3.5：在集合W中重新選擇具有最小金屬密度的窗口作為待填充的窗口p，然后轉到步驟3.2。

4.如權利要求1或3所述的方法，其特征在于：步驟3.1所述啟發式算法進行初始化通過如下步驟：

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

步驟3.1.2：包含所有不能再進行啞元填充的網格的集合T初始化為空集合；

步驟3.1.3：包含所有還需要進行啞元填充的窗口的集合W初始化為包含版圖內所有窗口。