一種利用資源協(xié)商的FPGA布局方法

王德奎

(西安電子科技大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，陜西西安710071)

隨著現(xiàn)場可編程門陣列(Field Programmable Gate Arrays，F(xiàn)PGA)和電路規(guī)模的增大，計算機(jī)輔助設(shè)計工具在對電路進(jìn)行編譯并配置到芯片時需要耗費更多的時間。對于現(xiàn)代大規(guī)模工業(yè)電路，現(xiàn)有的計算機(jī)輔助設(shè)計工具耗時幾個小時甚至一到兩天[1]。由于電路編譯耗時的增大，電路的設(shè)計調(diào)試周期也隨之變長，從而降低電路設(shè)計人員的開發(fā)效率以及現(xiàn)場可編程門陣列在市場上的競爭力。因此，減少電路編譯所需時間，已經(jīng)成為開發(fā)人員當(dāng)今主要研究方向之一。

現(xiàn)場可編程門陣列電路的設(shè)計流程包括行為綜合、工藝映射、打包、布局和布線，其中布局是最耗時的步驟之一[2]。目前，學(xué)術(shù)界權(quán)威的多用途布局布線工具(Versatile Place and Route，VPR)[3]在布局階段采用模擬退火算法，通過搜索大量的布局解空間并以一定的概率接受較差的解，最終找到一個較優(yōu)布局方案。但模擬退火布局算法運行時間長，隨著電路規(guī)模的增大，該缺點越來越明顯。文獻(xiàn)[4]采用并行編程技術(shù)將多用途布局布線工具模擬退火布局算法并行化，時間減少37.5%，同時電路延時降低4.2%。文獻(xiàn)[5]將遺傳算法應(yīng)用到現(xiàn)場可編程門陣列布局，并用布線器代替目標(biāo)評價函數(shù)；和多用途布局布線工具相比，電路延時降低8.4%，但布局運行時間增加了2 887倍。文獻(xiàn)[6]提出了基于劃分的布局算法，采用遞歸劃分將電路邏輯單元劃分到現(xiàn)場可編程門陣列上不同的區(qū)域，直到每個區(qū)域中的邏輯單元數(shù)量小于設(shè)定的閾值。和多用途布局布線工具相比，劃分布局方法可以取得較高的加速比，但是布局質(zhì)量較差。文獻(xiàn)[7-9]中提出的解析布局算法將布局優(yōu)化目標(biāo)函數(shù)近似成連續(xù)可導(dǎo)函數(shù)，并采用現(xiàn)有的求解器對目標(biāo)函數(shù)求最小值，從而得到全局最優(yōu)布局方案。解析布局算法耗時遠(yuǎn)小于模擬退火算法，但在將優(yōu)化目標(biāo)函數(shù)近似成連續(xù)可導(dǎo)函數(shù)時會存在誤差；另外，解析布局算法往往只能對一個優(yōu)化目標(biāo)進(jìn)行優(yōu)化，無法同時對多個目標(biāo)進(jìn)行優(yōu)化，目前常見的解析布局算法都是對電路總線長進(jìn)行優(yōu)化，而不考慮電路的延時。

為了避免上述方法的不足并提高布局的效率，筆者提出了新的利用資源協(xié)商的迭代布局方法，電路單元通過協(xié)商確定物理資源的分配使用；同時，利用低溫模擬退火算法對布局結(jié)果進(jìn)行局部優(yōu)化。實驗結(jié)果表明，所提出的布局方法能夠在保證布局質(zhì)量的前提下顯著減少布局所需時間。

1 基礎(chǔ)知識

1.1 現(xiàn)場可編程門陣列結(jié)構(gòu)

現(xiàn)場可編程門陣列已經(jīng)廣泛應(yīng)用于現(xiàn)代數(shù)字系統(tǒng)設(shè)計[10-12]。根據(jù)內(nèi)部資源結(jié)構(gòu)，目前商用現(xiàn)場可編程門陣列主要分為兩類：島型結(jié)構(gòu)和層次化結(jié)構(gòu)；多用途布局布線工具和賽靈思公司均采用島型結(jié)構(gòu)[13]。如圖1所示，島型結(jié)構(gòu)由3部分構(gòu)成：輸入輸出單元、可配置邏輯單元和可編程連線資源。輸入輸出單元分布在四周，是芯片和外圍電路的接口；目前大多數(shù)現(xiàn)場可編程門陣列在內(nèi)部嵌入數(shù)字信號處理器等異構(gòu)功能單元來擴(kuò)大芯片的靈活性。

圖1 簡單島型現(xiàn)場可編程門陣列結(jié)構(gòu)

圖2 打包后的電路網(wǎng)表

