王德奎

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

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

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

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

1 基礎(chǔ)知識(shí)

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

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

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

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

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

用硬件描述語(yǔ)言設(shè)計(jì)的電路經(jīng)過(guò)行為綜合、工藝映射、打包后轉(zhuǎn)化為電路網(wǎng)表〈V，E〉。電路網(wǎng)表由邏輯單元和單元之間的連接構(gòu)成，其中V表示邏輯單元集合，E表示邏輯單元之間連接的集合。圖2為打包后的電路網(wǎng)表，該電路網(wǎng)表中共有9個(gè)邏輯單元：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)場(chǎng)可編程門陣列布局就是根據(jù)相應(yīng)的約束條件，確定電路網(wǎng)表中的各邏輯單元在物理芯片上的位置，每個(gè)位置坐標(biāo)都對(duì)應(yīng)唯一的可編程物理邏輯單元。布局是多目標(biāo)優(yōu)化問(wèn)題，優(yōu)化目標(biāo)主要包括：(1)使電路中所有連接使用的連線資源總線長(zhǎng)盡量短；(2)使電路的延時(shí)盡量小。

2 提出的布局方法

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

2.1 電路時(shí)序分析

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

(1)

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

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

(2)

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

2.2 花費(fèi)計(jì)算函數(shù)

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

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

(3)

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

(4)

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

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

(5)

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

(6)

(7)

其中，ex,y表示資源(x,y)的容量，即該資源可以被多少邏輯單元同時(shí)使用；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 初始布局

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

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

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

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

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

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

2.4 資源協(xié)商布局

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

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

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

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

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

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

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

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

2.5 低溫模擬退火布局

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

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

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

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

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

(5)如果變量j

(6)如果i

3 實(shí)驗(yàn)與比較

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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