一種綜合型FPGA布局算法

王新晨，許 慧，虞 健，惠 鋒

（1.中國(guó)電子科技集團(tuán)公司第五十八研究所，江蘇無錫 214072;2.無錫中微億芯有限公司，江蘇無錫 214072）

1 引言

現(xiàn)場(chǎng)可編程邏輯門陣列(Field-Programmable Gate Array,FPGA)近年來越來越多地應(yīng)用到各種各樣的場(chǎng)合，其可實(shí)現(xiàn)的功能越來越多，電路的規(guī)模也越來越大。電子設(shè)計(jì)自動(dòng)化 (Electronic Design Automation,EDA)工具在FPGA的應(yīng)用中起著關(guān)鍵作用，F(xiàn)PGA的快速發(fā)展也對(duì)EDA工具提出更高要求。EDA的主要流程有綜合、打包、布局、布線、仿真驗(yàn)證、位流下載等。

布局是影響EDA工具運(yùn)行速度及電路最終質(zhì)量的關(guān)鍵一步，它將布局網(wǎng)表中的邏輯單元一一映射到芯片的實(shí)際位置?，F(xiàn)有的主流算法中，模擬退火算法[1]可以以1的概率逼近全局最優(yōu)解，但較為緩慢；二次線性規(guī)劃算法[2]雖然能快速得出結(jié)果，但往往在解的質(zhì)量上遜色不少。單一使用一種算法已不能快速有效地解決布局問題，許多取長(zhǎng)補(bǔ)短的結(jié)合型算法因此出現(xiàn)。本文結(jié)合了二次線性規(guī)劃算法和模擬退火算法并做出了一些改進(jìn)，力求能夠快速有效地解決布局問題。

2 綜合型算法概述

本文提出的綜合型算法流程如圖1所示，首先使用二次線性規(guī)劃算法，利用該算法快速得到解的特性，快速迭代得到一個(gè)較優(yōu)的布局情況。該算法使各邏輯單元相對(duì)均勻地分布在電路中并保持了較優(yōu)的相對(duì)位置，但這個(gè)結(jié)果往往占用電路面積較大。這時(shí)再使用模擬退火算法，因?yàn)橐呀?jīng)有了一個(gè)相對(duì)較好的布局情況，模擬退火算法不必從高溫開始迭代退火，而是選擇一個(gè)較低的溫度，使算法快速收斂。這樣結(jié)合使用兩種算法，既獲得了較高質(zhì)量的解，又保證程序較快的運(yùn)行速度。

圖1 綜合型算法流程圖

3 二次線性規(guī)劃算法及改進(jìn)

二次線性規(guī)劃算法是一種解析型算法，使用數(shù)學(xué)的方法求解矩陣，以得到理論的最優(yōu)解。該算法把所有的布局邏輯單元看作節(jié)點(diǎn)，把所有節(jié)點(diǎn)之間的信號(hào)關(guān)系建立成點(diǎn)到點(diǎn)的邊的關(guān)系即力，并以此建立矩陣，用一種類似于“彈簧伸縮”的方式迭代優(yōu)化布局狀態(tài)。如圖2所示，方格表示芯片上一定范圍的區(qū)域，該區(qū)域可容納一定數(shù)量的單元，布局的過程中允許出現(xiàn)放置單元超出容量的情況，即形成overlap，迭代過程不斷降低overlap，并最終通過合法化過程將overlap消除。

圖2 節(jié)點(diǎn)移動(dòng)過程圖

圖2中空心圓代表某次解矩陣后節(jié)點(diǎn)所在的位置，首先進(jìn)行展開的過程，將節(jié)點(diǎn)按照密度均衡的原則移動(dòng)至虛線圓點(diǎn)處，同時(shí)對(duì)每個(gè)節(jié)點(diǎn)加一個(gè)新的力，此時(shí)同一個(gè)區(qū)域內(nèi)的節(jié)點(diǎn)相對(duì)于其相應(yīng)邊界距離的伸縮比例相同，但實(shí)際移動(dòng)距離和施加的力卻不同，且其施加的力不能使節(jié)點(diǎn)在此位置保持力平衡[3]。

