虞 健，周洋洋，王新晨

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

1 引言

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

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

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

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

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

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

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

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

(4)計(jì)算增量ΔC=C(S′)-C(S)，其中C(S)為評(píng)價(jià)函數(shù)；

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

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

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

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

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

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

2.1.1線長(zhǎng)代價(jià)函數(shù)構(gòu)建

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

圖1 半周長(zhǎng)示意圖

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

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

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

圖2 延時(shí)示意圖

2.1.3時(shí)序目標(biāo)函數(shù)與線長(zhǎng)目標(biāo)函數(shù)的歸一化處理

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

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

2.2 模擬退火算法流程

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

圖3 模擬退火算法流程

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

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

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

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

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

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

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

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

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

圖4 單個(gè)節(jié)點(diǎn)擁擠度計(jì)算示意圖

在實(shí)際布線過(guò)程中，擁擠度并不只看當(dāng)前節(jié)點(diǎn)的資源占用數(shù)量。布線資源競(jìng)爭(zhēng)如圖5所示，對(duì)中心點(diǎn)進(jìn)行布線時(shí)不僅要考慮到當(dāng)前節(jié)點(diǎn)資源競(jìng)爭(zhēng)問(wèn)題，還需要考慮到周?chē)?jié)點(diǎn)資源的使用情況。當(dāng)一根線進(jìn)入該區(qū)域時(shí)，如果被周?chē)渌壿媶卧哪骋粋鬏斝盘?hào)A使用了，那么當(dāng)前邏輯單元非傳輸信號(hào)A的走線就不能再使用這條邏輯資源線，從而會(huì)產(chǎn)生資源競(jìng)爭(zhēng)。

圖5 布線資源競(jìng)爭(zhēng)

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

圖6 芯片布線資源

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

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

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

4 試驗(yàn)結(jié)果

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

表1 試驗(yàn)結(jié)果對(duì)比

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

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

5 結(jié)論

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