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

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

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

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

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

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

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

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