圖的Steiner最小樹構建及其布線應用.pdf

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

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

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

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