集成電路二劃分的一維泊松方程方法

余永昕, 潘萍梅, 朱文興

(福州大學離散數學與理論計算機科學研究中心, 福建 福州 350108)

0 引言

近年來, 隨著集成電路制造工藝的迅速發展, 集成電路產業已經進入了超深亞微米和納米工藝時代, 芯片的集成度進一步提高. 一塊芯片上所能集成的電路元件越來越多, 加上存儲空間的局限性和封裝工藝的限制, 對超大規模集成電路(very large scale integration circuit, VLSI)設計方法提出了新的挑戰. 為降低設計復雜度, 需要將電路劃分為更小的模塊, 而二劃分算法則是所有劃分算法中最基礎、 最重要的部分.

平衡二劃分問題是NP(non-deterministic polynomial)難問題, 無法在線性時間內得到其最優解. 目前, 集成電路平衡二劃分的算法主要可以分為四種類型: 全局算法[1-2]、 啟發式迭代改進算法[3-4]、 進化算法[5-6]和多級劃分算法[7-10]. 其中, 全局算法雖然在理論上能得到二劃分問題的最優解, 但因為其存在復雜度過高的不足, 故僅適用于極小規模的問題; 啟發式迭代改進算法通過改變頂點的所屬劃分迭代優化劃分的割邊數量, 算法一輪迭代的復雜度較低, 但迭代輪數無法控制, 并且算法具有極強的局部性; 進化算法具有較強的全局搜索能力, 但無論是將其直接用于二劃分問題的求解, 或是與其他二劃分算法結合使用, 皆因運行時間過長使得這類算法難以應用于實際問題; 多級劃分算法是目前應用最廣泛的二劃分算法, 其劃分質量與運行時間綜合表現最優.

多級劃分算法包含粗化階段、 初始劃分階段和細化階段, 粗化階段通過縮合頂點降低電路規模, 初始劃分階段在粗化的最終電路上執行劃分算法并擇優作為初始解, 細化階段逐步恢復電路并優化劃分結果. 由于初始劃分階段得到的初始解存在明顯的提升空間, 而且近年來集成電路布局算法的研究得到顯著推進[11-12], 所以本研究將二劃分問題轉化為離散布局問題. 在全局布局階段將其松弛為連續布局問題, 并用提出的算法進行求解, 在合法化階段將求得的解映射到對應的離散解空間, 最后在詳細布局階段使用局部優化算法進行優化. 實驗結果表明, 提出的劃分算法直接用于二劃分或嵌入到多級劃分算法中的初始劃分階段都是有效的.

1 相關介紹

1.1 集成電路二劃分問題描述

(1)

其中:ε稱為平衡參數, 即允許兩個劃分子集之間權重差異的大小.為后續書寫方便起見, 將c(V1)、c(V2)的下界用L表示, 上界用U表示.式(1)可轉換為

L≤c(V1),c(V2)≤U

(2)

兩個子集之間存在的連邊又稱為割邊, 每條割邊e滿足:e∩V1≠φ且e∩V2≠φ.則cuts(H,V1,V2):={e:e∩V1≠φ且e∩V2≠φ}表示一個二劃分的所有割邊, 所有割邊的權重之和可以表示為

(3)

結合式(2)和式(3)可建立集成電路二劃分問題的數學模型為

(4)

1.2 集成電路布局問題介紹

在電路布局問題中, 每個單元vi擁有寬和高兩個屬性, 并通過坐標(xi,yi)表示其中心位置.而電路布局問題主要研究在給定的布局區域W×H中, 如何在滿足平衡性約束的條件下, 根據一個或多個目標, 確認每個單元所處的位置. 其中, 平衡約束要求頂點在整個布局區域內的分布是均勻的. 在滿足均衡性約束的前提下, 布局算法主要通過布局的半周長線長(half-perimeter wirelength, HPWL)來衡量布局的質量. HPWL的定義為

電路布局算法目前主要分為3個階段: 全局布局、 合法化與詳細布局. 其中, 全局布局階段的目的是生成一個合法化算法可接受的解. 對于一個解是否可接受的判定與具體使用的合法化算法有關, 一般與單元(頂點)間重疊面積的大小相關; 合法化階段, 將全局布局的結果(往往不是電路布局的合法解)調整為一個電路布局的合法解; 詳細布局則是在合法化的基礎上, 以保持解的合法性為前提, 通過對解的細微調整, 提升解的質量, 并返回一個最終的布局解.

全局布局階段的目標是盡可能降低布局的半周長線長和單元間的重疊面積, 合法化階段使用的策略包括貪心地將不合法的單元移動到合法位置、 動態規劃、 線性規劃、 網絡流算法等方法; 詳細布局階段使用的策略有分支定界法、 模擬退火、 單元交換、 動態規劃等方法.

