[發(fā)明專利]X結(jié)構(gòu)下超大規(guī)模集成電路總體布線方法

有效

• 申請?zhí)枺?/td>: 201410123885.4
• 申請日: 2014-03-31
• 公開（公告）號: CN103902774B
• 公開（公告）日: 2017-01-25
• 發(fā)明（設(shè)計）人: 陳國龍;郭文忠;劉耿耿
• 申請（專利權(quán)）人: 福州大學(xué)
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 福州元創(chuàng)專利商標(biāo)代理有限公司35100
• 代理人: 蔡學(xué)俊

1.一種X結(jié)構(gòu)下超大規(guī)模集成電路總體布線方法，其特征在于，包括以下步驟：

（1）初始階段，采用Steiner最小樹方法將多端線網(wǎng)分解為多個兩端線網(wǎng)，并對可連接的兩端線網(wǎng)采用X結(jié)構(gòu)邊連接，即進(jìn)行初始布線，得到近似的布線擁擠分布情況；

（2）主階段，從所述近似的初始布線結(jié)果中選取最擁擠區(qū)域作為當(dāng)前布線區(qū)域，為當(dāng)前布線區(qū)域構(gòu)建整數(shù)線性規(guī)劃模型并求解；繼而不斷擴(kuò)大布線區(qū)域并依次求解，直至布線區(qū)域擴(kuò)張至整個芯片為止；

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

2.根據(jù)權(quán)利要求1所述的X結(jié)構(gòu)下超大規(guī)模集成電路總體布線方法，其特征在于，在主階段中，所述整數(shù)線性規(guī)劃模型為：

其中Wl_j表示候選解y_j的線長；std(?)表示所有邊擁擠度的標(biāo)準(zhǔn)差，即表示擁擠度分布的均勻情況；cong(?)表示e₁到e_p的擁擠度集合，α₁和α₂分別表示兩個優(yōu)化目標(biāo)的權(quán)重大小；β表示懲罰項，用以對違反布線邊容量約束的方案進(jìn)行一定程度的懲罰；y_j表示候選解被選擇與否，其取值為0或1，而表示對于同一線網(wǎng)N_k的候選解的取值之和為1，確保只有一個候選解被選取；n表示線網(wǎng)總數(shù)，e_i表示總體布線網(wǎng)格邊，a_ij表示候選解j是否通過邊e_i，C(e_i)表示邊e_i的最大允許走線數(shù)，p表示總體布線網(wǎng)格邊數(shù)，r表示違反約束的邊數(shù)，t表示候選解的總數(shù)。

3.根據(jù)權(quán)利要求2所述的X結(jié)構(gòu)下超大規(guī)模集成電路總體布線方法，其特征在于，在主階段中，采用改進(jìn)的粒子群優(yōu)化方法求解所述整數(shù)線性規(guī)劃模型，包括以下步驟：

1）編碼粒子，每個粒子代表一個解；

2）對每個粒子，采用變異算子進(jìn)行變異操作，采用交叉算子與歷史最優(yōu)粒子進(jìn)行交叉操作，采用交叉算子與全局最優(yōu)粒子進(jìn)行交叉操作，并分別對變異、交叉后的粒子編碼進(jìn)行檢查操作；

3）采用如下的適應(yīng)度函數(shù)fitness計算更新后每個粒子的適應(yīng)度值：

4）如果粒子的適應(yīng)度值大于粒子歷史最優(yōu)值，更新該粒子為歷史最優(yōu)粒子，如果粒子的適應(yīng)度值大于種群全局最優(yōu)值，更新該粒子為種群全局最優(yōu)粒子。

4.根據(jù)權(quán)利要求1所述的X結(jié)構(gòu)下超大規(guī)模集成電路總體布線方法，其特征在于，在后處理階段中，所述布線邊代價按如下方法重新定義：如果邊e是待布線網(wǎng)i所隸屬的多端線網(wǎng)中已走線的邊，則布線邊代價為0，否則布線邊代價為以下兩項之和：邊e的線長（在本發(fā)明中等于1）、邊e的已走線數(shù)與邊e的布線容量之商。