極大規(guī)模集成電路全局互連線設(shè)計與優(yōu)化算法研究.pdf

1、伴隨著集成電路工藝進入超深亞微米和納米時代，不斷增大的電路規(guī)模和日益凸顯的互連線物理效應(yīng)等問題，給集成電路設(shè)計自動化提出了巨大的挑戰(zhàn)。集成電路設(shè)計自動化是一個發(fā)展變化快、學(xué)科交叉和算法密集型的領(lǐng)域，存在著大量的大規(guī)模數(shù)值方程求解和組合優(yōu)化等問題，受到學(xué)術(shù)界和工業(yè)界的高度關(guān)注，互連線優(yōu)化設(shè)計成為該領(lǐng)域研究的熱點和前沿。本文以時鐘網(wǎng)絡(luò)、電源/地線網(wǎng)絡(luò)和信號線網(wǎng)等三種全局互連線為背景，對互連線網(wǎng)分析和設(shè)計的方法和優(yōu)化算法進行深入研究，旨在探討

2、以“互連線為中心”的集成電路設(shè)計優(yōu)化方法和手段。 論文在廣泛調(diào)研了現(xiàn)有的互連線優(yōu)化算法的基礎(chǔ)上，深入分析了時鐘網(wǎng)絡(luò)、電源／地線網(wǎng)絡(luò)和信號線網(wǎng)等三種全局互連線優(yōu)化問題及其理論基礎(chǔ)，提出了相應(yīng)的設(shè)計方法并實現(xiàn)了優(yōu)化算法。研究了時鐘網(wǎng)絡(luò)可靠性設(shè)計問題，針對工藝變化對時鐘線網(wǎng)性能帶來的影響，以樹型拓撲結(jié)構(gòu)的時鐘線網(wǎng)為例，探討了抗工藝變化的時鐘設(shè)計的優(yōu)化算法；深入分析和研究了大規(guī)模供電網(wǎng)絡(luò)的瞬態(tài)分析和優(yōu)化問題，針對大規(guī)模網(wǎng)絡(luò)帶來的求解速度

3、和精度問題，以鏈+網(wǎng)的拓撲結(jié)構(gòu)為對象提出了快速的時域分析方法和高效的優(yōu)化算法；對信號線網(wǎng)的串擾問題進行了研究，針對資源分配階段解決串擾的多目標優(yōu)化問題，提出在層分配、過點分配和軌道分配過程中減小串擾的綜合資源分配算法，取得了以下創(chuàng)新性的成果： ●提出了抗工藝變化的帶緩沖器插入的時鐘網(wǎng)絡(luò)設(shè)計和優(yōu)化算法。針對時鐘網(wǎng)絡(luò)延遲和偏差易受工藝參數(shù)變化影響問題，論文從分析時鐘樹的特點入手，提出了時鐘樹對工藝參數(shù)變化的敏感性模型；在時鐘樹的構(gòu)建

4、過程中，采用偏差靈敏度指導(dǎo)下的時鐘節(jié)點合并方法構(gòu)造特殊的樹型拓撲結(jié)構(gòu)，有效地提高了時鐘樹抗工藝變化能力；通過對插入緩沖器數(shù)量和位置的規(guī)劃進一步減小工藝參數(shù)變化對時鐘偏差的影響，同時優(yōu)化連線時延。實驗結(jié)果表明，在時鐘線長增加小于14％的情況下，違反偏差約束減小60～80％。 ●提出了層次式供電網(wǎng)絡(luò)快速瞬態(tài)分析算法。針對大規(guī)模供電網(wǎng)絡(luò)分析速度和精度問題，對標準單元布圖模式中供電網(wǎng)絡(luò)的鏈狀(CHAIN)結(jié)構(gòu)，采用無誤差的等效電路方法將

5、中間節(jié)點進行壓縮，在求解壓縮電路之后，恢復(fù)求解中間節(jié)點，從而大大提高了算法的分析速度；對供電網(wǎng)絡(luò)的網(wǎng)狀(MESH)結(jié)構(gòu)，采用松弛策略進行電路劃分，與已有的多網(wǎng)格方法不同，該方法不僅避免了稠密矩陣的引入，而且可以補償由于電路劃分引起的誤差，同時避免了矩陣求逆運算，大大提高了求解速度并得到更為精確的結(jié)果。與商用軟件SPICE相比，在精度不低于0.035％的情況下，速度提高兩個數(shù)量級。 ●提出了基于電路劃分和考慮漏電流的供電網(wǎng)絡(luò)啟發(fā)式

6、優(yōu)化算法。以大規(guī)模供電網(wǎng)絡(luò)優(yōu)化問題為背景，從降低供電網(wǎng)絡(luò)優(yōu)化問題復(fù)雜性入手，采用基于松弛策略和隨機行走方法對電路進行劃分，大大降低問題求解規(guī)模；采用啟發(fā)式的算法求解去耦合電容的放置位置和大小，使優(yōu)化效率大大提高。在建立了去耦合電容漏電流模型的基礎(chǔ)上，采用線寬和添加去耦合電容結(jié)合的兩步優(yōu)化策略，有效地發(fā)揮了各自在消除供電網(wǎng)絡(luò)噪聲上的優(yōu)勢，使算法取得了比較好的綜合優(yōu)化效果。實驗結(jié)果表明，與已發(fā)表的同類算法只能處理1K節(jié)點的網(wǎng)絡(luò)相比，本算法可

7、以處理11M節(jié)點的網(wǎng)絡(luò)，且有更高的優(yōu)化效率。 ●提出了減小串擾的啟發(fā)式綜合布線資源分配算法。針對互連線串擾帶來的信號完整性問題，論文從布線資源分配的角度，探討解決串擾影響的方法。算法將屏蔽插入與層分配、過點分配和軌道分配結(jié)合起來，使資源分配策略一致并提高分配質(zhì)量；采取逐行(slice)處理的分解策略及屏蔽規(guī)劃與詳細分配的兩階段分而治之方法，有效地減小了問題的搜索空間；在詳細分配中，采用動態(tài)優(yōu)先隊列策略，根據(jù)分配過程中資源占用情況