正態分布評價方式的布局擁擠度優化方法

虞 健，周洋洋，王新晨

（無錫中微億芯有限公司，江蘇無錫 214072）

1 引言

布局是FPGA配套設計工具中非常重要的模塊，布局質量的好壞直接影響著整個用戶設計的實現。布局模式一般分為非時序驅動模式布局和時序驅動模式布局兩種。在傳統做法中，非時序驅動模式布局一般以線長作為優化目標，時序驅動模式布局一般以時序和線長兩個因素作為優化目標。在實際應用設計中由于一般用戶設計都帶有時序約束，因此主要采用時序驅動模式布局。然而由于實際芯片上邏輯資源、模塊間互聯線資源等數量有限，理論上以線長和時序的優化結果不能完全反映最終的布局結果質量。如在互聯線利用率比較高的區域，會存在模塊間互聯線的競爭關系，從而影響到后續布線流程的效率，最終影響用戶設計質量[1]。為使布局算法能夠更準確地反映芯片實際的資源競爭關系，從而提高布局質量，本文提出了一種基于正態分布評價方式的布局擁擠度優化方法，將布線擁擠度因素提前考慮到布局中。

2 基于模擬退火算法的時序驅動模式布局算法

模擬退火算法來源于固體退火原理，將固體加溫至充分高溫，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。根據Metropolis準則，粒子在溫度T時趨于平衡的概率為exp[-ΔE/(kT)]，其中E為溫度T時的內能，ΔE為其改變量，k為玻爾茲曼常數。用固體退火模擬組合優化問題，將內能E模擬為目標函數值f，溫度T演化成控制參數t，即得到解組合優化問題的模擬退火算法：由初始解i和控制參數初值t開始，對當前解重復“產生新解→計算目標函數差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優解，這是基于蒙特卡羅迭代求解法的一種啟發式隨機搜索過程。退火過程由冷卻進度表控制，包括控制參數的初值t及其衰減因子Δt、每個t值時的迭代次數L和停止條件S。

模擬退火算法可以分解為解空間、目標函數和初始解3部分。

模擬退火的基本思想如下。

(1)初始化：初始溫度T0(充分大)，初始解狀態S（是算法迭代的起點），每個T值的迭代次數L；

(2)對k=1,2,...,L做第3至第6步；

(3)產生新解S′；

(4)計算增量ΔC=C(S′)-C(S)，其中C(S)為評價函數；

(5)若ΔC<0則接受S′作為新的當前解，否則以概率exp(-ΔC/T)接受S′作為新的當前解；

(6)如果滿足終止條件則輸出當前解作為最優解，結束程序，終止條件通常取為連續若干個新解都沒有被接受時終止算法；

(7)T逐漸減少，并不斷趨近于0，每次T減少后轉第2步，進行下一溫度的迭代。

模擬退火算法是布局實現的經典算法之一，著名的VTR系統中布局模塊就是使用的模擬退火算法[2]。

2.1 代價函數的構建

傳統模擬退火布局算法都以線長和時序作為優化目標，將這兩個因素通過構建代價函數輸入到算法中。在退火過程中，通過分析代價函數的變化來確定接受或者不接受節點移動。

2.1.1線長代價函數構建

在模擬退火算法中，一個用戶設計網表可以描述為一張超圖G=（V，E），其中V代表網表中的所有基本邏輯單元，E代表網表中的所有連接線。在以線長為優化目標時，一般都以線網半周長來構建代價函數[3]。圖1為半周長示意圖，圖中有網表中一條連接線的連接關系，其中點A為源頭端，點B、C、D、E、F為負載端。那么對于該條連接線的線長評價計算為連接線上所有節點最大坐標范圍的半周長，如圖1中紅線所示，即maxi∈e xi-minj∈e xj+maxi∈e yi-minj∈e yj，其中e代表整個網表連接線集合E中的一條連接線，xi，xj代表節點的x坐標，yi，yj代表節點y坐標。即網表中節點所占x方向的最大長度和y方向最大長度之和[6]。

圖1 半周長示意圖

對于整個網表，以線網半周長來構建代價函數為所有連接線的半周長之和，即H=∑e∈E(maxi∈e ximinj∈e xj+maxi∈e yi-minj∈eyj)，其中H代表線網半周長。

