[發明專利]超大規模集成電路中高性能X結構多層總體布線方法

有效

• 申請號: 201711060869.5
• 申請日: 2017-11-02
• 公開（公告）號: CN107832519B
• 公開（公告）日: 2021-01-29
• 發明（設計）人: 劉耿耿;郭文忠;陳國龍
• 申請（專利權）人: 福州大學
• 主分類號: G06F30/394
• 分類號: G06F30/394;G06F30/398
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

本發明涉及一種超大規模集成電路中高性能X結構多層總體布線方法，在XGRouter布線器的基礎上，提供了包括：增加新類型的布線方式，子群優化算法與基于新布線代價的迷宮布線的結合，初始階段中預布線容量的縮減策略，設計動態資源調度策略，繼而引入了多層布線模型，簡化了XGRouter的整數線性規劃模型，最終構建了一種高性能的X結構多層總體布線器。通過在標準測試電路的仿真實驗結果表明，相對其他各類總體布線器，在多層總體布線中最重要的優化目標——溢出數和線長總代價兩個指標上均取得最佳效果。

技術領域

本發明涉及集成電路計算機輔助設計技術領域，特別是一種超大規模集成電路中高性能X結構多層總體布線方法。

背景技術

隨著半導體和互連線的大小不斷縮小，互連線嚴重影響很多關鍵的設計指標，因此，作為組織互連線的實際走線位置的布線階段在現今超大規模集成電路(very largescale integration,簡稱VLSI)物理設計中變得尤為重要。復雜的布線過程是由總體布線和詳細布線兩階段構成的。在總體布線中，每個線網的走線被分配到各個通道布線區域中，每個通道區域的布線問題得到明確定義。而詳細布線則給出了每個線網在通道區域的具體位置。因此，總體布線的質量嚴重影響詳細布線的成功率，進而對整個芯片的性能起到決定性的作用。

總體布線是超大規模集成電路物理設計中極為重要的一部分，因而學者們提出了很多有效的算法和總體布線技術，主要可分為串行算法和并行算法兩種，特別是以串行算法為代表的總體布線方法能夠處理大規模的問題。但串行算法對線網的布線順序或是布線代價的定義具有嚴重的依賴性，這一潛在特性嚴重影響了總體布線的質量。而以整數線性規劃為代表的并行算法能夠減少布線結果對線網順序的依賴性，取得質量較好的總體布線方案。這些以整數線性規劃為代表的部分方法在求解整數線性規劃模型是先將其松弛為線性規劃模型以減少求解規劃模型的時間復雜度，再利用隨機取整的方法將線性解轉換為非線性解，這樣導致隨機取整的過程所取得的布線方案可能嚴重偏離真正的解方案。

大部分總體布線算法都是以曼哈頓結構為模型基礎開展相關工作，而基于曼哈頓結構的優化策略在進行互連線線長優化時，由于繞線方向只能為水平和垂直，其優化能力受限。因此，有必要從根本入手，改變傳統的曼哈頓結構，故研究人員開始嘗試以非曼哈頓結構為基礎模型進行布線，實現芯片整體性能的優化。學者對能帶來可觀的線長減少量等物理設計指標提高的非曼哈頓結構已展開研究，特別是出現專門的工業聯盟推廣X結構，為這樣的研究提供實現和驗證基礎。目前關于X結構布線的研究主要包括兩方面：X結構布線樹的構造和X結構總體布線算法設計。隨著X結構的引入，布線算法設計變得更為的復雜。然而，一些關于X結構總體布線的研究主要集中在線長優化，這些算法是基于早期的Steiner樹構造方法，從而導致了這些X結構總體布線算法相對于曼哈頓結構總體布線算法的優化效果不明顯，甚至部分工作的布線結果相對曼哈頓結構的布線結果在線長總代價優化能力方面顯得更差。

隨著集成電路設計進入納米領域，布線金屬層數增加，線寬大幅度減少，而連線間距也大幅度減小,使電路的性能和密度得到了很大的提高，因此多層布線應運而生，并且引起了諸多研究機構的廣泛關注。而現有關于非曼哈頓結構總體布線問題的研究中，僅局限于單層結構總體布線問題的研究，據我們所知，尚未開展考慮到非曼哈頓結構、多層結構兩個條件的總體布線算法研究。

發明內容

本發明的目的在于提供一種超大規模集成電路中高性能X結構多層總體布線方法，以克服現有技術中存在的缺陷。

為實現上述目的，本發明的技術方案是：一種超大規模集成電路中高性能X結構多層總體布線方法，包括如下步驟：

步驟S1：在初始布線階段，建立X結構Steiner最小樹；

步驟S2：進行多端線網分解；

步驟S3：將初始布線階段的預布線容量縮減到原容量的一半；