[發明專利]超大規模集成電路多層繞障Steiner最小樹構造方法

有效

• 申請號: 201410124000.2
• 申請日: 2014-03-31
• 公開（公告）號: CN103902775B
• 公開（公告）日: 2017-02-15
• 發明（設計）人: 郭文忠;陳國龍;劉耿耿
• 申請（專利權）人: 福州大學
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06N3/12
• 代理公司: 福州元創專利商標代理有限公司35100
• 代理人: 蔡學俊

技術領域

本發明屬于集成電路計算機輔助設計技術領域，具體涉及一種X結構下帶粒子群優化的超大規模集成電路多層繞障Steiner最小樹構造方法。

背景技術

超大規模集成電路(very?large?scale?integration，VLSI)設計中多層繞障X結構Steiner最小樹(multilayer?obstacle-avoiding?X-architecture?Steiner?minimal?tree，ML-OAXSMT)問題是給定布線層上一系列布線引腳和障礙物集合，通過X結構邊連接每個布線層上的引腳且布線層之間借助通孔連接，在布線邊和通孔不穿越障礙物的約束下，構建布線總代價最小的Steiner樹。ML-OAXSMT問題是考慮到障礙物、X結構、多層等三個條件的Steiner最小樹模型。

Steiner最小樹作為ML-OAXSMT問題的基礎模型是布線中多端線網連接的最佳模型。近年來超大規模集成電路設計中芯片會存在宏單元、IP預布好的線網等布線障礙物，在此基礎上考慮到障礙物的Steiner最小樹問題受到廣泛的關注。單層繞障Steiner最小樹的構建方法主要包含四類：先構造再替換法、不確定性算法、基于生成圖的方法、精確算法。第一種方法主要是在不考慮障礙物的情況下先構建布線端點集合的Steiner最小樹，然后對其中穿過障礙物的邊替換成經過障礙物邊界的布線邊，該類算法過程簡單，但容易獲得較低質量的布線方案。不確定性算法是基于一些元啟發式策略的，主要包括基于局部搜索的蟻群算法和基于粒子群優化算法。很多繞障算法都屬于第三類基于生成圖的方法，其中生成圖一般包含引腳端點和部分障礙物端點，在一定程度上減低了問題求解空間的復雜度，并在此基礎上取得線長與運行時間較為折中的方案。第四種方法是能夠得到準確方案的精確算法，主要是基于GeoSteiner方法的兩階段算法，首先構造考慮障礙的完全Steiner樹(full?Steiner?trees，FSTs)，繼而構建整數規劃模型并利用分支定界策略從中選取若干FSTs用于構建最后的考慮障礙物的矩形Steiner最小樹。

目前關于布線樹的相關研究工作主要集中在曼哈頓結構，但基于曼哈頓結構進行線長與時延的優化，由于其布線走向有限，不能夠充分地利用布線區域，導致互連線資源的過分冗余。故基于曼哈頓結構的優化策略在進行互連線線長優化時，其優化能力受限。因此，有必要從根本入手，改變傳統的曼哈頓結構，故研究人員開始嘗試以非曼哈頓結構為基礎模型進行布線，實現芯片整體性能的優化。?學者提出了在X結構下的布線樹和布線算法的一些挑戰和機遇，同時給出該結構下良好的展望，并指出在X結構下，Steiner最小樹問題仍是最為關鍵的問題之一。學者對能帶來可觀的線長減少量等物理設計指標提高的非曼哈頓結構已展開研究，特別是出現專門的工業聯盟推廣X結構，為這樣的研究提供實現和驗證基礎。但對于能帶來線長、通孔、功耗等目標優化的非曼哈頓結構的繞障工作研究較少。

隨著集成電路設計進入納米領域，布線金屬層數增加，線寬大幅度減少，而連線間距也大幅度減小，使電路的性能和密度得到了很大的提高，因此多層布線應運而生，并且引起了諸多研究機構的廣泛關注。目前多層Steiner最小樹工作大多集中在基于曼哈頓結構，即求解多層矩形Steiner最小樹的構建問題。而對于非曼哈頓結構下多層繞障Steiner最小樹的構建工作是考慮到線長和通孔數的優化，分別對每個布線層進行繞障Steiner最小樹的構建工作，再為每兩個毗鄰布線層尋找最短的連接路徑。但該方法將多層繞障Steiner最小樹問題轉換為多個單層繞障Steiner最小樹問題，未能從多層結構的全局角度尋找解方案，很大程度影響布線解的質量。

發明內容

本發明的目的在于克服現有技術的不足，提供一種超大規模集成電路多層繞障Steiner最小樹構造方法，該方法有利于降低布線總代價，提高布線樹的質量。

為實現上述目的，本發明的技術方案是：一種超大規模集成電路多層繞障Steiner最小樹構造方法，包括以下步驟：

步驟1：讀取基準測試電路網絡數據，并按照層數和坐標大小進行升序排序；

步驟2：初始化種群規模、迭代次數等參數，對優化參數進行編碼并隨機產生初始種群；

步驟3：采用粒子更新公式更新每個粒子的位置和速度，得到新粒子；

步驟4：采用基于懲罰機制的適應度計算函數計算新粒子的適應度值，并判斷新粒子的適應度值是否小于粒子的歷史最優值，是則將新粒子更新為粒子的歷史最優粒子，并轉步驟5，否則直接轉步驟5；