2.1.2時序代價函數構建

在時序模式中，通過時序分析引擎可以分析出每一個連接點的建立保持余量。當余量值為正時表示該連接點時序合法，負值時表示不合法，余量值為最小的節點代表當前設計中時序最差的情況[4]。每一個負載節點都有一個延時值，表示從源節點到當前負載點的線的延時。圖2為延時示意圖，節點F上的延時值表示該虛線的信號傳輸延時。在構建代價函數時，以所有負載節點的延時值和當前節點余量值的權重綜合考慮，即J=∑v∈V[D×(Sworst-Scurrent)/Sworst]，其中J代表時序代價函數，D代表負載點的延時值，S代表時序余量，(Sworst-Scurrent)/Sworst項代表當前節點跟設計中時序最差節點對比后所占的權重值。

圖2 延時示意圖

2.1.3時序目標函數與線長目標函數的歸一化處理

在模擬退火算法中，需要將這兩個代價函數擬合成一個最終代價函數。但是由于計算線長和時序的目標函數最終得出的代價值經常不在一個數量級上，因此在算法中需要將這兩個因素的數量級拉到同一水平上。即F=H/J，得出線長代價與時序代價的比例系數，其中F代表比例因素。在后續模擬退火算法中計算時序變化時都需要乘以F。

經過歸一化處理后，最終的代價函數可以歸結為C=Whpw1×H+Wtiming×J×F，其中，C代表最終代價函數，Whpw1代表線長所占權重，Wtiming代表時序所占權重。在模擬退火算法中，每次節點移動都根據Cost值的變化來確定是否接受移動結果[7]。

2.2 模擬退火算法流程

模擬退火布局算法流程如圖3所示，分為讀入用戶網表、初始布局形成初始解、基于初始解構建代價函數、產生新解判斷是否接受、接受新解替換舊解、達到退出條件時退出。其核心模塊主要有如下5個步驟：

圖3 模擬退火算法流程

第1步是產生初始解，通過隨機的方式對每個節點給定一個合法的初始位置，形成初始解，求得初始代價和決定退火初始溫度。

第2步是由一個產生函數從當前解產生一個位于解空間的新解；為便于后續的計算和接受，減少算法耗時，通常選擇由當前新解經過簡單的變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。

第3步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分產生，所以目標函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目標函數差的最快方法。

第4步是判斷新解是否被接受，判斷的依據是一個接受準則，最常用的接受準則是Metropolis準則：若ΔC<0則接受S′作為新的當前解S，否則以概率exp(-ΔC/T)接受S′作為新的當前解S。其中ΔC代表代價函數變化。

第5步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應于產生新解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一次迭代，可在此基礎上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續下一輪試驗[5,8]。

3 基于正態分布評價方式的布局擁擠度模型優化

由于線長和時序的布局模型不能完全反映芯片后續步驟布線的實際情況，當布局把繞線資源競爭比較多的模塊放得比較靠近時，會大大影響布線效率，從而影響整體設計最終結果的質量。為了解決此問題，本文提出了一種正態分布式的布局擁擠度評估模型，并應用到模擬退火算法中，達到優化布局結果的效果。

3.1 基于正態分布的擁擠度評估模型建立

在算法模型中，每一個節點上的連接線都需要通過端口輸入輸出，而輸出端口比較固定，很少出現資源競爭問題，因此本文提出以模塊被連接的輸入端口數量來代表當前模塊所需要占用連接線資源的數量。圖4為單個節點擁擠度計算示意圖，模塊有6個輸入端口和3個輸出端口被連接，那么在模塊擁擠度計算時，其擁擠度代價Ccost=6。

圖4 單個節點擁擠度計算示意圖

在實際布線過程中，擁擠度并不只看當前節點的資源占用數量。布線資源競爭如圖5所示，對中心點進行布線時不僅要考慮到當前節點資源競爭問題，還需要考慮到周圍節點資源的使用情況。當一根線進入該區域時，如果被周圍其他邏輯單元的某一傳輸信號A使用了，那么當前邏輯單元非傳輸信號A的走線就不能再使用這條邏輯資源線，從而會產生資源競爭。

圖5 布線資源競爭

