[發(fā)明專利]基于多策略優(yōu)化的Slew約束下的X結(jié)構(gòu)Steiner樹構(gòu)造方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202110086124.6
• 申請(qǐng)日: 2021-01-22
• 公開（公告）號(hào): CN112733484B
• 公開（公告）日: 2022-06-14
• 發(fā)明（設(shè)計(jì)）人: 劉耿耿;黃逸飛;郭文忠;陳國(guó)龍
• 申請(qǐng)（專利權(quán)）人: 福州大學(xué)
• 主分類號(hào): G06F30/394
• 分類號(hào): G06F30/394;G06F30/398;G06F111/04;G06F115/06
• 代理公司: 福州元?jiǎng)?chuàng)專利商標(biāo)代理有限公司 35100
• 代理人: 丘鴻超;蔡學(xué)俊

1.一種基于多策略優(yōu)化的Slew約束下的X結(jié)構(gòu)Steiner樹構(gòu)造方法，其特征在于，包括以下步驟：

步驟S1：結(jié)合三角剖分方法和最小生成樹方法獲得點(diǎn)集為引腳集的最小生成樹；

步驟S2：生成用于記錄引腳以及障礙之間的信息的預(yù)查表，并將最小生成樹轉(zhuǎn)換成Steiner樹；

步驟S3：進(jìn)行重布線，通過(guò)消除布線中經(jīng)過(guò)障礙的較長(zhǎng)片段并重新布線以降低Slew大小，使Steiner樹部分滿足Slew約束；并采用精煉策略，以減少Steiner樹的布線代價(jià)；

步驟S4：逐個(gè)計(jì)算并修正不滿足Slew約束的布線，使得內(nèi)部樹完全滿足Slew約束；

在步驟S3中，精煉策略采用的子樹結(jié)構(gòu)優(yōu)化方法具體包括以下步驟：

步驟31：遍歷Steiner樹的所有邊以記錄每個(gè)引腳p_i的相鄰引腳，每個(gè)引腳p_i與其相鄰引腳構(gòu)成根為引腳p_i、 邊集大小為引腳個(gè)數(shù)m、 深度為2的子樹結(jié)構(gòu)；

步驟32：對(duì)于每個(gè)子樹，枚舉的所有4^m種拓?fù)浣Y(jié)構(gòu)；然后選擇所有邊集元素繞障或者在障礙內(nèi)部的連通分量不超過(guò)閾值且具有最小線長(zhǎng)的那一個(gè)子樹結(jié)構(gòu)作為該子樹最佳子結(jié)構(gòu)記為bp_i，同時(shí)計(jì)算每個(gè)bp_i的公共邊長(zhǎng)度sp_i；

步驟33：根據(jù)sp_i的長(zhǎng)度按遞減順序?qū)λ凶訕溥M(jìn)行排序；

步驟34：對(duì)于每個(gè)引腳p_i，按sp_i的順序?qū)p_i的布線選擇組合對(duì)原有的Steiner樹進(jìn)行替換，直到布線樹的所有邊都已確定；

步驟S41:遍歷Steiner樹的所有邊，為每個(gè)障礙建立對(duì)應(yīng)的內(nèi)部樹；

步驟S42：遍歷所有的內(nèi)部樹，自驅(qū)動(dòng)節(jié)點(diǎn)而下逐點(diǎn)的準(zhǔn)確計(jì)算內(nèi)部樹的接收節(jié)點(diǎn)的Slew值的大小；

步驟S43：對(duì)Slew值大于閾值的接收節(jié)點(diǎn)，刪除接收節(jié)點(diǎn)至其內(nèi)部樹上游節(jié)點(diǎn)的連通分量，并沿著障礙的邊連接至同側(cè)上游接收節(jié)點(diǎn)，無(wú)同側(cè)上游接收節(jié)點(diǎn)則沿著障礙的邊連至驅(qū)動(dòng)節(jié)點(diǎn)；

其中，Slew估計(jì)值的計(jì)算方式為：

其中，c_b是中繼器輸入電容，r_b是中繼器輸出電阻，c是互連線上單位電容，r是互連線上單位電阻，Len(v_in,v_out)為布線在障礙內(nèi)部的節(jié)點(diǎn)v_in到節(jié)點(diǎn)v_out的連通分量；K_bin為中繼器B_in的固有電壓轉(zhuǎn)換速率；R_bin為中繼器B_in的電壓轉(zhuǎn)換速率阻抗。

2.根據(jù)權(quán)利要求1所述的基于多策略優(yōu)化的Slew約束下的X結(jié)構(gòu)Steiner樹構(gòu)造方法，其特征在于，包括以下步驟：

步驟S1：初始階段：通過(guò)三角剖分方法將待連接的引腳構(gòu)造成點(diǎn)集為引腳的連通圖，并利用Kruskal方法在該連通圖構(gòu)建最小生成樹；

步驟S2：預(yù)處理階段：通過(guò)預(yù)先計(jì)算并記錄初始階段構(gòu)造的最小生成樹的邊集以及與障礙之間的信息，生成相應(yīng)的預(yù)查表，并將初始階段構(gòu)造的最小生成樹轉(zhuǎn)變?yōu)镾teiner樹；

步驟S3：主體階段：通過(guò)引入偽Steiner點(diǎn)的方法，除去預(yù)處理階段構(gòu)造的Steiner樹中經(jīng)過(guò)障礙較長(zhǎng)的布線并重新布線，從而有效消除部分違反約束的布線結(jié)構(gòu)，并采用精煉策略，通過(guò)去除冗余點(diǎn)及子樹結(jié)構(gòu)優(yōu)化方法的優(yōu)化線長(zhǎng)；

步驟S4：后處理階段：遍歷Steiner樹中所有的內(nèi)部樹，逐點(diǎn)的判斷內(nèi)部樹所有的接收節(jié)點(diǎn)的Slew值，修復(fù)違反約束部分，使得Steiner樹完全滿足Slew約束。

3.根據(jù)權(quán)利要求1或2所述的基于多策略優(yōu)化的Slew約束下的X結(jié)構(gòu)Steiner樹構(gòu)造方法，其特征在于：

步驟S1具體包括以下過(guò)程：在給定電路下，首先通過(guò)平面掃描在給定引腳集的基礎(chǔ)上構(gòu)造泰森多邊形，然后通過(guò)將泰森多邊形轉(zhuǎn)換為對(duì)偶圖來(lái)生成三角剖分，并通過(guò)Kruskal方法在三角剖分上構(gòu)建最小生成樹。