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

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

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

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

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