[發明專利]X結構下超大規模集成電路總體布線方法

有效

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

技術領域

本發明屬于集成電路計算機輔助設計技術領域，具體涉及一種超大規模集成電路布線設計領域中高質量的X結構總體布線方法。

背景技術

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

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

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

發明內容

本發明的目的在于提供一種X結構下超大規模集成電路總體布線方法，該方法有利于提高布線方案的質量，且易于實現，使用效果好。

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

（1）初始階段，采用Steiner最小樹方法將多端線網分解為多個兩端線網，并對可連接的兩端線網采用X結構邊連接，即進行初始布線，得到近似的布線擁擠分布情況；

（2）主階段，從所述近似的初始布線結果中選取最擁擠區域作為當前布線區域，為當前布線區域構建整數線性規劃模型并求解；繼而不斷擴大布線區域并依次求解，直至布線區域擴張至整個芯片為止；

（3）后處理階段，重新定義布線邊代價，利用基于所述布線邊代價的迷宮算法對尚未布通的兩端線網進行布線，得到最終的總體布線結果。

進一步的，在主階段中，所述整數線性規劃模型為：