考慮通孔的基於不均勻網格的多層布線方法

2023-10-23 17:50:32 1

專利名稱：考慮通孔的基於不均勻網格的多層布線方法
技術領域：
本發明涉及一種超大規模集成電路物理設計技術領域。
背景技術：
目前，集成電路製造工藝已經可以支持多層互連線結構的晶片製造，各層互連線 由金屬實現，層之間的連接通過通孔工藝實現。相應的集成電路設計及電子設計自動化 (EDA)工具需要支持多層互連結構的版圖設計。由於不同布線層的線寬和最小線間距並不 一樣，連接每兩層通孔的大小和通孔與金屬連線之間的最小間距也各有差異，因此實現集 成電路的多層布線還存在著巨大困難。目前的集成電路布線模型可分為兩大類一、有網格布線模型，二、無網格布線模 型。這兩種模型主要是根據布線區域的表示以及走線位置是否受限制來劃分的。因為無網 格模型在處理多線寬方面具有一定的優勢，並且無網格模型的布線效率也比有網格模型高 很多，致使越來越多的布線器選擇無網格模型。基於無網格模型的布線算法主要有以下兩類一、基於隱式連接圖的布線方法。在布線開始前，將每個障礙的邊界按照「線寬/2+ 線間距」的距離進行擴展，並延長障礙的擴展邊界直到遇到布線區域邊界。把各個延長線 的交點表示為結點，則整個版圖形成了一個圖。因為結點並沒有在計算機中顯示地構造出 來，而是通過保存橫向延長線和縱向延長線的坐標間接表示結點的，所以是一種隱式的連 接圖。然後採用某種方法尋找最短路徑，如圖1所示。二、基於網塊的布線方法。該方法將整個布線區域劃分為一個個矩形區域，稱為 「網塊」，一個網塊為一個障礙網塊，或者空白網塊。障礙網塊是不能走線的區域，空白網塊 是可以走線的區域，並採用角勾鏈數據結構對網塊進行管理。然後採用某種方法尋找一條 由空白網塊連成的路徑，如圖2所示。基於隱式連接圖的無網格布線方法通過將無網格布線環境轉化為一個隱式連接 圖，可以直接調用傳統的布線算法進行布線，直觀易行且數據表示和維護簡單。但是當障礙 數目較多時，障礙邊界擴展得到的橫向延長線和縱向延長線也會較多，導致搜索速度變慢。 在極端情況下，延長線之間的間距甚至小於有網格布線中的一個網格大小時，效率會低於 有網格的效率。此外，因為延長線交點並沒有實際構造出來，因此在搜索時檢查該交點是否 可擴展這個操作無法在常數時間內完成，也在一定程度上影響了算法速度。基於網塊的布線方法是在一個網塊構成的區域中尋找布線路徑。該方法相對於基 於隱式連接圖的方法速度略有提高，但是因為網塊的大小位置不能用一個簡單的數據結構 表示，尋找相鄰的網塊也無法簡單的通過一步操作來實現，在該方法中採用了角勾鏈結構 存儲，角勾鏈結構對於尋找相鄰網塊比較方便，但是仍然無法在常數時間內完成，並且維護 該結構也需要一定的時間代價。

