正態(tài)分布評價方式的布局擁擠度優(yōu)化方法

虞 健，周洋洋，王新晨

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

1 引言

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

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

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

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

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

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

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

(3)產(chǎn)生新解S′；

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

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

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

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

模擬退火算法是布局實現(xiàn)的經(jīng)典算法之一，著名的VTR系統(tǒng)中布局模塊就是使用的模擬退火算法[2]。

2.1 代價函數(shù)的構(gòu)建

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

2.1.1線長代價函數(shù)構(gòu)建

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

圖1 半周長示意圖

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

2.1.2時序代價函數(shù)構(gòu)建

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

圖2 延時示意圖

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

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

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

2.2 模擬退火算法流程

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

圖3 模擬退火算法流程

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

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

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

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

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

3 基于正態(tài)分布評價方式的布局擁擠度模型優(yōu)化

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

3.1 基于正態(tài)分布的擁擠度評估模型建立

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

圖4 單個節(jié)點擁擠度計算示意圖

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

圖5 布線資源競爭

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

圖6 芯片布線資源

3.2 模擬退火算法中擁擠度模型應(yīng)用

與傳統(tǒng)模擬退火算法不同，基于擁擠度模型的模擬退火算法需要在原有的代價函數(shù)上增加一個擁擠度代價因子，即代價函數(shù)變?yōu)椋篊=Whpw1×H+Wtiming×T×Ftiming+Wcongestion×Ccongestion×Fcongestion，其中Wcongestion代表擁擠度因素所占權(quán)重，F(xiàn)congestion是通過2.1.3節(jié)方法對擁擠度代價歸一化處理后得出的比例因子。

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

4 試驗結(jié)果

一般評價布局結(jié)果的質(zhì)量有兩個方面：第一是布線運行時間，布線時間越短，布局質(zhì)量越好；第二是布線后最差路徑的時序余量（Slack），余量越大，質(zhì)量越好。本文所提出的基于正態(tài)分布擁擠度模型的模擬退火布局算法與傳統(tǒng)的基于時序模擬退火布局算法進行了試驗對比。將布局結(jié)果分別用相同的布線器進行布線，通過對比布線的運行時間和最差時序建立余量兩方面來評價最終布局結(jié)果的好壞。測試用例選用了客戶實際用例中規(guī)模比較大的一些，其中測試用例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資源，具體每個測試用例邏輯資源占用數(shù)量如表1所示。

表1 試驗結(jié)果對比

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

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

5 結(jié)論

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