[發(fā)明專利]一種大規(guī)模集成電路設(shè)計(jì)中的繞障直角斯坦納樹構(gòu)造方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310249724.5
• 申請(qǐng)日: 2013-06-21
• 公開（公告）號(hào): CN103324796A
• 公開（公告）日: 2013-09-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ì)中的繞障直角斯坦納樹構(gòu)造方法，屬于集成電路計(jì)算機(jī)輔助設(shè)計(jì)領(lǐng)域,尤其大規(guī)模集成電路物理設(shè)計(jì)中電路布線設(shè)計(jì)領(lǐng)域。

背景技術(shù)

在大規(guī)模集成電路物理設(shè)計(jì)中，電路布線解決的基本問題是在可布線區(qū)域內(nèi)采用一棵直角斯坦納樹來連通一個(gè)線網(wǎng)的所有引腳，并使得樹總線長盡可能小。針對(duì)該問題，目前人們主要研究繞障最小直角斯坦納樹問題(obstacle-avoiding?rectilinear?Steiner?minimal?tree,OARSMT)。非繞障礙最小直角斯坦納樹問題(rectilinear?Steiner?minimal?tree,RSMT)是OARSMT問題的一個(gè)簡化了的特例，而且已經(jīng)被證明是NP-complete問題。隨著集成電路技術(shù)的迅速發(fā)展，現(xiàn)代集成電路設(shè)計(jì)中大量引入了宏單元、IP模塊、預(yù)布線線網(wǎng)等，使得布線芯片上的障礙個(gè)數(shù)不斷增加，同時(shí)需要互聯(lián)的引腳個(gè)數(shù)也在不斷的增加。這使得布線問題變得異常復(fù)雜，設(shè)計(jì)一種高效的布線方法顯得尤為重要。

對(duì)于較大規(guī)模的繞障直角斯坦納樹問題，確定性方法的運(yùn)行時(shí)間是無法預(yù)計(jì)和承受的。目前，國內(nèi)外學(xué)者提出的有效方法主要是將傳統(tǒng)啟方法和局部搜索相結(jié)合,其中具有代表性的方法有：[參考文獻(xiàn)：Long?J,Zhou?H,O.MS(2008)EBOARST:An?Efficient?Edge-Based?Obstacle-Avoiding?Rectilinear?Steiner?Tree?Construction?Algorithm.Computer-Aided?Design?of?Integrated?Circuits?and?Systems,IEEE?Transactions?on27(12):2169-2182.]、[參考文獻(xiàn)：Lin?CW,Chen?S-Y,Chi-Feng?L,Yao-Wen?C,Chia-Lin?Y(2008)Obstacle-Avoiding?Rectilinear?Steiner?Tree?Construction?Based?on?Spanning?Graphs.Computer-Aided?Design?of?Integrated?Circuits?and?Systems,IEEE?Transactions?on27(4):643-653.]、[參考文獻(xiàn)：Li?L,Young?EFY(2008)Obstacle-avoiding?rectilinear?Steiner?tree?construction.Paper?presented?at?the?Proceedings?of?the2008IEEE/ACM?International?Conference?on?Computer-Aided?Design,San?Jose,California:523-528]、[參考文獻(xiàn)：Liu?C-H,Kuo?S-Y,Lee?DT,Lin?C-S,Weng?J-H,Yuan?S-Y(2012)Obstacle-Avoiding?Rectilinear?Steiner?Tree?Construction:A?Steiner-Point-Based?Algorithm.Computer-Aided?Design?of?Integrated?Circuits?and?Systems,IEEE?Transactions?on31(7):1050-1060.]和[參考文獻(xiàn)：Ajwani?G,Chu?C,Mak?W-K(2011)FOARS:FLUTE?Based?Obstacle-Avoiding?Rectilinear?Steiner?Tree?Construction.Computer-Aided?Design?of?Integrated?Circuits?and?Systems,IEEE?Transactions?on30(2):194-204.]等。這類算法容易陷入局部最優(yōu)解，導(dǎo)致求解質(zhì)量較低。

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

本發(fā)明的目的是提供一種大規(guī)模集成電路設(shè)計(jì)中的繞障直角斯坦納樹構(gòu)造方法。

本發(fā)明采用以下方案實(shí)現(xiàn)：一種大規(guī)模集成電路設(shè)計(jì)中的繞障直角斯坦納樹構(gòu)造方法，其特征在于：首先根據(jù)逃逸圖（Escape?Graph）理論構(gòu)建出該布線問題布線圖；然后以人工蜂群優(yōu)化方法的為基本框架，使用布線圖中的邊構(gòu)造出一個(gè)準(zhǔn)最優(yōu)可行解；為了實(shí)現(xiàn)人工蜂群優(yōu)化方法，設(shè)計(jì)了全局搜索策略、基于關(guān)鍵節(jié)點(diǎn)的局部搜索策略、基于關(guān)鍵節(jié)點(diǎn)的編碼和一個(gè)以改進(jìn)的啟發(fā)式算法為基礎(chǔ)的編碼器；具體而言，它依次含有以下步驟：