發明內容
針對上述問題，本發明提供一種能夠處理不同布線層的不同線寬和最小線間距， 且滿足通孔的設計規則約束的考慮通孔的基於不均勻網格的多層布線方法。為達到上述目的，本發明所述考慮通孔的基於不均勻網格的多層布線方法，包括 以下步驟(1)讀入布線區域內的障礙信息、待布線網信息和工藝信息；(2)依據上述障礙信息建立並規範障礙列表；(3)擴展障礙列表中各障礙的邊界；(4)設置起始點集合和終止點集合；(5)構造三維不均勻網格陣列；(6)設置三維不均勻網格陣列的允許擴展方向；(7)基於上述允許擴展方向，採用A*算法對三維不均勻網格進行布線路徑搜索；(8)輸出搜索路徑。其中，步驟(1)中，所述待布線網信息包括該待布線網的可用布線層信息，布線區 域大小信息以及起始點和終止點信息或起始模塊和終止模塊信息；所述工藝信息包括待布線網的布線層層數，布線區域允許的最小線寬值，各布線 層通孔直徑大小，允許最小的線到線間距值，允許最小的線到通孔間距值，允許最小的通孔 到通孔間距值。步驟(2)中，所述障礙列表中的每個列表元素是由該障礙所在布線層層號，頂點 坐標，以及該障礙是通孔或非通孔來表示，進一步地，步驟(2)的具體實現步驟如下2. 1根據步驟(1)中所述的障礙信息建立障礙列表；2. 2遍歷障礙列表，調用多邊形到矩形的轉化程序將每一個多邊形障礙轉化為至 少一個矩形障礙；2. 3刪除障礙列表中存儲的原多邊形障礙，將轉化得到的矩形障礙添加到障礙列 表中。進一步地，步驟(3)具體實現如下3. 1初始化橫坐標集合和縱坐標集合；3. 2遍歷步驟(2)得到的障礙列表，將非通孔矩形障礙的每一個邊界分別按照「線寬 /2+線間距」的距離進行擴展，得出垂直擴展邊界和水平擴展邊界；將通孔矩形障礙的每一個 邊界按照「線寬/2+線到通孔的間距」的距離進行擴展，得出垂直擴展邊界和水平擴展邊界；3. 3遍歷步驟(2)得到的障礙列表，將非通孔矩形障礙的每一個邊界分別按照「通 孔直徑/2+線到通孔間距」的距離進行擴展，得出垂直擴展邊界和水平擴展邊界；將通孔矩 形障礙的每一個邊界分別按照「通孔直徑/2+通孔到通孔的間距」的距離進行擴展，得出垂 直擴展邊界和水平擴展邊界；3. 4將(3. 2)和(3. 3)步中的所有垂直擴展邊界的橫坐標加入到橫坐標集合中，所 有水平擴展邊界的縱坐標加入到縱坐標集合中。進一步地，步驟(4)具體實現如下4. 1初始化起始點集合和終止點集合；
4. 2若布線模式為點到點模式，將布線起點添加到起始點集中，將布線終點添加到 終止點集中；若布線模式為模塊到模塊模式，進行步驟4. 2. 1 4. 2. 6 ；4. 2. 1調用多邊形到矩形的轉化程序分別將起始模塊和終止模塊轉化為至少一個 矩形模塊，並將轉化後的矩形模塊分別添加到起始矩形鍊表和終止矩形鍊表中；4. 2. 2分別遍歷起始矩形鍊表和終止矩形鍊表，讀取各矩形模塊的左邊界，右邊 界，下邊界和上邊界，並依據所述的工藝信息將每一個邊界分別按照「線寬/2」的距離進行 收縮，得出垂直收縮邊界和水平收縮邊界；4. 2. 3將垂直收縮邊界的橫坐標添加到橫坐標集合中，將水平收縮邊界的縱坐標 添加到縱坐標集合中；4. 2. 4分別對縱坐標集合和橫坐標集合中的坐標進行排序並去重；4. 2. 5將橫坐標集合中各橫坐標對應的垂直線分別與起始矩形鍊表中每個矩形模 塊的上邊界和下邊界的交點，縱坐標集合中各縱坐標對應的水平線分別與起始矩形鍊表中 每個矩形模塊的左邊界和右邊界的交點，以及橫坐標集合中各橫坐標對應的垂直線和縱坐 標集合中的各縱坐標對應的水平線在起始模塊內部的交點添加到起始點集合中；4. 2. 6將橫坐標集合中各橫坐標對應的垂直線與終止矩形鍊表中每個矩形模塊的 上邊界和下邊界的交點，縱坐標集合中各縱坐標對應的水平線與終止矩形鍊表中每個矩形 模塊的左邊界和右邊界的交點，以及橫坐標集合中各橫坐標對應的垂直線和縱坐標集合中 的各縱坐標的水平線在終止模塊內部的交點添加到終止點集合中。其中，本發明所述的三維不均勻網格陣列表示為由步驟(3)所述的橫坐標集合， 所述的縱坐標集合，以及所述布線層層數構成的三維數組。進一步地，步驟(6)具體實現如下6. 1設置同層擴展的允許擴展方向；遍歷步驟(2)得到的障礙列表，若該矩形障礙是非通孔障礙，設置三維不均勻網 格陣列中所有在該矩形障礙按照「線寬/2+線間距」擴展的左，右，上，下邊界上的網格點， 分別不可向右，左，下，上擴展，並設置由該左，右，上，下邊界所構成的矩形內部的所有網格 點為不合法網格點；若該障礙是通孔障礙，設置三維不均勻網格陣列中所有在該障礙按照 「通孔直徑/2+線到通孔間距」擴展的左，右，上，下邊界上的網格點，分別不可向右，左，下， 上擴展，並設置由該左，右，上，下邊界所構成的矩形內部的所有網格點為不合法網格點；6. 2設置跨層擴展的允許擴展方向；遍歷步驟(2)得到的障礙列表，若該矩形障礙是非通孔障礙，設置三維不均勻網 格陣列中所有在該障礙按照「線寬/2+線到通孔間距」擴展的左，右，上，下邊界所構成的 矩形內部的網格點不能向相鄰層的網格擴展，並設置相鄰層在對應區域內的網格點不能向 該層擴展；若該障礙是通孔障礙，設置三維不均勻網格陣列中所有在該障礙按照「通孔直徑 /2+通孔到通孔間距」擴展的左，右，上，下邊界所構成的矩形內部的網格點不能向相鄰層的 網格擴展，並設置相鄰層在對應區域內的網格點不能向該層擴展。進一步地，步驟(7) A*算法進行路徑搜索的具體實現步驟如下7. 1創建待擴展點的鍊表，保存所有已生成而未擴展的點；以及封閉鍊表，記錄已 訪問過的點；7. 2將起始點集合中的所有點按照該點到終止點集合中點的最短距離有序地列入待擴展點的鍊表中；7. 3在上述待擴展點的鍊表中讀取擴展代價最小的點n，並判斷點η是否在終止點 集合中；是，結束搜索，否，繼續下面的步驟；7. 4對點η進行擴展，並對擴展後得到的點χ進行判斷若點χ在待擴展點的鍊表中，比較點χ的不同路徑的擴展代價，若該擴展代價小於 待擴展點的鍊表中的擴展代價，用該擴展代價更新待擴展點的鍊表中的擴展代價，並將具 有新的擴展代價的點X轉移到鍊表中；若點χ在封閉鍊表中，比較點χ的不同路徑的擴展代價，若該擴展代價小於封閉鏈 表中的擴展代價，用該擴展代價更新封閉鍊表中的擴展代價，並將點X放入待擴展點的鏈 表中；若點χ既不在待擴展點的鍊表中，也不在封閉鍊表中；求解點χ的擴展代價，並將 點X放入待擴展點的鍊表中；7. 5將點η放入到封閉列表中；7. 6按照擴展代價將待擴展點的鍊表中的各點進行排序，重複步驟7. 3 7. 6。進一步地，步驟(8)依據步驟(7)的搜索結果；搜索成功，輸出搜索到的路徑，搜索 失敗，輸出布線失敗。本發明所述考慮通孔的基於不均勻網格的多層布線方法不僅根據線寬和線間距 對障礙邊界進行擴展，同時還根據通孔大小和通孔間距對障礙邊界進行了擴展，並基於上 述擴展結果構造出了一三維不均勻網格陣列。此外，本發明在路徑搜索前，還分別設置同層 擴展的允許擴展方向和跨層擴展的允許擴展方向，使得搜索結果滿足設計規則。本發明具有以下幾點有益的效果1、本發明可以處理不同布線層的不同線寬和最小線間距，同時可以滿足通孔的設 計規則約束。2、本發明同時支持點到點布線模式和模塊到模塊布線模式，將點或者模塊統一轉 化為點集，點集中點的選取保證在多層搜索中可以找到最優路徑。3、本發明可使用C++語言並用面向對象思想設計和實現，具有較強的平臺通用 性，可以在不同的平臺上運行。


