基于緩沖器插入的非漢娜布線優化算法

呂麗華

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

關鍵詞：緩沖器插入 非漢娜優化 異步高階埃爾摩算法

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

1 引言

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

2 節點優化的緩沖器插入算法

2.1 問題描述

在布線區域中預先插入一組可用的緩沖區空間作為輸入，我們把這些緩沖空間中的可以被緩沖區所占用且不超過區域邊界的緩沖空間叫做關鍵區。為了實現更優布線，當且只當關鍵區被一條路徑穿過時，緩沖器才能插入到緩沖空間中，布線樹和緩沖區之間是動態變化的。

2.2 緩沖器插入與非漢娜優化過程

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

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

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

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

2.4 算法描述

文中用到的術語做如下描述：

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

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

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

2.5 算法步驟詳述

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

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

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

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

3 復雜性分析

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

4 實驗結果

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

5 結語

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

參考文獻

[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.