芯片邏輯資源情形如圖6所示，圖中有9條布線資源線，其中線1、2有3個輸出口，線3、4、5有2個輸出口，線6、7、8、9有1個輸出口。那么對于D點，其自身在繞線時互相有競爭關系的線有3條，為線2、3、9。與之距離為1的C點跟其有競爭關系的連接線有2條為線2、3，與之距離為2的B點跟其有競爭關系的連接線有1條為線2，與之距離為3的A點跟其有競爭關系的連接線有0條。針對此情況，可以認為距離當前節點越近的其他節點與當前節點的競爭關系越激烈。距離越遠繞線資源競爭關系越小，此特征符合正態分布關系。因此本文提出了基于正態分布模型來評估周圍節點對當前節點影響的方法，從而形成正態分布函數其中x代表與當前節點的坐標偏離，假設當前節點對擁擠度影響因素為1，則f(0)=1。假設基于當前節點為中心的正態分布，則μ=0，從而可以求出樣本方差σ=1.13。根據正態分布公式，可以得出每個節點距離當前節點的位置來求出相應的影響因子，從而得出當前節點的擁擠度代價為Ci=∑v∈V[Ccost×f(x)]，將每個節點的擁擠度代價相加，得出整個網表的擁擠度代價其中n代表網表中節點數量。另外正態分布的因子μ和σ可以根據各個器件資源競爭情況進行調整，得出合適的值。

圖6 芯片布線資源

3.2 模擬退火算法中擁擠度模型應用

與傳統模擬退火算法不同，基于擁擠度模型的模擬退火算法需要在原有的代價函數上增加一個擁擠度代價因子，即代價函數變為：C=Whpw1×H+Wtiming×T×Ftiming+Wcongestion×Ccongestion×Fcongestion，其中Wcongestion代表擁擠度因素所占權重，Fcongestion是通過2.1.3節方法對擁擠度代價歸一化處理后得出的比例因子。

將新的代價函數替換原來模擬退火算法中的代價函數，進行退火求解，從而可以得出基于擁擠度的布局結果。

4 試驗結果

一般評價布局結果的質量有兩個方面：第一是布線運行時間，布線時間越短，布局質量越好；第二是布線后最差路徑的時序余量（Slack），余量越大，質量越好。本文所提出的基于正態分布擁擠度模型的模擬退火布局算法與傳統的基于時序模擬退火布局算法進行了試驗對比。將布局結果分別用相同的布線器進行布線，通過對比布線的運行時間和最差時序建立余量兩方面來評價最終布局結果的好壞。測試用例選用了客戶實際用例中規模比較大的一些，其中測試用例X1、X2、X4、with_dsp包含slice、dsp、bram、iob邏輯資源，fixpt、syn測試用例不含有bram資源，no_dsp測試用 例 不 含 有dsp資 源，aes、ecg、noc、mac、smith、arm9_24、arm9_22不含有dsp和bram資源，具體每個測試用例邏輯資源占用數量如表1所示。

表1 試驗結果對比

如表中布線運行時間列所示，基于正態分布擁擠度模型的模擬退火布局算法得出的布局結果相較于傳統的基于時序模擬退火布局算法得出的布局結果，相同布線器布線時間平均下降23.32%。

如表中最差時序余量列所示，基于正態分布擁擠度模型的模擬退火布局算法得出的布局結果相較于傳統的基于時序模擬退火布局算法得出的布局結果，相同布線器得出的平均最差時序建立余量波動較小，影響不大。

5 結論

本文提出了一種基于正態分布擁擠度模型的模擬退火布局算法，通過試驗對比，得出本文所提出的方法是有效可行的，該方法可以在對設計時序影響不大的情況下大大降低布線時間，從而證明可以化簡布線時繞線資源的競爭關系，達到優化整個用戶設計的目的。本文所提出的方法也有一定局限性：用戶設計比較簡單時，擁擠度因素相較于線長和時序因素比較次要，因此不一定能達到優化布局結果的作用；代價函數參數的調整也需要大量的試驗去進行摸索，包括正態分布函數中和值的確定，后續將對該方面進行大量測試用例的試驗分析；試驗結果中有些情況利用擁擠度模型布局后布線運行時間增加，分析原因為布局結果后網表中Slack值接近的節點數量增加，導致布線時很多節點繞線優先度區分不開，增加了布線時間，后續將根據這方面缺陷進行改進。