基于緩沖器插入的非漢娜布線優(yōu)化算法

呂麗華

摘要：改進超大規(guī)模集成電路性能依靠插入緩沖器和非漢娜算法是一個有效的方案。在時間約束和互聯(lián)性能要求嚴格的情形下，在單元布局之后使用空余空間供緩沖器插入從而優(yōu)化布線拓撲。這樣可以將布線最大時延最小化，從而布線成本降至最低。本算法在18μm IC 工藝中測試，可以降低約30%布線樹時延，可以明顯提升布線性能。

關(guān)鍵詞：緩沖器插入 非漢娜優(yōu)化 異步高階埃爾摩算法

中圖分類號：TP311.52 文獻標(biāo)識碼：A 文章編號：1007-9416（2016）12-0137-01

1 引言

隨著集成電路的規(guī)模不斷提高，互聯(lián)阻抗對于布線性能的影響越來越大。利用節(jié)點優(yōu)化的緩沖器插入 算法是在異步高階埃爾摩算法時延模型下將非 漢娜點優(yōu)化和緩沖器插入結(jié)合起來[1]。在算法的執(zhí)行過程中，非漢娜優(yōu)化算法和緩沖器同步插入的操作多次迭代執(zhí)行，直至結(jié)果達到最優(yōu)。

2 節(jié)點優(yōu)化的緩沖器插入算法

2.1 問題描述

在布線區(qū)域中預(yù)先插入一組可用的緩沖區(qū)空間作為輸入，我們把這些緩沖空間中的可以被緩沖區(qū)所占用且不超過區(qū)域邊界的緩沖空間叫做關(guān)鍵區(qū)。為了實現(xiàn)更優(yōu)布線，當(dāng)且只當(dāng)關(guān)鍵區(qū)被一條路徑穿過時，緩沖器才能插入到緩沖空間中，布線樹和緩沖區(qū)之間是動態(tài)變化的。

2.2 緩沖器插入與非漢娜優(yōu)化過程

在時延違反條件的約束下，為了得到拐點到連接點距離的最大值，需要將連接點盡量移動至距離點，也就是使拐點到連接點的距離最大化[2]。為了進一步減低布線成本，我們引入了緩沖器的插入技術(shù)。

2.3 四階異步埃爾摩算法的使用

我們舉例來說明埃爾摩 時延的不準確性，下面是一個5個漏點的線網(wǎng)。利用SPICE 傳輸線模型、高階埃爾摩 公式計算結(jié)果進行了對比。分別計算了所有漏點上的時延，同時還計算了spice結(jié)果的誤差時延的百分比。通過實驗得知，埃爾摩 時延誤差最大，它的結(jié)果遠較異步高階埃爾摩算法模型的時延差。隨著布線深度的增加，這個趨勢只會越來越嚴重。

為了提高時延模型的精確度，我們提出了異步高階埃爾摩算法的時延模型。獲取時延的時候，可以利用 RICE 算法計算出布線的時間，對Padé近似值的分母進行解析，能夠得到一個在極值位置收斂的高階多項式。反拉普拉斯變換的使用，會讓我們獲得一個關(guān)于埃爾摩 時延的泰勒多項式，這是關(guān)于時間域的冪指函數(shù)。時延值就利用這個收斂的、四階的多項式來計算。經(jīng)過不超過三次的反復(fù)迭代，多項式就會收斂。

2.4 算法描述

文中用到的術(shù)語做如下描述：

Ui是規(guī)定時延在漏點i的值，Tdi是漏點 i時延，Tvi為根據(jù)公式計算：Tvi=Tdi-Qi漏點i時延違反，W布線樹的長度，表示一個漏點的負載電容，Bj可選的緩沖位置的緩沖區(qū)空間，α是緩沖器的加權(quán)系數(shù)，c是線路的單位長度電容值，位于布線樹上是漏點的個數(shù)用n表示，m是布線樹上可作為的緩沖區(qū)空間的數(shù)量，插入到布線樹上的緩沖器的數(shù)量由k表示。

已知條件為：一棵布線樹，它①擁有源點L0，②一組漏點L，③每個漏點的規(guī)定時延。并且已經(jīng)找到了一組可用的緩沖器插入空間，以上構(gòu)成一棵斯坦納布線樹，從集合L中再選擇一個滿足下列條件子集：

