圖的Steiner最小樹(shù)構(gòu)建及其布線應(yīng)用.pdf

1、隨著集成電路工藝制造技術(shù)的迅速發(fā)展，芯片的特征尺寸不斷減少，互連線的結(jié)構(gòu)變得越來(lái)越復(fù)雜。互連線的RC延時(shí)已經(jīng)成為了芯片的主要延時(shí)，極大地影響著芯片的性能。針對(duì)傳統(tǒng)的Manhattan互連結(jié)構(gòu)受限于布線走向只能水平、豎直兩個(gè)方向、無(wú)法充分利用布線空間資源而造成互連線的延時(shí)難以被進(jìn)一步優(yōu)化，產(chǎn)生了一系列新型的非直角的互連結(jié)構(gòu)，尤其是X互連結(jié)構(gòu)因其減少線長(zhǎng)的潛力而引起了廣泛的研究興趣。
　　本文主要研究X互連結(jié)構(gòu)的快速啟發(fā)式的布線算法，

2、將實(shí)際非常復(fù)雜的X互連結(jié)構(gòu)的布線問(wèn)題簡(jiǎn)化為構(gòu)建繞過(guò)障礙物的八叉Steiner最小樹(shù)(OAOSMT)的計(jì)算幾何問(wèn)題。通過(guò)研究學(xué)習(xí)國(guó)內(nèi)外相關(guān)學(xué)術(shù)成果，本文提出了構(gòu)建圖的Steiner最小樹(shù)(GSMT)的新啟發(fā)式算法，并運(yùn)用該算法和幾類簡(jiǎn)單的幾何變換來(lái)實(shí)現(xiàn)繞過(guò)障礙物的八叉Steiner最小樹(shù)的構(gòu)建。
　　針對(duì)經(jīng)典的圖的Steiner最小樹(shù)問(wèn)題，本文提出了包含四步驟的新啟發(fā)式算法。首先對(duì)原始輸入圖進(jìn)行連通子圖的分解并簡(jiǎn)化，來(lái)減少求解問(wèn)題的

3、規(guī)模。然后在每個(gè)連通子圖中按照三源最短路徑擴(kuò)展的思想來(lái)構(gòu)建Steiner樹(shù)。接著利用Steiner點(diǎn)插入和邊變換的操作來(lái)進(jìn)一步優(yōu)化連通子圖的Steiner樹(shù)。最后，合并各個(gè)子圖中的Steiner樹(shù)來(lái)獲得原始圖完整的Steiner最小樹(shù)。實(shí)驗(yàn)結(jié)果表明，該算法相比傳統(tǒng)的GSMT啟發(fā)式算法，能獲得更高質(zhì)量的Steiner樹(shù)，67％的測(cè)試?yán)荧@得的Steiner樹(shù)跟最優(yōu)Steiner樹(shù)相比誤差不超過(guò)1％。
　　本文將此GSMT的求解方法應(yīng)

4、用到X型互連結(jié)構(gòu)的布線問(wèn)題中，提出了構(gòu)建繞過(guò)障礙物的八叉Steiner最小樹(shù)(OAOSMT)的新啟發(fā)式算法。首先引入改進(jìn)型Escape圖的概念，然后將構(gòu)建繞過(guò)障礙物的直角Steiner最小樹(shù)問(wèn)題(OARSMT)轉(zhuǎn)化為改進(jìn)型Escape圖的GSMT問(wèn)題并求解。最后在OARSMT的基礎(chǔ)上，引入了5類簡(jiǎn)單的幾何變換來(lái)快速得到用于X型互連結(jié)構(gòu)的OAOSMT。實(shí)驗(yàn)結(jié)果表明，本文提出的構(gòu)建OAOSMT的新啟發(fā)式算法，獲得的OAOSMT相比OARSM