[發(fā)明專利]大規(guī)模集成電路設(shè)計(jì)中基于線長(zhǎng)最短優(yōu)化的繞障布線方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410036947.8
• 申請(qǐng)日: 2014-01-26
• 公開（公告）號(hào): CN103984789B
• 公開（公告）日: 2017-01-25
• 發(fā)明（設(shè)計(jì)）人: 張浩;葉東毅;陳羽中;余春艷;張棟;楊晶菁
• 申請(qǐng)（專利權(quán)）人: 福州大學(xué)
• 主分類號(hào): G06F17/50
• 分類號(hào): G06F17/50
• 代理公司: 福州元?jiǎng)?chuàng)專利商標(biāo)代理有限公司35100
• 代理人: 蔡學(xué)俊

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

本發(fā)明涉及大規(guī)模集成電路物理設(shè)計(jì)技術(shù)領(lǐng)域，特別是一種大規(guī)模集成電路設(shè)計(jì)中基于線長(zhǎng)最短優(yōu)化的繞障布線方法。

背景技術(shù)

大規(guī)模集成電路物理設(shè)計(jì)中，在曼哈頓模型下，基于線長(zhǎng)最短優(yōu)化的布線方法是物理設(shè)計(jì)中總體布線和詳細(xì)布線最重要的基礎(chǔ)工作。隨著集成電路技術(shù)的迅速發(fā)展，現(xiàn)代集成電路設(shè)計(jì)中大量引入了宏單元、IP模塊、預(yù)布線線網(wǎng)等，使得布線芯片上的出現(xiàn)了大量的矩形障礙且個(gè)數(shù)仍在不斷增加。同時(shí)，需要互聯(lián)的引腳個(gè)數(shù)也在不斷的增加，使得布線難度也增大。在布線過(guò)程中，需要將同屬于一個(gè)線網(wǎng)的所有引腳通過(guò)一個(gè)直角斯坦納樹連通起來(lái)，且不穿過(guò)任何的矩形障礙。所得到的直角斯坦納樹的總線長(zhǎng)是該問(wèn)題的一個(gè)重要指標(biāo)。因此，設(shè)計(jì)一個(gè)基于線長(zhǎng)最短優(yōu)化的繞障布線方法顯得尤為重要。

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

本發(fā)明的目的在于提供一種大規(guī)模集成電路設(shè)計(jì)中基于線長(zhǎng)最短優(yōu)化的繞障布線方法，該方法布線布局合理，所得線長(zhǎng)短，布線效果好。

為實(shí)現(xiàn)上述目的，本發(fā)明采用的技術(shù)方案是：一種大規(guī)模集成電路設(shè)計(jì)中基于線長(zhǎng)最短優(yōu)化的繞障布線方法，首先根據(jù)逃逸圖理論構(gòu)建布線問(wèn)題布線圖，然后采用多源并發(fā)探索方法選擇頂點(diǎn)標(biāo)記為必經(jīng)點(diǎn)，再基于必經(jīng)點(diǎn)集合構(gòu)建一個(gè)可行解Steiner樹，最后優(yōu)化可行解。

在本發(fā)明一實(shí)施例中，該方法具體包括以下步驟：

步驟(1)?初始化，輸入布線問(wèn)題的線網(wǎng)信息和障礙信息；

步驟(2)?根據(jù)線網(wǎng)信息和障礙信息，構(gòu)造逃逸圖G=(V,E,T,ω)；所述逃逸圖為帶權(quán)無(wú)向圖，E表示邊集合，V?表示頂點(diǎn)集合，引腳對(duì)應(yīng)的頂點(diǎn)稱為端點(diǎn)，T表示端點(diǎn)集合，???????????????????????????????????????????????表示邊的權(quán)重映射函數(shù)，邊的權(quán)重對(duì)應(yīng)邊在布線區(qū)域的實(shí)際線長(zhǎng)；

步驟(3)?采用多源并發(fā)探索方法標(biāo)記必經(jīng)點(diǎn)，得到必經(jīng)點(diǎn)集合PV；

步驟(4)?將必經(jīng)點(diǎn)集合和端點(diǎn)集合的并集PV∪T中頂點(diǎn)都看成端點(diǎn)，使用Steiner樹構(gòu)造方法構(gòu)建一個(gè)可行解ST；

步驟(5)?優(yōu)化可行解ST。

在本發(fā)明一實(shí)施例中，所述步驟(3)中，所述必經(jīng)點(diǎn)是指期望在構(gòu)造可行解時(shí)經(jīng)過(guò)這些頂點(diǎn)，所述多源并發(fā)探索方法包括以下步驟：

步驟(3.1)?初始化過(guò)程：用端點(diǎn)集合中各個(gè)端點(diǎn)分別構(gòu)成一個(gè)頂點(diǎn)集，并分別作為泰森圖種子也即源點(diǎn)，每個(gè)泰森圖種子設(shè)置為未標(biāo)記狀態(tài)；

步驟(3.2)?擴(kuò)展過(guò)程：從多個(gè)未標(biāo)記的泰森圖種子出發(fā)構(gòu)建泰森圖，記錄遍歷過(guò)程中得到的橋邊，每輪擴(kuò)展過(guò)程頂點(diǎn)遍歷范圍為當(dāng)前找到橋邊的最小跨度Range，即對(duì)當(dāng)前遍歷頂點(diǎn)u有u.dist?≤?Range，否則進(jìn)入回溯過(guò)程；

步驟(3.3)?回溯過(guò)程：從所有遍歷到的橋邊中選出跨度最小且相應(yīng)泰森圖種子S_i和S_j都未標(biāo)記的一組主橋邊MBs(S_i,S_j)，以每個(gè)主橋邊上的每個(gè)頂點(diǎn)為當(dāng)前點(diǎn)，采用回溯法遍歷S_i和S_j之間的所有最短路徑，每條最短路徑的兩端頂點(diǎn)都添加到必經(jīng)點(diǎn)集合PV中，該些最短路徑上的所有頂點(diǎn)構(gòu)成頂點(diǎn)集SPS_ij，進(jìn)入更新過(guò)程；

步驟(3.4)?更新過(guò)程：頂點(diǎn)集S_i、S_j和SPS_ij中所有頂點(diǎn)構(gòu)成一個(gè)新的泰森圖種子S_n，使用S_n替代S_i和S_j，S_n設(shè)置為標(biāo)記狀態(tài)，繼續(xù)執(zhí)行回溯過(guò)程，直到所有的泰森圖種子都為標(biāo)記狀態(tài)；