[發(fā)明專利]一種高效的詳細布線驅動軌道分配方法

有效

• 申請?zhí)枺?/td>: 201811598401.6
• 申請日: 2018-12-25
• 公開（公告）號: CN109684731B
• 公開（公告）日: 2022-06-14
• 發(fā)明（設計）人: 劉耿耿;莊震;郭文忠;陳國龍
• 申請（專利權）人: 福州大學
• 主分類號: G06F30/392
• 分類號: G06F30/392
• 代理公司: 福州元創(chuàng)專利商標代理有限公司 35100
• 代理人: 蔡學俊

本發(fā)明涉及一種高效的詳細布線驅動軌道分配算法，首先提供總體布線結果并進行初始分配：利用軌道分配算法NTA中的逐通道處理的貪心算法將每個iroute都分配到相應的軌道上；其次，進行iroute連接：利用通孔位置模型對步驟S1中分配到相應軌道上的iroute進行連接；然后，進行重疊消減：利用軌道分配算法NTA中的協(xié)商機制，在每一個通道中，iroute按照拆除代價從大到小排序，然后按照這個順序迭代地拆除iroute并將iroute重新分配到分配代價最小的軌道上；最后，進行引腳連接，將每一個引腳連接到iroute或通孔上；輸出軌道分配結果。本發(fā)明能夠得到一個精確的布線結果。

技術領域

本發(fā)明涉及集成電路計算機輔助設計技術領域，特別是一種高效的詳細布線驅動軌道分配方法。

背景技術

布線是超大規(guī)模集成電路(VLSI)物理設計的重要步驟。傳統(tǒng)的布線階段被分為了兩部分，分別是總體布線和詳細布線。在總體布線階段，布線區(qū)域被劃分為一組總體布線單元。總體布線可以得到跨越多個總體布線單元的總體線網(wǎng)大致的布線區(qū)域。總體布線可以得到跨越多個總體布線單元的總體線網(wǎng)大致的布線區(qū)域，即一個由總體布線單元構成的布線樹。而局部線網(wǎng)的所有引腳位于同一個總體布線單元內(nèi)部，無法構建出一棵由總體布線單元組成的布線樹。在總體布線中，局部線網(wǎng)的布線常常被省略。在詳細布線階段，每個線網(wǎng)的引腳被準確地在總體布線給出的布線區(qū)域內(nèi)連通。在問題規(guī)模較小時，這種兩階段的方法可以得到理想的結果。但是，布線作為物理設計中比較偏后的階段，需要處理大量的設計規(guī)則約束。隨著技術節(jié)點的進步，在布線階段需要考慮的設計規(guī)則急劇增加，大大增加了布線算法設計的復雜度以及布線算法運行的時間。在總體布線階段，包括局部線網(wǎng)在內(nèi)的很多信息都被忽略，隨著設計越來越復雜，總體布線已經(jīng)很難為詳細布線階段提供較好的指導。于是，學者們在兩個階段之間加入了軌道分配階段作為兩者之間的橋梁。

隨著對軌道分配的廣泛研究，產(chǎn)生了很多不同用途的軌道分配算法。有些軌道分配算法用于修正早期設計階段的可布線性問題，而更多的軌道分配算法是為了得到可用于詳細布線的草案。已有的用于解決總體布線和詳細布線不匹配問題的軌道分配算法大多數(shù)是為了最大化被分配的iroute數(shù)量。這種軌道分配結果不能預測全局的布線情況，未完成布線的部分在詳細布線階段可能會與已完成布線的部分產(chǎn)生大量的重疊以至于難以達到理想的效果。

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

有鑒于此，本發(fā)明的目的是提出一種高效的詳細布線驅動軌道分配方法，通過有效地縮減iroute之間以及iroute與障礙物之間的重疊長度，能夠有效地解決總體布線和詳細布線之間不匹配的問題，節(jié)約經(jīng)濟成本。

本發(fā)明采用以下方案實現(xiàn)：一種高效的詳細布線驅動軌道分配方法，包括以下步驟：

步驟S1：提供總體布線結果并進行初始分配：利用軌道分配算法NTA中的逐通道處理的貪心算法將每個iroute都分配到相應的軌道上；

步驟S2：進行iroute連接：利用通孔位置模型對步驟S1中分配到相應軌道上的iroute進行連接；

步驟S3：進行iroute的重疊消減：利用軌道分配算法NTA中的協(xié)商機制，在每一個通道中，iroute按照拆除代價從大到小排序，然后按照這個順序迭代地拆除iroute并將iroute重新分配到分配代價最小的軌道上；

步驟S4進行線網(wǎng)的引腳連接，將每一個引腳連接到iroute或通孔上；輸出軌道分配結果，即完成所有線網(wǎng)連接后的布線圖。

進一步地，步驟S1具體為：在每一個通道中，對屬于該通道的iroute按照長度從長到短排序，然后按照這個順序將每個iroute分配到具有最小分配代價的軌道上。

進一步地，所述分配代價的計算公式為：

wlCost+α×overlapCost+β×blkCost