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

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

1 引言

現(xiàn)場可編程邏輯門陣列(Field-Programmable Gate Array,FPGA)是一種可以根據(jù)用戶需要來編程以改變其內(nèi)部功能的通用型芯片，這種芯片以其使用靈活、成本低廉的特點(diǎn)而受到廣泛的青睞。電子設(shè)計(jì)自動(dòng)化(Electronic Design Automation,EDA)工具在FPGA的推廣和使用中扮演著舉足輕重的角色，這一過程主要包括綜合、打包、布局、布線、仿真驗(yàn)證、位流下載等。其中布局是本文研究的重點(diǎn)，也是整個(gè)EDA流程中至關(guān)重要的環(huán)節(jié)。

布局是將網(wǎng)表中的邏輯單元與實(shí)際電路的物理位置建立一一對應(yīng)關(guān)系的過程。布局首先要保證電路符合既定的約束條件，在這個(gè)前提下再進(jìn)行布局質(zhì)量的優(yōu)化，其中線長、延時(shí)、功耗等都是可以考慮的指標(biāo)。當(dāng)前的布局算法大致可以分為三類：基于劃分的算法如MHP算法[1]，基于解析的算法如使用最小二乘法求解[2]，基于啟發(fā)式搜索的算法如模擬退火算法[3]。本文主要基于模擬退火算法，該算法通過設(shè)置評價(jià)函數(shù)并依據(jù)評價(jià)函數(shù)不斷交換布局模塊的位置來搜索最優(yōu)的布局。

2 傳統(tǒng)模擬退火布局

在傳統(tǒng)模擬退火布局開始之前首先要經(jīng)歷打包的過程。打包首先將觸發(fā)器 (flip-flop，F(xiàn)F)和查找表(Look-Up-Table，LUT)進(jìn)行一對一的配對并封裝為基本邏輯單元(basic logic element，BLE)，然后根據(jù)一定約束和優(yōu)化條件將若干個(gè)BLE放入一個(gè)可配置邏輯塊(Configurable Logic Block，CLB)中，在此后的過程中CLB內(nèi)部的配置不再發(fā)生改變。

布局基于打包階段生成的CLB級網(wǎng)表進(jìn)行。圖1所示為傳統(tǒng)模擬退火算法的基本流程。首先生成一個(gè)初始布局狀態(tài)，這一狀態(tài)一般是隨機(jī)生成的，然后在初始布局的基礎(chǔ)上進(jìn)行若干次交換并計(jì)算出初始溫度，初始半徑一般設(shè)置為芯片長度。布局的主體部分分為內(nèi)外兩層循環(huán)，外循環(huán)控制溫度和交換半徑，內(nèi)循環(huán)交換CLB。每一次內(nèi)循環(huán)中僅選定一個(gè)CLB，然后根據(jù)當(dāng)前的交換半徑選取一個(gè)芯片上的位置(site)，如果site空置則直接將選定的CLB移動(dòng)到site上，如果site上已有CLB放置則交換兩個(gè)CLB。移動(dòng)CLB后，根據(jù)事先設(shè)定的評價(jià)函數(shù)計(jì)算出評價(jià)值的變化量ΔC，評價(jià)函數(shù)一般可以使用線長、延時(shí)、擁擠等作為參數(shù)。如果ΔC≤0，則直接接受該交換；若ΔC＞0，則以的概率接受交換[4]。這樣算法便具有了接受差解的能力即爬坡能力。接受或拒絕交換后，一次內(nèi)循環(huán)結(jié)束，判斷是否達(dá)到了內(nèi)循環(huán)的迭代上限，若未達(dá)到則繼續(xù)下一次CLB的選取；若達(dá)到則退出內(nèi)循環(huán)。內(nèi)循環(huán)退出后在外循環(huán)中更新溫度和交換半徑，并判斷是否達(dá)到外循環(huán)退出溫度，若達(dá)到則退出，未達(dá)到則再次進(jìn)入內(nèi)循環(huán)。外循環(huán)退出后，將溫度設(shè)置為0，這時(shí)候只能接受使布局變好的交換，進(jìn)行若干次交換后算法結(jié)束。

圖1 傳統(tǒng)模擬退火算法流程圖

3 BLE級模擬退火布局實(shí)現(xiàn)

本文基于Virtex-5芯片結(jié)構(gòu)實(shí)現(xiàn)了BLE級的布局，布局的大體過程與傳統(tǒng)的模擬退火算法相似，但也有一些不同的地方。

3.1 布局開始前的處理

一個(gè)Virtex-5芯片的CLB包含了兩個(gè)slice和一個(gè)開關(guān)矩陣，每個(gè)slice又可以包含最多4個(gè)BLE，如圖2即為一個(gè)slice。程序在打包階段不生成CLB級網(wǎng)表，而是直接將BLE級網(wǎng)表傳遞給布局使用，在布局結(jié)束后再生成slice級網(wǎng)表供布線使用。

3.2 初始狀態(tài)的生成

