[發明專利]基于多子群競爭PSO的限制長度的X結構Steiner最小樹構建方法

在審

• 申請號: 202210833830.7
• 申請日: 2022-07-14
• 公開（公告）號: CN115630605A
• 公開（公告）日: 2023-01-20
• 發明（設計）人: 劉耿耿;周茹平;郭文忠;陳國龍
• 申請（專利權）人: 福州大學
• 主分類號: G06F30/3947
• 分類號: G06F30/3947;G06F30/398;G06N3/006;G06F111/04
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊;薛金才

本發明提供了一種基于多子群競爭PSO的限制長度的X結構Steiner最小樹構建方法，包括步驟如下：步驟1：加載電路數據；步驟2：進入MSCPSO搜索階段；步驟3：使用極限穿障策略；步驟4：使用雙精煉策略：步驟5：輸出LRXSMT作為布線方案，結束算法。應用本技術方案可實現以充分利用障礙內部的可布線資源，從而有效縮短布線長度。

技術領域

本發明涉及集成電路計算機輔助設計技術領域，特別是一種基于多子 群競爭PSO的限制長度的X結構Steiner最小樹構建方法。

背景技術

隨著超大規模集成電路(Very Large Scale Integration,VLSI)問題 規模的擴大，芯片密度急劇增加，功能愈發復雜，越來越多的組件(如知識 產權保護模塊、宏單元、預布線線網等)集成到一個芯片上。在VLSI物理 設計的總體布線階段，這些在布線過程中無法移動的組件被視為障礙，成 為無法忽視的因素。以往不考慮障礙物的布線算法已經難以滿足實際的芯 片設計需求。一些學者研究繞障布線，即布線邊完全繞開障礙物并連通線網。然而，在實際的多層布線中，障礙只占據了設備層以及某些底層金屬 層，即障礙內部仍然存在可布線區域，并不會完全阻斷布線。但是，障礙 內部的導線過長會引起噪音問題，信號在其中傳輸可能因此衰減或失真。 為避免信號的衰減或失真，一般需要使用中繼器對信號進行再生和放大。 又由于障礙已經占據了設備層，故障礙內部無法放置中繼器，為此，需要 限制障礙內部的導線長度，使信號在失真之間到達障礙外部。綜上，研究 限制長度的布線問題能夠保證時序收斂，有效縮短布線總線長，節約布線 資源，從而提高芯片質量。

總體布線多端線網的最佳連接模型是Steiner最小樹(Steiner Minimum Tree,SMT)。而SMT的構造中，布線邊的互連模型通常為直角結 構，即只能以0°或90°方向布線。然而，直角結構的布線方向過于單一， 限制了SMT問題的解空間，在線長這一重要指標上的優化能力已步入瓶頸 期。相較于傳統的直角結構，以X結構為代表的新興的非直角結構允許從0°、 90°、45°及135°四個方向進行布線，擴大了SMT解方案的搜索空間，更 有利于減少布線資源冗余，優化總線長，降低互連線時延。目前，隨著VLSI 芯片制造工藝的進步，X結構已被成功應用于SMT的構造中，成為總體布線 算法的研究熱點。然而，目前僅有少量工作研究限制長度的X結構Steiner 最小樹(Length-Restricted X-architecture SteinerMinimum Tree, LRXSMT)。

以往的研究工作常用精確算法構造SMT。精確算法能夠保證求得準確的 最優解，然而其復雜度過高，難以求解大規模布線問題。后有學者嘗試使 用傳統啟發式算法構造SMT，但多使用貪心策略，算法極易陷入局部最優， 難以找到更高質量的解，無法滿足復雜性呈指數增長的VLSI物理設計的發 展需求。因此，學者們將目光聚焦于群智能算法。自然界中，個體通過簡 單的交互行為往往能實現群體的智能行為，群智能(SwarmIntelligence, SI)算法即是模擬這種生物現象所提出的智能計算技術，為復雜的優化問題 提供了新的解決思路。其中，粒子群優化算法(Particle Swarm Optimization,PSO)作為SI的代表之一，由于控制參數少，實現簡單，尋 優能力強，在眾多SI技術中脫穎而出，被用于解決VLSI布線問題，以期 突破傳統布線算法的瓶頸。然而將PSO應用于LRXSMT問題的工作中，PSO 存在因多樣性喪失而過早收斂的問題，且未能充分利用障礙內部的布線空間，算法的性能有很大的提升空間。

發明內容

有鑒于此，本發明的目的在于提供一種基于多子群競爭PSO的限制長 度的X結構Steiner最小樹構建方法，以充分利用障礙內部的可布線資源， 從而有效縮短布線長度。

為實現上述目的，本發明采用如下技術方案：基于多子群競爭PSO的 限制長度的X結構Steiner最小樹構建方法，其特征在于包括步驟如下：

步驟1：加載電路數據；

步驟2：進入MSCPSO搜索階段；