圖1為基於隱式連接圖的布線方法；圖2為基於網塊的布線方法圖；圖3為本發明考慮通孔的基於不均勻網格的多層布線方法的流程圖；圖4為本發明所述非通孔障礙根據線寬和線間距約束擴展邊界的示意圖；圖5為本發明所述通孔障礙根據線寬和線間距約束擴展邊界的示意圖；圖6為本發明所述非通孔障礙根據通孔大小和通孔間距約束擴展邊界的示意圖；圖7為本發明所述通孔障礙根據通孔大小和通孔間距約束擴展邊界的示意圖；圖8為本發明起始點模塊或終止點模塊轉化為點集的示意圖；圖9為本發明所述三維不均勻網格陣列的一具體實施例示意圖。
具體實施例方式下面結合說明書附圖對本發明的具體實施方式
做詳細描述。如圖3所示，本發明考慮通孔的基於不均勻網格的多層布線方法的流程圖。圖中 所示本發明的具體實施步驟如下(1)讀入布線區域內的障礙信息、待布線網信息和工藝信息。所述的待布線網信息包括該待布線網的可用布線層信息，布線區域大小信息，以 及起始點和終止點信息或起始模塊和終止模塊信息；其中，待布線網的可用布線層信息由 用戶指定輸入。工藝信息主要包括該布線層層數，布線區域允許的最小線寬值，通孔直徑 大小，允許最小的線到線間距值，允許最小的線到通孔間距值，允許最小的通孔到通孔間距 值。(2)建立並規範障礙列表。2. 1依據讀入的障礙信息建立障礙列表obsList，其中，所有障礙的形狀均為直角 多邊形，由該直角多邊形所在的布線層層號和多邊形的頂點坐標表示，同時障礙還包括一 個表示其是否是通孔的屬性通孔或非通孔。2. 2規範障礙列表obsList，即遍歷已建立的障礙列表obsList，調用多邊形到矩 形的轉化程序將每一個多邊形障礙都轉化為矩形障礙；然後，刪除障礙列表中存儲的原多 邊形障礙，將轉化得到的矩形障礙添加到障礙列表中。(3)擴展障礙邊界。3. 1初始化橫坐標集合和縱坐標集合；3. 2根據線寬和線間距約束擴展障礙邊界；遍歷步驟(2)得到的障礙列表obsList，將非通孔矩形障礙的每一個邊界分別按 照「線寬/2+線間距」的距離進行擴展，得出垂直擴展邊界和水平擴展邊界；將通孔矩形障 礙的每一個邊界分別按照「線寬/2+線到通孔的間距」的距離進行擴展，得出垂直擴展邊界 和水平擴展邊界；3. 3根據通孔大小和間距約束擴展障礙邊界；遍歷步驟(2)得到的障礙列表obsList，將非通孔矩形障礙的每一個邊界分別按 照「通孔直徑/2+線到通孔間距」的距離進行擴展，得出垂直擴展邊界和水平擴展邊界；將 通孔矩形障礙的每一個邊界分別按照「通孔直徑/2+通孔到通孔的間距」的距離進行擴展， 得出垂直擴展邊界和水平擴展邊界；3. 4將(3. 2)和(3. 3)步中的所有垂直擴展邊界的橫坐標加入到橫坐標集合xset 中，所有水平擴展邊界的縱坐標加入到縱坐標集合yset中。(4)設置起始點集合和終止點集合。4. 1初始化起始點集合S和終止點集合T ；4. 2若布線模式為點到點模式，則將布線起點加入起始點集中，將布線終點加入終 止點集中；若布線模式為模塊到模塊模式，進行如下步驟；首先，調用多邊形到矩形的轉化程序分別將起始模塊和終止模塊轉化為至少一個 矩形模塊，並分別將各矩形模塊相應地添加到起始矩形鍊表和終止矩形鍊表中；然後對鏈 表中的每個矩形模塊的邊界分別按照「線寬/2」的距離進行收縮，得到垂直收縮邊界和水平 收縮邊界；
然後，將垂直收縮邊界的橫坐標加入到橫坐標集合中，水平收縮邊界的縱坐標加 入到縱坐標集合中，對橫坐標集合和縱坐標集合重新排序並去重；最後，將橫坐標集合中各橫坐標對應的垂直線分別與起始矩形鍊表中每個矩形的 上邊界和下邊界的交點，縱坐標集合中各縱坐標對應的水平線分別與起始矩形鍊表中每個 矩形的左邊界和右邊界的交點，以及橫坐標集合中各橫坐標對應的垂直線和縱坐標集合中 的各縱坐標對應的水平線在起始模塊內部的交點添加到起始點集合中；同理，將橫坐標集 合中各橫坐標對應的垂直線與終止矩形鍊表中每個矩形的上邊界和下邊界的交點，縱坐標 集合中各縱坐標對應的水平線與終止矩形鍊表中每個矩形的左邊界和右邊界的交點，以及 橫坐標集合中各橫坐標對應的垂直線和縱坐標集合中的各縱坐標的水平線在終止模塊內 部的交點添加到終止點集合中。(5)構造三維不均勻網格陣列。三維不均勻網格陣列表示為由步驟(3)得到的橫坐標集合xset和縱坐標集合 yset,以及布線層數構造的三維數組Info，
其中sizeX是數組的列數，SizeY
是數組的行數，sizeZ是布線層數。(6)設置三維不均勻網格陣列網格的允許擴展方向。6. 1根據線寬和線間距設置同層擴展的允許擴展方向；遍歷步驟(2)得到的障礙列表obsList，在橫坐標集合xset中搜索依據線寬和線 間距約束擴展的障礙邊界的左邊界和右邊界，在縱坐標集合yset中搜索依據線寬和線間 距約束擴展的障礙邊界的上邊界和下邊界，設置位於左邊界上的網格點不可向右擴展，位 於右邊界上的網格點不可向左擴展；位於上邊界的網格點不可向下擴展，位於下邊界上的 網格點不可向上擴展，並設置由該邊界所圍成矩形內部的所有網格點為不合法網格點。6. 2根據通孔設計規則約束設置跨層擴展的允許擴展方向；遍歷步驟(2)得到的障礙列表obsList，在橫坐標集合xset中搜索依據通孔大小 和通孔間距擴展的障礙邊界的左邊界和右邊界，在縱坐標集合yset中搜索依據通孔大小 和通孔間距擴展的障礙邊界的上邊界和下邊界，設置由上述左邊界，右邊界，上邊界和下邊 界所圍成矩形內部的網格點不能向相鄰層擴展，並設置相鄰層在對應區域內的網格不能向 該層擴展。(7)採用k*搜索算法對三維不均勻網格陣列進行布線路徑的搜索；在搜索過程開始時，將起始點集合S中的所有點按照該點到終止點集合T中點的 最短距離有序地插入待擴展點的鍊表中，A*算法停止的條件是當前搜索到的網格在終止點 集合T中。然後，將搜索到的路徑進行保存。在多層布線模式中，網格點除了向同層相鄰的 網格點擴展之外還可以向相鄰層擴展。A*搜索算法的具體實現步驟如下7. 1創建待擴展點的鍊表，保存所有已生成而未擴展的點；以及封閉鍊表，記錄已 訪問過的點；7. 2將起始點集合中的所有點按照該點到終止點集合中點的最短距離有序地列入 待擴展點的鍊表中；7. 3在上述待擴展點的鍊表中讀取擴展代價最小的點n，並判斷點η是否在終止點 集合中；是，結束搜索，否，繼續下面的步驟；7. 4對點η進行擴展，並對擴展後得到的點χ進行判斷
若點χ在待擴展點的鍊表中，比較點χ的不同路徑的擴展代價，若該擴展代價小於 待擴展點的鍊表中的擴展代價，用該擴展代價更新待擴展點的鍊表中的擴展代價，並將點X 放入待擴展點的鍊表中；若點X在封閉鍊表中，比較點X的不同路徑的擴展代價，若該擴展代價小於封閉鏈 表中的擴展代價，用該擴展代價更新封閉鍊表中的擴展代價，並將點X放入待擴展點的鏈 表中；若點χ既不在待擴展點的鍊表中，也不在封閉鍊表中；求解點χ的擴展代價，並將 點X放入待擴展點的鍊表中；7. 5將點η放入到封閉列表中；7. 6按照擴展代價將待擴展點的鍊表中的各點進行排序，重複步驟7. 3 7. 6。(8)輸出搜索結果；如果搜索成功，輸出搜索到的路徑；否則返回布線失敗。下面通過本發明的一具體實施例，對本發明的實現過程作進一步地說明。本實施例是採用本發明所述考慮通孔的基於不均勻網格的多層布線方法，使用 C++語言在LINUX/UNIX環境下開發實現的。本實施例的實現程序是以布線區域內的障礙 信息、待布線網信息以及工藝信息為輸入；輸出為搜索到的布線路徑。該程序的具體執行流 程(1)程序讀入布線信息程序讀入不局限於以配置文件形式提供的布線區域大小、布線區域內的障礙信 息、待布線網信息和工藝信息。其中，待布線網信息包括該待布線網的可用布線層，布線 區域大小和布線模式，即該線網可以在哪幾層金屬層上布線，布線區域的最大邊界，以及 點到點模式或模塊到模塊模式。若布線模式為點到點模式，布線信息要提供布線的起點 和終點；否則提供布線起始模塊和終止模塊，起始模塊和終止模塊均為直角多邊形，由多 邊形所在的布線層號和頂點坐標表示。工藝信息主要包括該布線層層數sizeZ，布線區 域允許的最小線寬值lineW[sizeZ]，通孔直徑大小viaWtsizeZ]，允許最小的線到線間距 值ltol [sizeZ]，允許最小的線到通孔間距值ltoV[sizeZ]，允許最小的通孔到通孔間距值 vtov [sizeZ]，這些大小和間距信息均為數組，數組的大小等於sizeZ，下標表示對應的布線 層層號。(2)建立障礙列表obsList，並將其中的每一個多邊形障礙都轉化為矩形障礙；程序根據步驟(1)讀入的信息建立布線過程所必須的數據結構，主要包括障礙列 表obsList，其中所有障礙的形狀均為直角多邊形，由該直角多邊形所在的布線層層號和直 角多邊形的頂點坐標表示，每個頂點由其橫坐標和縱坐標表示，同時障礙還包括一個表示 其是否是通孔的屬性即通孔或非通孔屬性。然後，調用多邊形到矩形的轉化程序將障礙列 表中所有的直角多邊形障礙轉化為多個矩形障礙，同時保留相應的是否是通孔的屬性。(3)擴展障礙邊界3. 1初始化橫坐標集合xset和縱坐標集合yset。3. 2依據線寬和線間距約束擴展障礙邊界遍歷由步驟(2)得到的障礙列表obsList，設當前遍歷到的障礙所在的層號為z， 若該障礙為非通孔障礙，將其上邊界，下邊界，左邊界，右邊界分別按照距離lineWz/2+ltolz進行擴展(如圖4所示)；若該障礙為通孔障礙，將其上邊界，下邊界，左邊界，右邊界分別 按照距離1^1謂2/2+1切\進行擴展(如圖5所示)。然後，將擴展障礙的左邊界和右邊界 對應的橫坐標添加到xset中，擴展障礙的上邊界和下邊界對應的縱坐標添加到yset中。3. 3依據通孔大小和通孔間距約束擴展障礙邊界遍歷由步驟(2)得到的障礙列表obsList，設當前遍歷到的障礙所在的層號為z， 若該障礙為非通孔障礙，將其上邊界，下邊界，左邊界，右邊界分別按照距離ViaWz/2+ltovz 進行擴展(如圖6所示)；若該障礙為通孔障礙，將其上邊界，下邊界，左邊界，右邊界分別 按照距離￥化12/2+對0\進行擴展(如圖7所示)。然後，將擴展障礙的左邊界和右邊界對 應的橫坐標添加到xset中，擴展障礙的上邊界和下邊界對應的縱坐標添加到yset中。(4)設置布線起始點集合和終止點集合4. 1初始化起始點集合S和終止點集合T。4. 2若布線模式為點到點模式，則將布線起點加入起始點集中，將布線終點加入終 止點集中；4. 3若布線模式為模塊到模塊模式4. 3. 1將起始模塊和終止模塊通過多邊形到矩形的轉化程序分別轉化至少一個矩 形模塊，並分別將各矩形模塊相應地添加到起始矩形鍊表sList和終止矩形鍊表tList中。4. 3. 2初始化一個點集P，分別將步驟(4. 3. 1)得到的起始矩形鍊表sList和終止 矩形鍊表tList賦給矩形鍊表list，調用下面步驟(4. 3. 3) (4. 3. 4)將矩形鍊表list轉 化為點集P，然後分別將P賦值給相應的起始點集S和終止點集T。4. 3. 3遍歷矩形鍊表list，從當前遍歷的矩形的屬性中讀取矩形的左邊界left， 右邊界right，下邊界bottom，上邊界top。然後，將left+width/2和right-width/2依次 添加到橫坐標集合中，將bottom+width/2和top-width/2依次添加到縱坐標集合中，其中 width由步驟(1)讀入。4. 3. 4將矩形邊界上和矩形內部的網格點加入到點集中步驟(3)得到的橫坐標集合xset和縱坐標集合yset中橫坐標對應的垂直線和各 縱坐標對應的水平線相交得到一系列網格點，將位於矩形模塊內部的網格點加入到點集P 中；並將橫坐標集合xset中各橫坐標對應的垂直線與矩形模型的上下邊界的交點加入到P 中，將縱坐標集合yset中的縱坐標對應的水平線與矩形左右邊界的交點加入P中，如圖8 所示，圖中黑色的點2都加入到點集P中，矩形框1為起始點矩形模塊。依上述步驟設置布線起始點集合和終止點集合的目的是，由於同層擴展擴展到矩 形模塊時首先擴展到矩形模塊邊界，而跨層擴展有可能直接擴展到模塊的內部，所以位於 模塊邊界上和內部的點都要加入點集中。(5)構造三維不均勻網格根據步驟(3)得到的橫坐標集合xset和縱坐標集合yset，以及布線層數構造三 維數組Info[sizeXXsizeYXsizeZ]，其中SizeX是數組的列數，sizeY是數組的行數，sizeZ是布線 層數。橫坐標集合xset中的一個元素為布線區域內的一個橫坐標，對應於一個布線層內 的一條縱向延長線，集合xset中的所有元素對應一個布線層內的多條縱向延長線。同樣， 縱坐標集合yset中的所有元素對應一個布線層內的多條橫向延長線。多條縱向延長線和 多條橫向延長線相交，將一個布線層劃分為一個不均勻二維網格陣列，將該不均勻網格映射到所有層中，則形成一個三維不均勻網格陣列，如圖9所示，每一個網格對應三維數組 Info[sizeXXsizeYXsizeZ]的一個元素，sizeX等於xset中元素的個數，sizeY等於yset中元素的 個數。(6)設置網格的允許擴展方向6. 1根據線寬和線間距設置同層擴展的允許擴展方向遍歷障礙列表obsList，在xset中搜索按照步驟(3)中3. 1擴展的左右邊界，在 yset中搜索根據步驟(3)中3. 1擴展的上下邊界，設置位於左邊界上的網格點為不可向右 擴展，位於右邊界上的網格點不可向左擴展；位於上邊界的網格點不可向下擴展，位於下邊 界上的網格點不可向上擴展，並設置由該邊界所圍成矩形內部的所有網格點為不合法網格
點ο6. 2根據通孔設計規則約束設置跨層擴展的允許擴展方向在xset中搜索按照步驟(3)中3. 2擴展的左右邊界，在yset中搜索根據步驟(3) 中3. 2擴展的上下邊界，設置由該邊界所圍成矩形內部的網格點不能向相鄰層擴展，並設 置相鄰層在對應區域內的網格不能向該層擴展。(7)基於上述允許擴展方向，採用A*算法對三維不均勻網格進行布線路徑搜索採用A*搜索算法對三維不均勻網格進行布線路徑的搜索，在搜索過程開始時，要 將起始點集中的所有點按照該點到終止點集中點的最短距離有序地插入待擴展點的鍊表 中，A*算法停止的條件是當前搜索到的網格在終止點集T中。並將搜索到的路徑進行保存。 在多層布線模式中，網格點除了向同層相鄰的網格點擴展之外還可以向相鄰層擴展。(8)輸出搜索結果如果布線成功，輸出連線路徑，否則，輸出布線失敗。本發明所述考慮通孔的基於不均勻網格的多層布線方法，根據已有的布局結果和 工藝信息，將布線區域劃分成三維不均勻網格陣列，然後，基於已設置的三維不均勻網格陣 列的允許擴展方向，利用路徑搜索方法完成布線。本發明能夠處理不同布線層的不同線寬 和最小間距，同時滿足通孔的設計規則約束，解決了現有集成電路多層布線存在的問題。以上，僅為本發明的較佳實施例，但本發明的保護範圍並不局限於此，任何熟悉本 技術領域的技術人員在本發明揭露的技術範圍內，可輕易想到的變化或替換，都應涵蓋在 本發明的保護範圍之內。因此，本發明的保護範圍應該以權利要求所界定的保護範圍為準。
權利要求
一種考慮通孔的基於不均勻網格的多層布線方法，其特徵在於，包括以下步驟(1)讀入布線區域內的障礙信息、待布線網信息和工藝信息；(2)依據上述障礙信息建立並規範障礙列表；(3)擴展障礙列表中各障礙的邊界；(4)設置起始點集合和終止點集合；(5)構造三維不均勻網格陣列；(6)設置三維不均勻網格陣列的允許擴展方向；(7)基於上述允許擴展方向，採用A*算法對三維不均勻網格進行布線路徑搜索；(8)輸出搜索路徑。
2.根據權利要求1所述考慮通孔的基於不均勻網格的多層布線方法，其特徵在於，步 驟(1)中，所述待布線網信息包括該待布線網的可用布線層信息，布線區域大小信息以及 起始點和終止點信息或起始模塊和終止模塊信息；所述工藝信息包括待布線網的布線層層數，布線區域允許的最小線寬值，各布線層通 孔直徑大小，允許最小的線到線間距值，允許最小的線到通孔間距值，允許最小的通孔到通 孔間距值。
3.根據權利要求1所述考慮通孔的基於不均勻網格的多層布線方法，其特徵在於，步 驟(2)中，所述障礙列表中的每個列表元素是由該障礙所在布線層層號，頂點坐標，以及該 障礙是通孔或非通孔來表示，
4.根據權利要求1所述考慮通孔的基於不均勻網格的多層布線方法，其特徵在於，步 驟(2)的具體實現步驟如下2. 1根據步驟(1)中所述的障礙信息建立障礙列表；2. 2遍歷障礙列表，調用多邊形到矩形的轉化程序將每一個多邊形障礙轉化為至少一 個矩形障礙；2.3刪除障礙列表中存儲的原多邊形障礙，將轉化得到的矩形障礙添加到障礙列表中。
5.根據權利要求1或2所述考慮通孔的基於不均勻網格的多層布線方法，其特徵在於， 步驟(3)具體實現如下3.1初始化橫坐標集合和縱坐標集合；3. 2遍歷步驟(2)得到的障礙列表，將非通孔矩形障礙的每一個邊界分別按照「線寬 /2+線間距」的距離進行擴展，得出垂直擴展邊界和水平擴展邊界；將通孔矩形障礙的每一 個邊界按照「線寬/2+線到通孔的間距」的距離進行擴展，得出垂直擴展邊界和水平擴展邊 界；3. 3遍歷步驟(2)得到的障礙列表，將非通孔矩形障礙的每一個邊界分別按照「通孔直 徑/2+線到通孔間距」的距離進行擴展，得出垂直擴展邊界和水平擴展邊界；將通孔矩形障 礙的每一個邊界分別按照「通孔直徑/2+通孔到通孔的間距」的距離進行擴展，得出垂直擴 展邊界和水平擴展邊界；3. 4將(3. 2)和(3. 3)步中的所有垂直擴展邊界的橫坐標加入到橫坐標集合中，所有水 平擴展邊界的縱坐標加入到縱坐標集合中。
6.根據權利要求1或2所述考慮通孔的基於不均勻網格的多層布線方法，其特徵在於， 步驟(4)具體實現如下`4. 1初始化起始點集合和終止點集合；`4. 2若布線模式為點到點模式，將布線起點添加到起始點集中，將布線終點添加到終止 點集中；若布線模式為模塊到模塊模式，進行步驟4. 2. 1 4. 2. 6 ；`4. 2. 1調用多邊形到矩形的轉化程序分別將起始模塊和終止模塊轉化為至少一個矩形 模塊，並將轉化後的矩形模塊分別添加到起始矩形鍊表和終止矩形鍊表中；`4. 2. 2分別遍歷起始矩形鍊表和終止矩形鍊表，讀取各矩形模塊的左邊界，右邊界，下 邊界和上邊界，並依據所述的工藝信息將每一個邊界分別按照「線寬/2」的距離進行收縮， 得出垂直收縮邊界和水平收縮邊界；`4. 2. 3將垂直收縮邊界的橫坐標添加到橫坐標集合中，將水平收縮邊界的縱坐標添加 到縱坐標集合中；`4. 2. 4分別對縱坐標集合和橫坐標集合中的坐標進行排序並去重； 4. 2. 5將橫坐標集合中各橫坐標對應的垂直線分別與起始矩形鍊表中每個矩形模塊的 上邊界和下邊界的交點，縱坐標集合中各縱坐標對應的水平線分別與起始矩形鍊表中每個 矩形模塊的左邊界和右邊界的交點，以及橫坐標集合中各橫坐標對應的垂直線和縱坐標集 合中的各縱坐標對應的水平線在起始模塊內部的交點添加到起始點集合中；`4. 2. 6將橫坐標集合中各橫坐標對應的垂直線與終止矩形鍊表中每個矩形模塊的上邊 界和下邊界的交點，縱坐標集合中各縱坐標對應的水平線與終止矩形鍊表中每個矩形模塊 的左邊界和右邊界的交點，以及橫坐標集合中各橫坐標對應的垂直線和縱坐標集合中的各 縱坐標的水平線在終止模塊內部的交點添加到終止點集合中。
7.根據權利要求1或2所述考慮通孔的基於不均勻網格的多層布線方法，其特徵在於， 所述的三維不均勻網格陣列表示為由步驟(3)所述的橫坐標集合，所述的縱坐標集合，以 及所述布線層層數構成的三維數組。
8.根據權利要求1或2所述考慮通孔的基於不均勻網格的多層布線方法，其特徵在於， 步驟(6)具體實現如下`6. 1設置同層擴展的允許擴展方向；遍歷步驟(2)得到的障礙列表，若該矩形障礙是非通孔障礙，設置三維不均勻網格陣 列中所有在該矩形障礙按照「線寬/2+線間距」擴展的左，右，上，下邊界上的網格點，分別 不可向右，左，下，上擴展，並設置由該左，右，上，下邊界所構成的矩形內部的所有網格點為 不合法網格點；若該障礙是通孔障礙，設置三維不均勻網格陣列中所有在該障礙按照「通孔 直徑/2+線到通孔間距」擴展的左，右，上，下邊界上的網格點，分別不可向右，左，下，上擴 展，並設置由該左，右，上，下邊界所構成的矩形內部的所有網格點為不合法網格點； 6. 2設置跨層擴展的允許擴展方向；遍歷步驟(2)得到的障礙列表，若該矩形障礙是非通孔障礙，設置三維不均勻網格陣 列中所有在該障礙按照「線寬/2+線到通孔間距」擴展的左，右，上，下邊界所構成的矩形內 部的網格點不能向相鄰層的網格擴展，並設置相鄰層在對應區域內的網格點不能向該層擴 展；若該障礙是通孔障礙，設置三維不均勻網格陣列中所有在該障礙按照「通孔直徑/2+通 孔到通孔間距」擴展的左，右，上，下邊界所構成的矩形內部的網格點不能向相鄰層的網格 擴展，並設置相鄰層在對應區域內的網格點不能向該層擴展。
9.根據權利要求1所述考慮通孔的基於不均勻網格的多層布線方法，其特徵在於，步驟(7) A*算法進行路徑搜索的具體實現步驟如下'7. 1創建待擴展點的鍊表，保存所有已生成而未擴展的點；以及封閉鍊表，記錄已訪問 過的點；'7. 2將起始點集合中的所有點按照該點到終止點集合中點的最短距離有序地列入待擴 展點的鍊表中；'7. 3在上述待擴展點的鍊表中讀取擴展代價最小的點n，並判斷點η是否在終止點集合 中；是，結束搜索，否，繼續下面的步驟；'7. 4對點η進行擴展，並對擴展後得到的點χ進行判斷若點χ在待擴展點的鍊表中，比較點χ的不同路徑的擴展代價，若該擴展代價小於待擴 展點的鍊表中的擴展代價，用該擴展代價更新待擴展點的鍊表中的擴展代價，並將具有新 的擴展代價的點χ轉移到鍊表中；若點χ在封閉鍊表中，比較點χ的不同路徑的擴展代價，若該擴展代價小於封閉鍊表中 的擴展代價，用該擴展代價更新封閉鍊表中的擴展代價，並將點χ放入待擴展點的鍊表中； 若點χ既不在待擴展點的鍊表中，也不在封閉鍊表中；求解點χ的擴展代價，並將點χ 放入待擴展點的鍊表中；'7. 5將點η放入到封閉列表中；'7. 6按照擴展代價將待擴展點的鍊表中的各點進行排序，重複步驟7. 3 7. 6。
10.根據權利要求1所述考慮通孔的基於不均勻網格的多層布線方法，其特徵在於，步 驟(8)依據步驟(7)的搜索結果；搜索成功，輸出搜索到的路徑，搜索失敗，輸出布線失敗。
全文摘要
本發明公開一種考慮通孔的基於不均勻網格的多層布線方法，主要是為了解決現有集成電路多層布線存在的困難而設計。本發明依據讀入的障礙信息建立並規範障礙列表；然後，分別依據工藝信息線寬和線間距約束以及通孔大小和通孔間距約束擴展障礙邊界，同時設置起始點集合和終止點集合，構造三維不均勻網格陣列；最後，基於已設置的三維不均勻網格陣列的允許擴展方向，採用A*算法進行路徑搜索，並輸出搜索路徑。本發明同時支持點到點布線模式和模塊到模塊布線模式，通過將點或模塊統一轉化為點的集合，點的集合中各點的選取保證了在多層搜索中能夠找到最短路徑，此外，本發明通過構造三維不均勻網格陣列有效的解決了現有集成電路多層布線存在的問題。
文檔編號G06F17/50GK101957876SQ20101028203
公開日2011年1月26日 申請日期2010年9月15日 優先權日2010年9月15日
發明者周強, 姚海龍, 楊帆, 蔡懿慈 申請人:清華大學