是導(dǎo)線成本的加權(quán)系數(shù)。公式中增加了系數(shù)和，使得緩沖器和導(dǎo)線成本從數(shù)量上變得具有可比性。這樣做的目的是可以從理論上證明埃爾摩時延是遠程控制線網(wǎng)時延 的上限，而實際應(yīng)用中，需要對 埃爾摩 時延公式進行校正，即 乘以ln2可提高準確性。我們這里所使用的“埃爾摩時延”便是由上述方法而得到的。

2.5 算法步驟詳述

算法是由兩個主要步驟組成。第一步，斯坦納異步埃爾摩算法布線樹階段，它與 SERT 布線方法類似，不同的就是由四階 AWT 模型所取代其 埃爾摩時延模型，可得到布線樹 T；行非 Hanan 優(yōu)化和緩沖器插入是算法第二階段。

在第一步中，布線樹由一個源點組成，之后布線樹不斷生長。布線樹生長的基本辦法就是先找到原本未連接到布線樹上的漏點，陸續(xù)將這些漏點連接到布線樹的特定上，目的是為了盡量減小最大時延。

然后進行第二步的優(yōu)化。該步驟的主要目的是為每個漏點找到合適的連接點以便重新連接到布線樹上。這個過程可能的結(jié)果有三種：成功在一個緩沖區(qū)中插入了一個緩沖器；該緩沖區(qū)依然空閑；緩沖區(qū)由于不能導(dǎo)致最大時延的最小化而被舍棄。

緩沖區(qū)所處的位置可能位于多個布線片段的交叉區(qū)域，即該緩沖區(qū)所處節(jié)點具有多扇出特性。該緩沖區(qū)是否允許插入緩沖器將由每個分支上的漏點臨界點的狀態(tài)來決定。如果每個分支中的漏點具有十分接近的臨界點，那么在該緩沖區(qū)插入緩沖器將會對所有扇出分支進行優(yōu)化；否則，緩沖器會被插入在非關(guān)鍵漏點的分支，結(jié)果將會調(diào)配關(guān)鍵路徑和非關(guān)鍵路徑中負荷，使得每個路徑中的負荷達到最優(yōu)。

3 復(fù)雜性分析

雖然將傳統(tǒng)埃爾摩算法被異步高階埃爾摩算法代替，進行緩沖器插入優(yōu)化，但穿越和迭代次數(shù)沒有發(fā)生變化，復(fù)雜度依然為O（n）級，所以，緩沖器插入在節(jié)點優(yōu)化的第一步驟中成本還是O（n4）。緩沖器插入在節(jié)點優(yōu)化的第二步驟中，每個經(jīng)過第一步優(yōu)化的布線樹具有兩個迭代層，緩沖區(qū)的數(shù)目為層數(shù)的上界。綜合第一步和第二部的總成本約為O（m2·n4·L/）。從公式看出，參加乘法運算的對象比m2小得多，可用空間的數(shù)目總是比線網(wǎng)穿越的候選緩沖區(qū)數(shù)據(jù)要多。

4 實驗結(jié)果

我們用IC 和 MCM 工藝分別對以4的1倍、2倍、3倍的線網(wǎng)為例，測試了優(yōu)化情形。從實驗結(jié)果表明，18μmIC工藝中，經(jīng)過節(jié)點優(yōu)化的緩沖器插入算法優(yōu)化，31%的布線成本可被改善；針對 MCM，33%的成本可被改善。在實驗中，對具有12個漏點的線網(wǎng)進行了測試，通常在一分鐘內(nèi)可計算完成，在最壞的情況下，也只需要幾分鐘即可完成。總體來看，在針對全局時延的關(guān)鍵線網(wǎng)進行試驗測試，計算成本合理。

5 結(jié)語

為了改進超大規(guī)模集成電路的互聯(lián)性能，我們提出的非 Hanan 優(yōu)化算法和同步緩沖器插入，尤其當(dāng)時延約束布線資源要求非常嚴格的時候，該算法對優(yōu)化布線性能效果明顯。

參考文獻

[1]Hou Huibo， Hu Jiang， Sapatnekar S S. Non-Hanan Routing[J].IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems， 1999，18（4）：436-444.

[2]Lillis J， Cheng C K， Lin T T Y， et al. New Performance-driven Routing Techniques with Explicit Area/delay Tradeoffs and Simultaneous Wire Sizing[C]//Proc. of the ACM/IEEE Design Automation Conference. [S. 1.]： IEEE Press， 1996： 395-400.