[發(fā)明專(zhuān)利]一種兩步式X結(jié)構(gòu)Steiner最小樹(shù)構(gòu)建方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010410094.5
• 申請(qǐng)日: 2020-05-14
• 公開(kāi)（公告）號(hào): CN111582431B
• 公開(kāi)（公告）日: 2022-07-08
• 發(fā)明（設(shè)計(jì)）人: 劉耿耿;陳曉華;郭文忠;陳國(guó)龍
• 申請(qǐng)（專(zhuān)利權(quán)）人: 福州大學(xué)
• 主分類(lèi)號(hào): G06N3/00
• 分類(lèi)號(hào): G06N3/00
• 代理公司: 福州元?jiǎng)?chuàng)專(zhuān)利商標(biāo)代理有限公司 35100
• 代理人: 錢(qián)莉;蔡學(xué)俊

本發(fā)明涉及集成電路計(jì)算機(jī)輔助設(shè)計(jì)技術(shù)領(lǐng)域中針對(duì)超大規(guī)模集成電路（Very Large Scale Integration,VLSI）的一種兩步式X結(jié)構(gòu)Steiner最小樹(shù)構(gòu)建方法，充分利用X結(jié)構(gòu)模型和粒子群優(yōu)化技術(shù)的優(yōu)勢(shì)，分兩步進(jìn)行實(shí)現(xiàn)：1)社會(huì)學(xué)習(xí)離散粒子群搜索階段，其中包括使用能夠保持粒子最優(yōu)拓?fù)湫畔⒌倪咟c(diǎn)對(duì)編碼策略，設(shè)計(jì)考慮線長(zhǎng)的適應(yīng)值函數(shù)，采用了一種混沌下降變異策略和新的社會(huì)學(xué)習(xí)策略以設(shè)計(jì)出新的離散粒子群更新公式；2）線長(zhǎng)優(yōu)化階段，其中設(shè)計(jì)了一種基于局部拓?fù)鋬?yōu)化的策略以最小化X結(jié)構(gòu)Steiner樹(shù)的線長(zhǎng)。本發(fā)明不僅能保證產(chǎn)生的線網(wǎng)總線長(zhǎng)較短，并且具有極強(qiáng)的穩(wěn)定性，從而構(gòu)建出高質(zhì)量的X結(jié)構(gòu)Steiner最小樹(shù)。

技術(shù)領(lǐng)域

本發(fā)明涉及集成電路計(jì)算機(jī)輔助設(shè)計(jì)技術(shù)領(lǐng)域，特別是針對(duì)超大規(guī)模集成電路中的一種兩步式X結(jié)構(gòu)Steiner最小樹(shù)構(gòu)建方法。

背景技術(shù)

SMT(Steiner Minimum Tree,SMT)問(wèn)題是在給定引腳集合的基礎(chǔ)上，通過(guò)引入額外的點(diǎn)(Steiner點(diǎn))來(lái)尋找一棵連接這些引腳集合的具有最小代價(jià)的布線樹(shù)。因此，SMT的構(gòu)建是超大規(guī)模集成電路(Very Large Scale Integration,VLSI)布線中的重要環(huán)節(jié)之一。

隨著VLSI制造工藝的不斷進(jìn)步和發(fā)展，互連線效應(yīng)逐漸成為影響芯片性能的重要因素。然而，目前大多數(shù)布線算法的研究都是基于曼哈頓結(jié)構(gòu)展開(kāi)的，這種基于曼哈頓結(jié)構(gòu)的布線模型要求引腳之間的走線方式只能是水平方向和垂直方向，導(dǎo)致芯片中互連線的線長(zhǎng)優(yōu)化更加困難。而非曼哈頓結(jié)構(gòu)由于具有更多的走線方向，能夠更加充分利用布線資源，從而提高布線質(zhì)量，改善芯片的性能。

為了更好地開(kāi)展非曼哈頓結(jié)構(gòu)下的布線工作，非曼哈頓結(jié)構(gòu)Steiner最小樹(shù)的構(gòu)建是關(guān)鍵的一步。X結(jié)構(gòu)是非曼哈頓結(jié)構(gòu)的一種，除了水平和垂直方向，引腳之間的走線還可以使45°和135°方向。而現(xiàn)有的X結(jié)構(gòu)Steiner最小樹(shù)(X-architecture Steiner MinimumTree,XSMT)構(gòu)建算法主要分為精確算法和啟發(fā)式算法。隨著問(wèn)題規(guī)模地不斷擴(kuò)大，這些算法要么面臨時(shí)間復(fù)雜度的劇增，要么極易陷入局部極值，很難得到一個(gè)高質(zhì)量的解方案。因此，迫切需要一種高效可行的X結(jié)構(gòu)Steiner最小樹(shù)構(gòu)建方法以提高VLSI布線質(zhì)量，最終優(yōu)化芯片的性能。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明的目的是提供一種兩步式X結(jié)構(gòu)Steiner最小樹(shù)構(gòu)建方法，目的是在保證時(shí)間復(fù)雜度較低的前提下，利用粒子群優(yōu)化算法強(qiáng)大的搜索能力，優(yōu)化布線樹(shù)拓?fù)浣Y(jié)構(gòu)，最終構(gòu)建一棵線長(zhǎng)最短的X結(jié)構(gòu)Steiner樹(shù)，從而減少布線資源的冗余。

本發(fā)明采用以下方案實(shí)現(xiàn)：一種兩步式X結(jié)構(gòu)Steiner最小樹(shù)構(gòu)建方法，包括以下步驟：

步驟S1：提供X結(jié)構(gòu)模型，進(jìn)行社會(huì)學(xué)習(xí)離散粒子群搜索階段，通過(guò)粒子群優(yōu)化技術(shù)找到一棵具有較短線長(zhǎng)的次優(yōu)X結(jié)構(gòu)Steiner樹(shù)；

步驟S2：線長(zhǎng)優(yōu)化階段：設(shè)計(jì)了一種基于局部拓?fù)鋬?yōu)化的策略用以最小化X結(jié)構(gòu)Steiner樹(shù)的線長(zhǎng)；從而構(gòu)建出一棵線長(zhǎng)最短的X結(jié)構(gòu)Steiner樹(shù)模型，也就是X結(jié)構(gòu)Steiner最小樹(shù)。

進(jìn)一步地，所述X結(jié)構(gòu)模型的定義如下：

定義1.偽Steiner點(diǎn)：假設(shè)除了引腳外,引入的額外的連接點(diǎn)，稱(chēng)為偽Steiner點(diǎn)即PS(Pseudo-Steiner point,PS)；

定義2.0選擇：從出發(fā)引腳節(jié)點(diǎn)先引曼哈頓結(jié)構(gòu)邊至PS，再?gòu)腜S引X結(jié)構(gòu)邊至目標(biāo)引腳節(jié)點(diǎn)，這種連接方式稱(chēng)作0選擇；

定義3.1選擇；從出發(fā)引腳節(jié)點(diǎn)先引X結(jié)構(gòu)邊至PS，再?gòu)腜S引曼哈頓結(jié)構(gòu)邊至目標(biāo)引腳節(jié)點(diǎn)，這種連接方式稱(chēng)作1選擇；

定義4.2選擇；從出發(fā)引腳節(jié)點(diǎn)先引豎直邊至PS，再?gòu)腜S引水平邊至目標(biāo)引腳節(jié)點(diǎn)，這種連接方式稱(chēng)作2選擇；