如式（1）所示，施加的新力force等于實(shí)際移動(dòng)距離 fx與 force_rate之積，force_rate由當(dāng)前區(qū)域的overlap情況決定，overlap越大，force_rate越大。

在下一次解矩陣后，力重新回到平衡狀態(tài)，由于各節(jié)點(diǎn)之間的連接關(guān)系不同，其收縮的力也有不同，各節(jié)點(diǎn)因而又各自移動(dòng)了不同的距離。圖2中實(shí)心圓即表示重新回到力平衡狀態(tài)后節(jié)點(diǎn)的位置。

在實(shí)際運(yùn)用中，特別是一些中、大規(guī)模電路中，往往有許多連接關(guān)系十分緊密的節(jié)點(diǎn)，它們從第一次解矩陣開始即分布在相同的位置，此后的伸縮過程也由于其緊密的關(guān)系導(dǎo)致每次伸縮的距離大致相同，節(jié)點(diǎn)之間的相對(duì)位置很難拉開，甚至合法化過程開始前依然處于同一個(gè)區(qū)域中。這樣關(guān)系緊密的節(jié)點(diǎn)越多，算法過程中overlap降低得越慢，合法化過程開始前的overlap率越高。這樣既影響了速度，也影響了質(zhì)量。

本文的算法在計(jì)算新施加的力時(shí)進(jìn)行了區(qū)別對(duì)待，對(duì)于overlap小的區(qū)域，仍然按照原有公式計(jì)算，對(duì)于overlap大的區(qū)域，則在原有公式的基礎(chǔ)上加入一個(gè)擾動(dòng)，見式（2）：

其中α代表所加的擾動(dòng)，在操作每個(gè)適用區(qū)域時(shí)，α首先取一個(gè)很小的值，然后每對(duì)一個(gè)節(jié)點(diǎn)加力后，α就隨之增大，但也始終保持在一個(gè)較低的值。這樣一個(gè)小的擾動(dòng)既不會(huì)破壞原有節(jié)點(diǎn)間的相互關(guān)系，又可以使overlap加速變小，使節(jié)點(diǎn)分布更加均勻，從而在一定程度上提高了布局的質(zhì)量。

4 模擬退火算法及改進(jìn)

模擬退火算法是一種基于啟發(fā)式搜索的算法，它通過設(shè)置一個(gè)評(píng)價(jià)函數(shù)來評(píng)定當(dāng)前解的情況，并通過不斷迭代達(dá)到優(yōu)化的目的。該算法分為內(nèi)外兩層循環(huán)：每一次內(nèi)循環(huán)中，電路邏輯單元會(huì)進(jìn)行若干次位置交換，每次交換都使用評(píng)價(jià)函數(shù)進(jìn)行評(píng)估，然后判斷是否接受；每一次外循環(huán)都會(huì)更新溫度、交換半徑等控制參數(shù)，當(dāng)溫度達(dá)到一定低值時(shí)，退火過程結(jié)束，再進(jìn)行若干次零溫度迭代后算法結(jié)束。

初始溫度是模擬退火算法的重要參數(shù)。傳統(tǒng)的模擬退火算法使用一個(gè)隨機(jī)的布局作為初始狀態(tài)，在這個(gè)初始狀態(tài)的基礎(chǔ)上進(jìn)行若干次交換，求取其評(píng)價(jià)值的標(biāo)準(zhǔn)差，再計(jì)算出初始溫度，如式（3），T0即為初始溫度[4]。

T0往往是一個(gè)很高的溫度，在這個(gè)溫度下幾乎所有的交換都被接受，從而保證了模擬退火算法足夠大的解空間。但在結(jié)合型算法中，模擬退火算法前已經(jīng)使用二次線性規(guī)劃算法獲得了一個(gè)較優(yōu)的解，這時(shí)再使用高溫退火會(huì)使布局情況再度變得無序，破壞了二次線性規(guī)劃的結(jié)果。因此，本文提出的結(jié)合型算法使用式（4）計(jì)算 T0。

其中β由內(nèi)迭代的規(guī)模決定，內(nèi)迭代次數(shù)每上升一個(gè)數(shù)量級(jí)，β就下降一個(gè)數(shù)量級(jí)，當(dāng)內(nèi)迭代次數(shù)為10時(shí)β為2。