1.2 現(xiàn)場可編程門陣列電路布局

用硬件描述語言設(shè)計的電路經(jīng)過行為綜合、工藝映射、打包后轉(zhuǎn)化為電路網(wǎng)表〈V，E〉。電路網(wǎng)表由邏輯單元和單元之間的連接構(gòu)成，其中V表示邏輯單元集合，E表示邏輯單元之間連接的集合。圖2為打包后的電路網(wǎng)表，該電路網(wǎng)表中共有9個邏輯單元：V={vi| 0 ≤i< 9}, 其中v5、v6、v7和v8為可配置邏輯單元，其余為輸入輸出單元。圖2中各邏輯單元之間有向連接構(gòu)成的集合為：E={〈v0,v5〉, 〈v1,v7〉, 〈v1,v6〉, 〈v2,v6〉, 〈v5,v7〉, 〈v6,v8〉, 〈v7,v8〉, 〈v7,v3〉, 〈v8,v4〉}，其中〈v0,v5〉表示從v0到v5的連接。

現(xiàn)場可編程門陣列布局就是根據(jù)相應(yīng)的約束條件，確定電路網(wǎng)表中的各邏輯單元在物理芯片上的位置，每個位置坐標(biāo)都對應(yīng)唯一的可編程物理邏輯單元。布局是多目標(biāo)優(yōu)化問題，優(yōu)化目標(biāo)主要包括：(1)使電路中所有連接使用的連線資源總線長盡量短；(2)使電路的延時盡量小。

2 提出的布局方法

所提出的布局方法分為3個階段：(1)初始布局：為電路邏輯單元計算花費最小且類型相同的物理模塊資源，如果一個物理資源被多個邏輯單元同時占用，則稱該資源發(fā)生擁擠；(2)資源協(xié)商布局：迭代地對占用擁擠物理資源的邏輯單元重新布局，直到消除資源擁擠；(3)低溫模擬退火優(yōu)化：采用低溫模擬退火算法對布局結(jié)果進(jìn)行優(yōu)化。下面詳細(xì)介紹各布局階段，以及布局過程中用到的資源花費計算函數(shù)。

2.1 電路時序分析

通過對電路進(jìn)行時序分析，可以得到電路的延時和各連接的關(guān)鍵度。電路中延時最長的路徑稱為關(guān)鍵路徑，關(guān)鍵路徑延時決定了電路延時。對于連接，其關(guān)鍵度定義為

(1)

其中，D是關(guān)鍵路徑延時，As,t表示在不影響關(guān)鍵路徑前提下連接的延時裕量。因此，0

λb=max{βb,i} ， 1≤i≤Nb，

(2)

其中，Nb表示連到邏輯單元b的連接的數(shù)量，βb,i表示連到b的第i個連接的關(guān)鍵度。

2.2 花費計算函數(shù)

當(dāng)邏輯單元b使用坐標(biāo)為(x,y)的資源時，使用花費包括時序花費和資源擁擠花費，計算方式為

C(b,x,y)=λb·Tb+(1-λb)·Gx,y，

(3)

其中，Tb表示邏輯單元b占用資源(x,y)的時序花費，Gx, y為資源(x,y)的擁擠花費。λb是邏輯單元b的關(guān)鍵度且0 <λb≤ 1，通過λb來平衡資源擁擠花費和時需花費占總花費的比重；λb值越大，時序花費占總花費的比例越高。邏輯單元b使用資源(x,y)的時序花費Tb計算方法為

(4)

其中，βb,i和db,i分別表示連到邏輯單元b的第i個連接的關(guān)鍵度和延時；zb表示和b相連且已經(jīng)布局的邏輯單元數(shù)目。物理資源(x,y)的擁擠花費包括該資源的當(dāng)前擁擠和歷史擁擠成本，計算方法為

Gx,y=α·px,y·hx,y，

(5)

其中px,y和hx,y分別表示資源(x,y)的當(dāng)前擁擠成本和歷史擁擠成本，α為資源基本花費。由于px,y和hx,y均大于或等于1，而延時花費的數(shù)量級為10-9；通過將α的值設(shè)為1.3×10-9，從而使式(3)中Tb和Gx, y保持在基本相同的數(shù)量級上。px,y和hx,y的計算方法為

(6)

(7)

其中，ex,y表示資源(x,y)的容量，即該資源可以被多少邏輯單元同時使用；ux,y為占用資源(x,y)的邏輯單元數(shù)量；ε和σ分別為當(dāng)前和歷史懲罰因子，初始值均為1。根據(jù)式(6)和(7)，占用資源(x,y)的邏輯單元越多，px,y的值越大；隨著資源(x,y)發(fā)生擁擠的次數(shù)越多，hx,y的值越大，hx,y初始值為1。