模擬退火開始之前先使用二次線性規(guī)劃算法進(jìn)行布局，得到一個(gè)較優(yōu)的布局狀態(tài)，并以此作為模擬退火的初始布局。在這個(gè)布局上進(jìn)行若干次交換并記錄其評價(jià)值，以此計(jì)算出模擬退火的初始溫度，但這里所進(jìn)行的交換均被拒絕，僅記錄下交換后的評價(jià)值，從而保護(hù)二次線性規(guī)劃算法生成的較優(yōu)的布局狀態(tài)不被破壞。由于已經(jīng)有了較優(yōu)的布局，初始的交換半徑也不再設(shè)置為整個(gè)芯片的長度而是直接設(shè)置為1。

3.3 內(nèi)循環(huán)

首先隨機(jī)選定一個(gè)交換單元，這個(gè)單元可能是一個(gè)BLE，也可以是DSP等其他Virtex-5芯片中存在的復(fù)雜單元。若選中的是一個(gè)slice型的單元?jiǎng)t使用交換半徑來約束其交換的可達(dá)空間，在可達(dá)空間中隨機(jī)選定一個(gè)site后又分為幾種情況：（1）site空置，則直接將選定的單元移動(dòng)到site上；（2）site上已有BLE放置但未滿，則隨機(jī)選擇放置到空位上或者與其中一個(gè)BLE交換，空置的位置越大放在空位上的幾率也越大，但不論是放置到空位還是進(jìn)行交換，都必須先對其控制信號進(jìn)行一致性的檢測，若不一致則需重新選擇其他site；（3）site上已放滿，則隨機(jī)選擇一個(gè)BLE進(jìn)行交換，并檢測控制信號的一致性。如果多次單一單元的交換均失敗，則將選定單元所在site上所有的單元與選定site上所有的單元進(jìn)行整體交換。若選中的不是一個(gè)slice型的單元?jiǎng)t不使用交換半徑，直接在全芯片范圍內(nèi)選擇一個(gè)相同類型的site進(jìn)行交換。圖3是選擇和交換過程的流程圖。交換后，使用基于線網(wǎng)邊界框半周長的評價(jià)函數(shù)對交換后的結(jié)果進(jìn)行評價(jià)，計(jì)算出評價(jià)值的變化量ΔC。若ΔC≤0，則直接接受該交換；若 ΔC＞0，則以的概率接受交換。一次內(nèi)循環(huán)結(jié)束后，判斷是否達(dá)到內(nèi)循環(huán)迭代上限，達(dá)到則退出。

圖2 slice示例圖

3.4 外循環(huán)

內(nèi)循環(huán)達(dá)到迭代上限退出后進(jìn)入外循環(huán)中。由于已經(jīng)在初始化時(shí)將交換半徑設(shè)置為1，外循環(huán)中不再更新交換半徑。外循環(huán)中以分段線性下降的方式更新溫度。但在前6次更新溫度時(shí)若當(dāng)前布局的評價(jià)值小于初始布局的評價(jià)值，則溫度反而會(huì)上升。這一過程是為了增大模擬退火算法的搜索空間，使其向全局最優(yōu)解收斂。表1即為溫度更新的規(guī)則，t表示溫度，curscore為當(dāng)前布局的總評價(jià)值，initscore為初始狀態(tài)的總評價(jià)值，outer_iter代表外循環(huán)的次數(shù)，rejrate代表交換被拒絕的比例。更新完溫度后判斷是否達(dá)到外循環(huán)退出溫度，若未達(dá)到則重新進(jìn)入內(nèi)循環(huán)，若達(dá)到則退出外循環(huán)。

3.5 布局結(jié)束

外循環(huán)退出后將溫度置為0，此時(shí)只能接受使布局變好的交換，進(jìn)行若干次交換后確定最終布局并生成slice級網(wǎng)表，布局結(jié)束。

表1 溫度更新規(guī)則表

4 布局驗(yàn)證

布局結(jié)束后，將其結(jié)果保存為xdl文件，再使用Xilinx的XDL工具來驗(yàn)證其正確性。

使用18位累加器作為測試用例，該用例中除了普通的BLE單元外還有分布式RAM和DSP等復(fù)雜單元。在使用本文提出的BLE級布局處理電路之后將其結(jié)果保存為XDL文件，命名為ae18_core_place.xdl。使用Xilinx工具ISE Design Suite 64 Bit Command Prompt，輸入 xdl-xdl2ncd ae18_core_place.xdl命令，驗(yàn)證布局結(jié)果的正確性，其結(jié)果如圖4所示，轉(zhuǎn)換成功即代表布局信息合法。

圖3 BLE級模擬退火算法流程圖

圖4 驗(yàn)證布局結(jié)果

5 結(jié)論和展望

本文實(shí)現(xiàn)了一種BLE級的布局算法并驗(yàn)證了其正確性。這種算法不同于傳統(tǒng)的CLB級布局算法，它允許在打包之后仍可以改變CLB內(nèi)部配置，理論上可以增大解集以求獲得更好的解，今后的研究中將基于本文實(shí)現(xiàn)的算法嘗試改進(jìn)和優(yōu)化。

參考文獻(xiàn)：

[1]G Karypis,R Aggarwal,V Kumar.Multilevel Hypergraph Partitioning:Application in VLSI domin[C].IEEE Transactions on Very Large Scale Integration (VLSI)Systems.1999.69-79.

[2]謝志宏.FPGA布局布線算法的研究和優(yōu)化[D].西安：西安電子科技大學(xué)，2012.

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

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