[發(fā)明專利]超大規(guī)模集成電路多層繞障Steiner最小樹構(gòu)造方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410124000.2
• 申請(qǐng)日: 2014-03-31
• 公開（公告）號(hào): CN103902775B
• 公開（公告）日: 2017-02-15
• 發(fā)明（設(shè)計(jì)）人: 郭文忠;陳國(guó)龍;劉耿耿
• 申請(qǐng)（專利權(quán)）人: 福州大學(xué)
• 主分類號(hào): G06F17/50
• 分類號(hào): G06F17/50;G06N3/12
• 代理公司: 福州元?jiǎng)?chuàng)專利商標(biāo)代理有限公司35100
• 代理人: 蔡學(xué)俊

1.一種超大規(guī)模集成電路多層繞障Steiner最小樹構(gòu)造方法，其特征在于，包括以下步驟：

步驟1：讀取基準(zhǔn)測(cè)試電路網(wǎng)絡(luò)數(shù)據(jù)，并按照層數(shù)和坐標(biāo)大小進(jìn)行升序排序；

步驟2：初始化種群規(guī)模、迭代次數(shù)等參數(shù)，對(duì)優(yōu)化參數(shù)進(jìn)行編碼并隨機(jī)產(chǎn)生初始種群；

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

步驟4：采用基于懲罰機(jī)制的適應(yīng)度計(jì)算函數(shù)計(jì)算新粒子的適應(yīng)度值，并判斷新粒子的適應(yīng)度值是否小于粒子的歷史最優(yōu)值，是則將新粒子更新為粒子的歷史最優(yōu)粒子，并轉(zhuǎn)步驟5，否則直接轉(zhuǎn)步驟5；

步驟5：判斷新粒子的適應(yīng)度值是否小于種群的全局最優(yōu)值，是則將新粒子更新為種群的全局最優(yōu)粒子，并轉(zhuǎn)步驟6，否則直接轉(zhuǎn)步驟6；

步驟6：判斷是否滿足迭代終止條件，是則輸出最終的布線樹，否則返回步驟3進(jìn)行下一次迭代。

2.根據(jù)權(quán)利要求1所述的超大規(guī)模集成電路多層繞障Steiner最小樹構(gòu)造方法，其特征在于，該方法采用適合X結(jié)構(gòu)和多層布線的邊點(diǎn)對(duì)編碼方法對(duì)X結(jié)構(gòu)多層Steiner樹進(jìn)行編碼：用布線樹的邊集合編碼相應(yīng)的Steiner樹，每條邊的編碼采用四位數(shù)字串表示，前兩位表示邊所連接兩引腳的引腳編號(hào)，第三位走線方式位pspc表示邊的偽Steiner點(diǎn)選擇方式，最后一位用以記錄布線邊走線是否穿越障礙物及其產(chǎn)生的通孔數(shù)，正數(shù)代表未穿越障礙物，負(fù)數(shù)代表穿越障礙物，數(shù)值大小代表通孔數(shù)。

3.根據(jù)權(quán)利要求2所述的超大規(guī)模集成電路多層繞障Steiner最小樹構(gòu)造方法，其特征在于，所述基于懲罰機(jī)制的適應(yīng)度計(jì)算函數(shù)F(X)為：

其中N(X)=cost(T)，S(X)=cost(T)，；e表示屬于布線樹T的邊，penalty(e)的計(jì)算公式f₁(x)為：

其中lb、ub是值大于1的自定義參數(shù)，x表示邊e編碼中的走線狀態(tài)位的數(shù)值，lmax表示布線層的最大編號(hào)；

cost(T)表示布線樹T的布線總代價(jià)，其計(jì)算公式為：

其中Odis(i,?j)表示引腳i和引腳j之間的距離，其計(jì)算公式為：

其中x_i、y_i和x_j、y_j分別表示引腳i的水平坐標(biāo)、垂直坐標(biāo)和引腳j的水平坐標(biāo)、垂直坐標(biāo)，min(xy)表示|x_i?–?x_j|和|y_i?–?y_j|之間的最小值，min(xy)?=?min(|x_i?–?x_j|,?|y_i?–?y_j|)，max(xy)表示|x_i?–?x_j|和|?y_i?–?y_j|之間的最大值，max(xy)?=?max(|x_i?–?x_j|,?|y_i?–?y_j|)；

C_via(i,?j)表示通孔代價(jià)，C_via(i,?j)?=?|z_i?–?z_j|×C_v，其中z_i、z_j分別表示引腳i、j所在布線層的Z軸坐標(biāo)，C_v為一參數(shù)。