2.3 初始布局

初始布局為電路中每個邏輯單元計算花費最小的物理資源，具體步驟如下：

(1)對電路進(jìn)行時序分析，并根據(jù)關(guān)鍵度對邏輯單元降序排序，變量i= 1；

(2)隨機(jī)選擇現(xiàn)場可編程門陣列上和第i個邏輯單元bi類型相同的物理資源，該資源的坐標(biāo)記為(xi,yi)；

(3)計算以(xi,yi)為中心、向外擴(kuò)展r個長度單位的邊界盒范圍，其中一個可配置邏輯單元的長度為一個長度單位；r的值為max{0.25×W, 0.25×H, 2}，其中W、H分別表示現(xiàn)場可編程門陣列的長和寬；系數(shù)0.25為實驗值，可以較好地平衡布局耗時和電路質(zhì)量；

(4)根據(jù)式(3)計算邊界盒內(nèi)所有和bi類型相同的物理資源的使用花費，將花費最小的物理資源分配給邏輯單元bi，并根據(jù)式(6)更新bi所占資源的當(dāng)前擁擠成本；

(5)如果所有的邏輯單元都完成布局，則根據(jù)式(7)更新所有物理資源的歷史擁擠花費，以及所有連接的延時，并對電路進(jìn)行時序分析，初始布局結(jié)束；否則，i++，轉(zhuǎn)步驟(2)繼續(xù)執(zhí)行。

2.4 資源協(xié)商布局

在資源協(xié)商布局階段，迭代地對占用擁擠資源的電路邏輯單元重新布局，隨著迭代次數(shù)增加，逐漸增大擁擠物理資源的使用成本，最終消除資源擁擠并得到合法的布局結(jié)果。資源協(xié)商布局的具體步驟如下：

(1)邏輯單元總數(shù)記為N，根據(jù)關(guān)鍵度對邏輯單元降序排序，變量i= 1，集合M置為空集。

(2)第i個邏輯單元bi所占用的物理資源的坐標(biāo)記為(xi,yi)，判斷資源(xi,yi)是否同時被其它邏輯單元占用著，即該資源是否發(fā)生擁擠。若資源(xi,yi)發(fā)生擁擠，則轉(zhuǎn)步驟(3)；否則，轉(zhuǎn)步驟(5)。

(3)將bi添加到集合M，并計算以(xi,yi)為中心、向外擴(kuò)展r個長度單位的邊界盒范圍，r的值為max{λ×W,λ×H, 2}，為了平衡布局耗時和電路質(zhì)量，通過實驗測試將λ值設(shè)為0.25。

(4)根據(jù)式(3)計算邊界盒內(nèi)所有和bi類型相同的物理資源的使用花費，并將花費最小的物理資源分配給邏輯單元bi，并更新資源(xi,yi)和bi當(dāng)前所占資源的當(dāng)前擁擠成本。

(5)如果i等于N，則完成對所有邏輯單元的遍歷，轉(zhuǎn)步驟(6)；否則，i++，轉(zhuǎn)步驟(2)執(zhí)行。

(6)更新所有和集合M中邏輯單元相連的連接的延時，并對布局后的電路進(jìn)行時序分析。

(7)如果布局結(jié)果中存在擁擠的物理資源，則更新資源的歷史擁擠花費，當(dāng)前擁擠懲罰因子乘以f，轉(zhuǎn)步驟(1)繼續(xù)執(zhí)行；否則，布局結(jié)果合法，資源協(xié)商布局結(jié)束。通過實驗發(fā)現(xiàn)，f的值越大，所需布局迭代次數(shù)越少，電路布局質(zhì)量質(zhì)量越差。當(dāng)f> 1.3時，電路平均布局迭代次數(shù)下降速度逐漸變慢；當(dāng)f> 1.55時，電路延時隨f的增大而逐漸惡化。為了平衡布局時間和電路布局質(zhì)量，將f的值設(shè)為1.3。

2.5 低溫模擬退火布局

資源協(xié)商布局后，調(diào)用低溫模擬退火算法對所得到的布局結(jié)果進(jìn)行局部優(yōu)化，具體步驟如下：

(1)邏輯單元總數(shù)記為N，變量i= 1；

(2)隨機(jī)選擇一個邏輯單元，記為bi；變量j= 1；

(3)隨機(jī)選擇和bi類型相同的物理單元，坐標(biāo)記為(xj,yj)；如果該物理單元已被別的邏輯單元占用，則交換該邏輯單元和bi的位置；否則，將bi移動到(xj,yj)位置；