2 模型的建立與求解

2.1 布局模型

為滿足轉換后的離散布局問題與二劃分問題等價, 設立如下模型: 將區間[0, 1]與區間(1, 2]分別代表二劃分中的兩個劃分塊, 設超圖中每個頂點是長度1的線段, 頂點v的中心坐標xv表示頂點位置及頂點所屬劃分塊, 令xv∈{0.5, 1.5}, 模型如圖1所示.沿用劃分問題的記號, 兩個劃分塊可定義為V1={v:xv=0.5,v∈V},V2={v:xv=1.5,v∈V}.

圖1 布局模型Fig.1 Placement model

用Φ(e,i)表示超邊e在劃分塊Vi中關聯的頂點個數, 那么可以定義劃分產生的割邊集合cuts(H,V1,V2)={e:Φ(e, 1)>0且Φ(e, 2)>0}.

從圖1可以看出, 當所有頂點的中心都處于0.5或1.5處時, 該布局模型的HPWL(x)等于二劃分問題(4)中的目標函數. 即

設超圖的頂點數|V|=n, 于是二劃分問題(4)等價于如下離散布局問題的數學模型, 即

(5)

2.2 一維泊松方程推導結果

鑒于泊松方程在布局算法中表現優異, 使用泊松方程建立的密度函數作為優化中的罰函數. 參考ePlace[11]與pPlace[12]關于二維泊松方程的討論, 結合本研究的布局模型, 得到一維泊松方程形式及其邊界條件, 有

(6)

(7)

當所有的頂點權重均勻地分布在0.5與1.5處時, 全局的密度分布是均勻的. 根據φ(x)的形式可知, 對所有頂點求φ′(x)需要O(n2)的時間復雜度.為降低時間復雜度, 用φ′(0.5)和φ′(1.5)的加權平均值近似頂點的導數, 權重為頂點與兩個部分的重疊面積.即

φ′(xi)=(1.5-xi)φ′(0.5)+(xi-0.5)φ′(1.5)

(8)

由式(8)可證明, 當0≤x≤2且?1≤i≤n, 0≤xi≤2時,φ′(0.5)=φ′(1.5)=0的充要條件為

這說明式(8)的計算方式是可行的.

2.3 松弛問題求解

將式(7)作為懲罰項加入模型(5)的目標函數中, 可得到全局布局階段要優化的目標函數為

(9)

同時, 將xi的取值范圍松弛至[0.5, 1.5]. 于是, 原本離散的布局問題的數學模型(5)變成一個連續優化問題的數學模型為

并且使用Nesterov[11]方法進行優化.

在合法化階段, 需要將全局布局階段得到的連續解, 映射至原問題離散解空間上. 因此, 將所有頂點的坐標調整為

從而得到該離散布局問題的一個合法解.

由于HPWL和割邊等價, 在詳細布局階段使用FM算法對解進行迭代優化. 其中, 頂點移動意味著頂點從0.5的坐標位置移動到1.5, 或者從1.5移動到0.5. 迭代結束后, 便得到問題的最終解.

2.4 算法流程

2.4.1初始解設置

利用隨機算法、 裝箱算法、 寬度優先搜索算法、 貪心圖增長算法[13]、 標簽傳遞算法[14]在劃分過程中, 對頂點確認所屬劃分的順序產生本研究提出的劃分方法的初始解. 除隨機算法外, 其他劃分算法有一共同特點: 頂點確定所屬的劃分存在先后次序, 更符合算法設定標準的頂點越早加入劃分. 由于寬度優先搜索算法往往在搜索到占總頂點權重一半的頂點時停止搜索, 將搜索到的頂點歸入劃分塊V1, 這就使得另一劃分塊V2中的頂點并沒有加入劃分的順序.因此, 對寬度優先搜索算法進行修改, 采用如下方式獲得初始解: 當搜索到頂點權重一半的頂點時搜索并不停止, 而是持續搜索整張圖, 并記錄下最后一個搜索到的頂點, 從這個頂點出發, 再利用寬度優先搜索, 獲得V2中頂點的順序. 如此, 在得到兩個劃分塊各自加入頂點的順序后, 按照順序分別將一定比例的頂點放置在0.5與1.5處, 并將剩余的頂點放置于1.0處.

2.4.2圖結構轉換

無論是HPWL還是關于HPWL的近似模型LSE、 WA等, 只有超邊上坐標處于最左或最右的頂點的偏導數非0. 而對于劃分問題而言, 一條超邊若為割邊, 則需要優化的頂點往往不止有左右端兩個頂點, 因此, 對于每條割邊而言, 在優化過程中, 不僅最左與最右的兩個頂點需要有收縮的趨勢, 其他頂點也應該有收縮的趨勢. 所以, 在對超圖進行優化時, 將超圖轉化為星型圖以達到該效果. 星型圖將超圖中的每條超邊e轉化為一個頂點, 該頂點與對應超邊所關聯的頂點鄰接.星型圖G(V′E′)的定義為