除了溫度，模擬退火算法中另一個(gè)重要的控制參數(shù)是交換半徑。傳統(tǒng)模擬退火算法在外循環(huán)中設(shè)置交換半徑來約束交換的范圍，最初交換半徑為芯片長(zhǎng)度，之后，交換半徑隨著溫度下降而變小，直至降為1。這樣的交換半徑變化配合溫度的變化，既可以保證足夠的解空間，又可以使算法逐漸收斂。

圖3 交換范圍示意圖

由于綜合型算法中的模擬退火算法緊跟二次線性規(guī)劃算法后使用，且已經(jīng)對(duì)初始溫度的計(jì)算做出修改，所以傳統(tǒng)的交換半徑計(jì)算方法也需要做出改變。本文算法在內(nèi)循環(huán)中確定被選中單元的交換范圍，而不是傳統(tǒng)模式的在外循環(huán)中統(tǒng)一設(shè)置。如圖3所示，被選中的交換單元有若干連接有線網(wǎng)的引腳，線網(wǎng)所連的其他單元用空心圓表示，圖3中虛線框恰好包含了一個(gè)線網(wǎng)的所有單元，稱為這個(gè)線網(wǎng)的邊界框。交換時(shí)，首先與傳統(tǒng)模擬退火算法相同，隨機(jī)選取一個(gè)要交換的單元，然后隨機(jī)選取被選中單元的一個(gè)有線網(wǎng)連接的引腳，獲取該引腳所在線網(wǎng)的邊界框，邊界框中的位置無論是否已有單元放置均為候選的位置，只需隨機(jī)選擇一個(gè)即可。

5 實(shí)驗(yàn)結(jié)果及討論

本文隨機(jī)選取了10個(gè)MCNC測(cè)試集中的電路，在Xilinx的xc5vlx330ff1760器件上分別使用本文提出的改進(jìn)的結(jié)合型算法和原版結(jié)合型算法進(jìn)行布局。設(shè)置quadratic重疊率5%或迭代次數(shù)達(dá)到1000次時(shí)退出迭代，測(cè)試結(jié)果如表1和表2所示。

表1 Quadratic迭代次數(shù)測(cè)試結(jié)果表

從表1中可以看出，對(duì)原本迭代次數(shù)就比較少的電路來說，對(duì)quadratic的改進(jìn)并不能造成影響，但對(duì)于迭代次數(shù)較多的電路卻有可觀的提高，尤其對(duì)于電路clma，在原版中該電路因達(dá)到迭代上限1000次而退出迭代，即原算法已不能使該電路有效展開，而在改進(jìn)算法后只需145次迭代即可達(dá)到要求，迭代次數(shù)的減少即代表時(shí)間的減少。

表2 布局后預(yù)估線長(zhǎng)測(cè)試結(jié)果表

此外，如表2所示，使用線長(zhǎng)來評(píng)估電路質(zhì)量，可以看到改進(jìn)后算法獲得了平均5.30%的提升。

6 結(jié)論

本文提出的綜合型算法在二次線性規(guī)劃算法和模擬退火算法上分別做出了改進(jìn)，使得算法可以在較短的時(shí)間內(nèi)給出質(zhì)量較高的布局結(jié)果，解決了現(xiàn)有的FPGA布局算法單獨(dú)應(yīng)用于布局問題時(shí)或需要耗費(fèi)太長(zhǎng)時(shí)間、或不能給出質(zhì)量較高解的問題。

[1]Metropolis,N A,A Rosenbluth.Equation of State Calculations by Fast Computing Machines[J].Journal of Chemieal Physies,1953,21:1087-7092.

[2]Myung-Chul Kim,Dong-Jin Lee,Igor L Markov.SimPL:An Effective Placement Algorithm[M].University of Michigan,2005.

[3]虞健.FPGA布局算法應(yīng)用研究[D].武漢：武漢理工大學(xué),2011.

[4]Vauglm Betz,Jonathan Rose.VPR:A New Packing,Placement and Routing Tool for FPGA Research[C].InternationalWorkshop on Field Programmable Logic and Applications,1997.