(4)計算移動邏輯單元bi后的布局質(zhì)量，如果移動bi后的布局結(jié)果質(zhì)量更好，則接受移動bi后的布局結(jié)果；否則將bi移動到之前的位置；

(5)如果變量j

(6)如果i

3 實驗與比較

為了驗證新的布局方法在運行時間和布局質(zhì)量方面的性能，用多用途布局布線工具標(biāo)準(zhǔn)測試電路進(jìn)行測試，并和現(xiàn)有布局方法進(jìn)行比較。實驗環(huán)境為一臺惠普工作站，硬件包括一顆Xeon X5550處理器、12 G內(nèi)存和1 TB硬盤；系統(tǒng)為64位Ubuntu操作系統(tǒng)。分別使用工藝映射工具ABC和VPR對測試電路進(jìn)行工藝映射和打包；芯片模型使用多用途布局布線工具自帶的結(jié)構(gòu)描述文件k6_N10_mem32K_40nm.xml。

3.1 所提出的布局方法和多用途布局布線工具的比較

使用多用途布局布線工具標(biāo)準(zhǔn)電路分別對提出的布局方法和多用途布局布線工具進(jìn)行測試，每組數(shù)據(jù)測試10遍取平均值。從布局耗時、電路的延時和總線長三方面對提出的布局方法和多用途布局布線工具進(jìn)行比較。電路測試結(jié)果如表1所示。

表1 提出的布局方法與多用途布局布線工具的比較

根據(jù)表1中的數(shù)據(jù)，多用途布局布線工具布局耗時的平均值為27.5 s，所提出的布局方法平均只需要13.2 s；相比于多用途布局布線工具，提出的布局方法所需時間平均減少52%。對于規(guī)模最大的3個電路bgm、LU8PEEng和stereovision2，多用途布局布線工具布局時間均大于50 s，提出的布局方法的布局時間分別減少54.2%、53.8%和56.5%；對于多用途布局布線工具布局時間小于10 s的電路boundtop、mkPktMerge、mkSMAdapter4B、or1200和raygentop，所提出的布局算法將布局時間分別減少了43.5%、44.1%、44.4%、42.6%和43.2%，均小于平均值52%。可以看到，電路規(guī)模越大，和多用途布局布線工具相比所提出的布局方法布局效率越高。接下來比較布局的質(zhì)量：多用途布局布線工具布局后電路平均延時和總線長分別為17.764 8 ns和140 614；和多用途布局布線工具相比，提出的布局方法的延時和總線長分別優(yōu)化了4.8%和1.9%。表1的數(shù)據(jù)表明，提出的布局方法布局所需時間少于多用途布局布線工具，同時布局結(jié)果質(zhì)量優(yōu)于多用途布局布線工具。

3.2 與現(xiàn)有布局方法的比較

由于文獻(xiàn)[4-5]中的工具均未開放源代碼，無法對文獻(xiàn)[4-5]中的算法進(jìn)行測試。而文獻(xiàn)[4-5]均通過和多用途布局布線工具進(jìn)行比較來驗證算法的性能。因此，可以將新的布局方法與多用途布局布線工具的比較結(jié)果和文獻(xiàn)[4-5]與多用途布局布線工具的比較結(jié)果進(jìn)行比較，結(jié)果如表2所示。

表2 提出的布局方法和現(xiàn)有方法的比較

文獻(xiàn)[4]采用并行化布局算法，和多用途布局布線工具相比布局時間減少37.5%，延時減小4.2%。文獻(xiàn)[5]將遺傳算法應(yīng)用到現(xiàn)場可編程門陣列布局，電路延時減小8.4%，但布局時間增加了2 887倍。另外，文獻(xiàn)[4-5]都沒有比較電路的總線長。比較表2中數(shù)據(jù)可得：所提的布局方法的時間成本和布局質(zhì)量均優(yōu)于文獻(xiàn)[4]中的算法；雖然文獻(xiàn)[5]的延時優(yōu)于所提的布局方法，但耗時遠(yuǎn)大于所提的布局方法，而且沒有比較布局電路的總線長。

4 結(jié)束語

在初始布局階段，在允許資源重用的情況下為每個電路邏輯單元選擇最優(yōu)的布局，得到一個質(zhì)量較優(yōu)的布局結(jié)果；在資源協(xié)商布局階段，迭代地對占用擁擠資源的邏輯單元重新布局；隨著迭代次數(shù)增加，擁擠資源逐漸減少，避免了傳統(tǒng)模擬退火布局算法在每次布局迭代中陷入海量搜索空間的局限性。實驗結(jié)果表明，提出的布局方法的耗時和布局結(jié)果質(zhì)量優(yōu)于同類工具，有助于提高現(xiàn)場可編程門陣列電路開發(fā)效率。