其中, 所有超邊轉換而來的頂點v′(v′∈E?V′)的坐標由其對應超邊關聯的頂點的坐標加權得到.即

由于這些頂點只起標識作用, 不影響劃分結果, 因此并不直接參與優化, 只在所有頂點完成一輪移動后, 根據公式更新其坐標, 也不考慮其權重.

2.4.3預處理

由于HPWL(x)非二階可微, 參照ePlace[11]的調整策略, 用頂點的度代替HPWL(x)的二階偏導數為

(10)

其中:Ei代表所有與頂點vi相連的超邊的集合.

由于密度函數非凸, 參照ePlace[11]的做法, 采用如下方法估計其二階偏導數, 即

(11)

由式(9)～(11)可得

(12)

于是, 海森矩陣的估計為

(13)

2.4.4罰參數更新

為了使初始時密度函數的導數與線長部分的偏導數平衡, 設置罰參數的初始值,有

罰參數的更新方式為λk=μk·λk-1.ΔHPWLk=HPWL(xk)-HPWL(xk-1),μ0=1.04.其中, ΔHPWLref表示每輪迭代所期待增加的線長值, 將其定義為ΔHPWLref=10%·HPWL0, HPWL0表示初始解對應的線長.

2.4.5算法偽代碼

本研究提出的二劃分方法先是利用調整后的寬度優先劃分算法得到兩個劃分塊加入頂點的順序, 以此獲取布局模型的初始解, 然后使用Nesterov方法進行優化. 將優化后的解進行合法化處理, 并使用局部優化算法進行改進. 具體的算法偽代碼如下所示.

算法: 平衡二劃分的非線性布局方法

輸入: 超圖H(V′E′), 固定頂點權重比例β, 平衡參數ε

輸出: 超圖H(V′E′)的劃分結果

1: (vec1, vec2)=simple_bipartition(H)//使用簡單的劃分算法得到頂點加入劃分的順序

2: 星型圖G(V,E)=star_graph(H,ε)//超圖轉換為星型圖

3: intial_placement(vec1, vec2,β)//獲得布局初始解

4:k=1//迭代輪數初始化為1

6: while ! is_balanced(x) andk

7: Nesterov_optimize(x)//使用Nesterov方法優化(使用預處理后的梯度)

9: end while

10: (V1,V2)=legalization(x)//根據坐標進行合法化得到劃分

11: FM(G,V1,V2,ε)//使用FM算法進行局部優化

3 實驗結果與分析

本研究采用ISPD98標準測試樣例對所提出的非線性優化方法進行測試與分析. ISPD98標準測試樣例中各個測試樣例的數據說明詳見參考文獻[12]. 實驗所涉及的算法均使用C++編譯, 實驗環境為CPU AMD Ryzen7 4 800 H, 8核, 主頻2.9 GHz.

表1展示了本研究提出的二劃分算法與加州大學圣地亞戈分校提供的FM算法開源代碼直接對ISPD98標準測試樣例進行劃分得到的實驗結果. 從表1可以看出, 本算法相較于FM算法在劃分質量上有著十分顯著的提升, 但運行時間卻接近FM算法的10.5倍.

表1 與FM算法實驗結果對比Tab.1 Comparison of results with FM

因此, 額外考慮將提出的算法嵌入到多級劃分算法中的初始劃分階段, 得到Modified KaHyPar. 利用Modified KaHyPar和原始的KaHyPar進行實際的劃分實驗, 得到表2的實驗結果. 從表2中觀察到Modified KaHyPar對比于KaHyPar, 雖然在劃分質量上的提升低于表1中與FM算法的對比, 但時間上的差距也大幅降低. 這兩組實驗均設置平衡參數ε=0.1, 運行時間的單位均為s, 最后一行平均比率表示對比項的平均比例.

表2 與KaHyPar實驗結果對比Tab.2 Comparison of results with KaHyPar

4 結語

將二劃分問題轉化為一維離散布局問題, 并將其松弛為連續布局問題, 然后使用非線性優化方法求解, 將所得的連續解合法化后, 利用FM算法進行優化. 在ISPD98測試樣例上的實驗結果表明, 將多級劃分算法KaHyPar的初始劃分算法替換為上述算法較KaHyPar算法更有效. 在以后的研究中, 可以進一步考慮在連續優化過程中加入啟發式方法以提升結果質量, 并通過改進數據結構、 程序邏輯與計算方法提升運行速度.