饒 廣，饒?jiān)撇?/p>

(1.內(nèi)江職業(yè)技術(shù)學(xué)院，四川 內(nèi)江 641000；2.電子科技大學(xué) 信息與軟件工程學(xué)院，成都 610054)

0 引言

現(xiàn)場可編程門陣列(FPGA，field-programmable gate array)通常是部分可重構(gòu)的，允許在運(yùn)行時對芯片的各個部分進(jìn)行配置，其中每部分可以執(zhí)行一個獨(dú)立的任務(wù)[1-2]。具有這種特性的設(shè)備可以同時容納多個應(yīng)用，其中每個應(yīng)用可以由多個任務(wù)構(gòu)成。要充分利用部分可重構(gòu)結(jié)構(gòu)的優(yōu)勢，就必須充分利用芯片資源[3-6]。不合理放置到達(dá)任務(wù)會導(dǎo)致芯片區(qū)域的一些部分浪費(fèi)，因?yàn)檫@些部分盡管是空閑的，但它們太小而無法容納另一個到達(dá)的任務(wù)。通常把這些空閑的較小部分稱為碎片，類似于傳統(tǒng)存儲系統(tǒng)中的碎片，這些碎片可能占芯片區(qū)域的很大比例[7]。因此，區(qū)域碎片是獲得良好的芯片資源利用的最大障礙之一。一方面，高區(qū)域碎片化表示芯片上占用部分的分散，因此可能導(dǎo)致低的芯片利用率；另一方面，低區(qū)域碎片化使得到達(dá)任務(wù)能夠被放置，從而提高芯片利用率。

在一個在線放置系統(tǒng)中，由于矩形任務(wù)的動態(tài)添加和刪除，使得FPGA的空區(qū)域變得高度碎片化，因而無法有效地利用FPGA區(qū)域。一個高度碎片化的芯片是指其中包含了大量的由一些被占用單元所分割形成的孔洞[8]，即任務(wù)矩形邊界以外的區(qū)域資源的碎片。如果一個任務(wù)的矩形區(qū)域沒有可用的足夠的相鄰資源，則該任務(wù)可能被拒絕放置。圖1所示為這樣的一個例子，其中任務(wù)T1和T2導(dǎo)致FPGA區(qū)域碎片化，因此，即使FPGA上的總的空閑區(qū)域大于任務(wù)T3的區(qū)域，但任務(wù)T3也不能放置在FPGA上。

圖1 FPGA區(qū)域的碎片化

圖2 碎片計(jì)算示例

上述這些方法都給出的是絕對的碎片度量，僅考慮了可重構(gòu)單元的分布。

另一種發(fā)展趨勢是相對碎片度量，它基于到達(dá)任務(wù)的大小考慮可重構(gòu)單元的狀態(tài)。作為相對碎片度量的一個例子，文獻(xiàn)[15]根據(jù)任務(wù)的平均大小來進(jìn)行計(jì)算。他們在一個空單元的垂直和水平附近使用空單元數(shù)量，如果這個數(shù)量大于或等于到達(dá)任務(wù)平均大小的2倍，則該單元的碎片貢獻(xiàn)為0。總的碎片由可重構(gòu)芯片區(qū)域內(nèi)所有空單元的垂直碎片和水平碎片之和來計(jì)算；文獻(xiàn)[16]基于多FPGA的動態(tài)可重配置的多任務(wù)調(diào)度和放置方法，通過任務(wù)級和子任務(wù)級的兩階段調(diào)度和放置方法，實(shí)現(xiàn)了在多FPGA系統(tǒng)的多任務(wù)調(diào)度和放置。在任務(wù)調(diào)度階段，考慮任務(wù)相似性和資源需求相似性，為每個任務(wù)選擇合適的計(jì)算單元，以減少重新配置和資源爭用的可能性，在子任務(wù)調(diào)度階段，綜合考慮子任務(wù)的調(diào)度順序和放置位置，以充分利用FPGA的硬件資源，利用FPGA可重配置能力使任務(wù)高度并行化，從而減小多任務(wù)的最小完工時間；文獻(xiàn)[17]提出了一種HRCA系統(tǒng)的可重構(gòu)單元的二維任務(wù)放置方法。方法結(jié)合3種影響HRCA系統(tǒng)的可重構(gòu)單元的碎片產(chǎn)生因素，包括當(dāng)前任務(wù)與其鄰接任務(wù)在時間上的重合度，當(dāng)前任務(wù)與其鄰接任務(wù)的邊長的重合度以及當(dāng)前任務(wù)對其它空閑塊的影響程度，依次計(jì)算當(dāng)前任務(wù)的長、寬分別沿每個空閑塊的每兩條相鄰邊放置時的合適度，選出所有空閑塊的所有位置中合適度最大的位置作為當(dāng)前任務(wù)的最終放置位置。提出的可重構(gòu)單元的二維任務(wù)放置方法，可以使任務(wù)放置更為緊湊合理，減少可重構(gòu)單元中的碎片，提高可重構(gòu)單元的空間利用率；文獻(xiàn)[18]針對最佳匹配(BF，best fit)算法存在的缺陷，在目標(biāo)處理器結(jié)點(diǎn)的局部調(diào)度下和避免最大入侵原則下，提出了一種避免入侵最佳匹配算法AIBFA。AIBFA算法分別降低了全局系統(tǒng)調(diào)度的平均時間負(fù)載率和目標(biāo)處理器結(jié)點(diǎn)局部調(diào)度的任務(wù)拒絕率。針對尋找空閑資源全集的問題提出了一種基于單向棧的算法來尋找最大空閑矩形，利用可重構(gòu)計(jì)算單元的不同M值進(jìn)出單向棧來搜索到所有最大空閑矩形。實(shí)驗(yàn)表明，算法通過使用單向棧與算法優(yōu)化，有效提高了查找空閑資源全集時的性能，減少了FPGA資源的碎片率；文獻(xiàn)[19]針對目前可重構(gòu)系統(tǒng)任務(wù)在線調(diào)度方法的不足，提出了一種基于放置代價的可重構(gòu)系統(tǒng)軟/硬件任務(wù)統(tǒng)一調(diào)度方法。方法考慮了3種代價，分別為硬件任務(wù)在FPGA上的執(zhí)行時間、占用的FPGA面積以及FPGA的碎片情況，還考慮了軟/硬件任務(wù)的統(tǒng)一調(diào)度方法。在調(diào)度過程中，當(dāng)硬件任務(wù)的代價超過設(shè)定的閾值時，就拒絕其在FPGA上運(yùn)行，并由CPU執(zhí)行其相應(yīng)軟件任務(wù)實(shí)現(xiàn).通過合理地拒絕一些代價較大的任務(wù)，從而從整體上提高任務(wù)調(diào)度成功率。實(shí)驗(yàn)表明，提出的方法能夠獲得更高的任務(wù)截止保證率。

相對碎片度量對特定時間到達(dá)任務(wù)的大小不敏感，所以對于相同的芯片碎片狀態(tài)，可能在不同時間得到2種不同的碎片度量，而到達(dá)任務(wù)的大小也可能是高度變化的。因此，絕對度量更準(zhǔn)確，它不需要給出芯片是滿的或空的任何指示，相反，僅給出整個芯片區(qū)域的孔(或空區(qū)域)的分散程度。

對此，本文提出了一種測量區(qū)域碎片的新方法和利用這種碎片度量的在線任務(wù)放置。提出的碎片度量方法考慮的是可重構(gòu)芯片上被占用(或空閑)空間的連續(xù)性，而不是被占用(或空閑)空間的數(shù)量。這樣，可用于監(jiān)測芯片區(qū)域和選擇最佳的空區(qū)域來放置新任務(wù)，從而減少總的芯片區(qū)域碎片。基于一個二維結(jié)構(gòu)的FPGA的仿真實(shí)驗(yàn)結(jié)果表明，相比于一般的左下角、第一匹配和最佳匹配放置策略，本文提出的碎片度量及放置方法不僅在等待時間、分配時間和響應(yīng)時間方面有所改善，而且提高了芯片的利用率，降低了失配率。

1 系統(tǒng)模型

這部分給出本文所采用的部分可重構(gòu)系統(tǒng)的任務(wù)和系統(tǒng)模型。

一個H×W的部分可重構(gòu)FPGA芯片由H行和W列構(gòu)成，左下角是芯片原點(diǎn)，在不影響芯片其余部分的情況下對芯片的一部分進(jìn)行配置。由于單元按順序配置，故FPGA是部分可重構(gòu)的，重構(gòu)時間與重新配置的單元數(shù)量成正比，配置延遲是配置一個單元及其相關(guān)路由資源所需要的時間。

系統(tǒng)假設(shè)任務(wù)在線到達(dá)，并按到達(dá)順序排隊(duì)和放置。只要在FPGA區(qū)域中有可用的空閑單元，服務(wù)器就會繼續(xù)為到達(dá)的任務(wù)提供服務(wù)，方法是將每個任務(wù)放置在FPGA芯片的一個未被占用的區(qū)域上。如果由于沒有可用的相鄰資源(空閑單元)，隊(duì)列頂部的任務(wù)被拒絕放置，則放置隊(duì)列將處于停頓狀態(tài)，直至存在足夠的相鄰空空間。

任務(wù)是非搶占的[20]。一旦任務(wù)被放置在可重構(gòu)芯片區(qū)域的任何空閑區(qū)域，就停留在這個地方直至完成執(zhí)行；任務(wù)參數(shù)事先是未知的，這些任務(wù)參數(shù)定義為：對于一個任務(wù)ti，ti=(hi，wi，ai，si，di，xi，yi)，hi和wi分別代表其高度和寬度，是用單元數(shù)量來度量的，ai、si和di分別為任務(wù)到達(dá)時間、任務(wù)服務(wù)時間和任務(wù)截止時間。分配給任務(wù)的矩形區(qū)域由其左下角(xi，yi)給出，其中xi表示行號，yi表示列號。這些特征能夠反映一個通用計(jì)算系統(tǒng)。任務(wù)的大小、到達(dá)時間、服務(wù)時間和截止時間在一個預(yù)定義的區(qū)域都是均勻分布的，且事先未知的。

從形式上說，任務(wù)ti在時刻ai到達(dá)，在時刻si開始執(zhí)行，在時刻fi完成執(zhí)行，因此，任務(wù)ti的等待時間為w(ti)=si-ai給出，響應(yīng)時間為r(ti)=fi-ai。任務(wù)的分配時間al(ti)是任務(wù)在等待隊(duì)列的頂部等待直到它在可重構(gòu)區(qū)域中找到一個位置的時間。

2 碎片度量

本節(jié)提出一種新的多維結(jié)構(gòu)的碎片度量方法。假設(shè)單元是區(qū)域資源的最小單位，已使用的單元是指已占用的單元，未使用的單元稱為空單元。我們從一維結(jié)構(gòu)的度量開始，然后將它擴(kuò)展到二維結(jié)構(gòu)和更高維的結(jié)構(gòu)。

2.1 一維碎片度量

首先給出一些定義。

考慮一個一維結(jié)構(gòu)S，由L個單元構(gòu)成，每個單元可以是占用的或空閑的兩種狀態(tài)之一，稱這種結(jié)構(gòu)為單元流。

定義1：長度為L的單元流S是一組L個連續(xù)單元。

備注：一個單元流表示一組連續(xù)的單元，而不考慮每個單元的狀態(tài)。

定義2：長度為K的單元序列Q是一組K個連續(xù)的空單元。

在圖3(a)中，存在長度分別為2、3的兩個單元序列，而在圖3(b)中，存在長度分別為1、4、5的3個單元序列。令c(S)為單元流S中單元序列的數(shù)量，QS(x)為單元流S中第x個單元序列，l(QS(x))為其長度(0≤x≤c(S))。

圖3 一維碎片度量說明

引理1：在長度為L的單元流S中，單元序列數(shù)量c≤S[L/2]。

證明：當(dāng)每個單元流的長度為1時，就會出現(xiàn)最大的單元流數(shù)量，即當(dāng)單元序列中有一個空單元，然后是一個已占用的單元時，等等，就會發(fā)生這種情況?？諉卧臄?shù)量表示單元序列的數(shù)量，對于一個長度為L的單元流來說，它為L/2。

我們的度量指標(biāo)測量在單元流內(nèi)被占用區(qū)域的連續(xù)性，而不是測量有多少個單元是空的。因此，并不與具體的問題相關(guān)聯(lián)，而是一個通用的度量指標(biāo)，可以在不同的情況下使用。測量單元流中被占用單元的連續(xù)性，可轉(zhuǎn)化為測量在單元流中有多少單元序列。具有小長度的許多單元序列的存在是高度碎片化的一個標(biāo)志，我們建立在這一觀察的基礎(chǔ)上。

令FS表示單元流S的碎片度量，隨著單元序列數(shù)量的增加，S的碎片也增加。每個單元序列的長度是計(jì)算S的碎片化的另一個重要因素，隨著每個單元序列長度的減小，單元序列對碎片度量的貢獻(xiàn)就更大。一個單元序列對FS貢獻(xiàn)的值為1/l(QS(x))，則一維碎片度量為：

(1)

在圖3(a)和(b)中，分別有F1-d=1/2+1/3=5/6，F(xiàn)1-d=1/1+1/4+1/5=29/20。

2.2 二維碎片度量

將上一節(jié)得到的一維碎片度量擴(kuò)展到二維結(jié)構(gòu)?？紤]一個二維結(jié)構(gòu)(陣列)A，由H×W個單元構(gòu)成，每個單元可以是被占用的或空閑的兩種狀態(tài)之一。

令FR(i)和FC(j)分別表示第i行和第j列對芯片的碎片度量F2-d的貢獻(xiàn)，單元序列QR(i)對FR(i)貢獻(xiàn)的值為1/l(QR(i)(x))，則：

(2)

在FPGA環(huán)境下，每行i對總的區(qū)域碎片度量貢獻(xiàn)的值為FR(i)。令FR表示芯片中全部行的貢獻(xiàn)值，則：

(3)

同樣，每列對總碎片度量的貢獻(xiàn)值為：

(4)

令FC表示芯片中全部列的貢獻(xiàn)值，則：

(5)

最后，二維碎片度量F2-d可以計(jì)算為F2-d=FR+FC，即：

(6)

2.3 高維碎片度量

現(xiàn)在將前面的結(jié)果推廣到n維結(jié)構(gòu)，如超立方體?？紤]一個n維單元陣列m1×m2×...×mn，令d1，d2，...，dn表示n維。這種結(jié)構(gòu)中的基本單元是基本邏輯塊(單元)。每個單元要么被占用，要么是空的。我們將考慮每個維度，并計(jì)算這個維度對碎片度量的貢獻(xiàn)，將2.2節(jié)中的做法擴(kuò)展到n維?？梢酝ㄟ^確定單元所在的每個維度中的值來定義陣列中的單元。例如，單元C(x1，x2，...，xn)是位于d1維的x1，d2維的x2等等的一個單元，其中0≤xi≤mi-1，1≤i≤n。令Fd1，F(xiàn)d2，...，F(xiàn)dn分別表示d1，d2，...，dn維對碎片度量的貢獻(xiàn)，令Qdr(x1，x2，...，xr-1，xr+1，...，xn)(k)表示維dr中第k個單元序列，1≤r≤n，且沿維d1，d2，...，dr-1，dr+1，...，dn的值分別為x1，x2，...，xr-1，xr+1，...，xn，令

{Qdr(x1，x2，...，xr-1，xr+1，...，xn)(k)：0≤k≤c(dr)}

(7)

為在維dr中單元序列的集合，同時令l(Qdr(x1，x2，...，xr-1，xr+1，...，xn)(k))為該單元序列的長度，把4.2節(jié)的結(jié)果進(jìn)行擴(kuò)展(這里1≤r≤n)，得到：

(8)

總的碎片度量是每維貢獻(xiàn)的總和：

(9)

當(dāng)n=3時，這個度量的一個直接應(yīng)用是測量超立方體中的活躍節(jié)點(diǎn)有多分散。

2.4 碎片度量計(jì)算及實(shí)例

本節(jié)提出一種運(yùn)行時間高效的算法來計(jì)算在給定時間的碎片度量。我們用一維陣列R(或C)的形式來保存行(或列)的碎片信息，碎片信息的更新是在每次添加和刪除任務(wù)到FPGA之后。最初，當(dāng)FPGA為空時，R和C中每個元素的值為零。

圖4所示為有一些正在運(yùn)行任務(wù)的一個芯片，代表芯片區(qū)域的陣列R和C在圖中是沿列和行顯示的，R(或C)的每個元素保存每行(或列)中相鄰空單元的數(shù)量。元素R(i)(或C(j))包含行i(或列j)的碎片信息。R(或C)中的每個元素可能包含多個值，因?yàn)橐恍?或一列)可能有多個空單元序列。圖4給出了一個6行6列的FPGA設(shè)備的示例。在圖4中，R(0)=4表示第一行中相鄰空單元的數(shù)量。C的第一個元素C(0)=[2，1]分別表示長度為2和1的兩個不同的空序列。

圖4 計(jì)算碎片度量

芯片的碎片度量F2-d=FR+FC，其中，F(xiàn)R=1/4+1/1+1/2+1/3+1/2+1/4+1/1+1/4，F(xiàn)C=1/2+1/1+1/2+1/1+1/4+1/1+1/1+1/3+1/3+1/3。

3 基于碎片度量的任務(wù)在線放置

3.1 任務(wù)的添加和刪除

在添加或刪除任務(wù)之后，可以非常高效地更新碎片陣列R和C。當(dāng)一個任務(wù)被添加或刪除時，它只影響R和C的相應(yīng)元素。如果將任務(wù)添加到芯片或從芯片中刪除，已占用的行ri到rj和列ci到cj，則元素R(ri)到R(rj)將相應(yīng)改變，以反映這些行的新的狀態(tài)。對于元素C(ci)到C(cj)也是同樣的分析。

3.2 任務(wù)的在線放置

根據(jù)其前面的討論，碎片度量測量的是被占用(空閑)區(qū)域的連續(xù)性，也就是說，具有較低碎片度量值的芯片狀態(tài)表示空閑空間的更多連續(xù)性，我們據(jù)此來選擇到達(dá)任務(wù)的位置。

一旦一個任務(wù)位于隊(duì)列的頂部，放置引擎就檢查該任務(wù)的全部可能位置。放置引擎選擇能夠得到新狀態(tài)較低碎片度量的位置，這將得到更多連續(xù)的空間，將有助于為下一組到達(dá)任務(wù)騰出空間。

碎片度量采用前述的陣列R和C快速計(jì)算，主要是找到最佳候選位置來放置任務(wù)，以減少新狀態(tài)的碎片度量。可以根據(jù)任務(wù)大小、任務(wù)間到達(dá)時間和任務(wù)執(zhí)行時間的不同分布，通過多次運(yùn)行來觀察這些參數(shù)對系統(tǒng)性能的影響。

4 實(shí)驗(yàn)結(jié)果

本節(jié)在二維結(jié)構(gòu)上，通過對一個綜合任務(wù)集的一系列實(shí)驗(yàn)來測試算法的性能。對于每個實(shí)驗(yàn)，生成1 000個任務(wù)的集合，任務(wù)由4個獨(dú)立選擇的均勻分布隨機(jī)變量來描述，其中2個變量表示隨機(jī)選擇(均勻分布)的到達(dá)任務(wù)的長度和寬度，允許從1～32個單元不等；一個變量表示任務(wù)的服務(wù)時間，在1～1 000個時間單位之間隨機(jī)生成(均勻分布)；任務(wù)的終止時間是通過在任務(wù)的服務(wù)時間中添加一個隨機(jī)變量(在1～50之間均勻分布)來形成的。對均勻分布在1～(10，20，30，40，50，60，70，80，90，100)時間單位之間不同的任務(wù)間到達(dá)時間間隔重復(fù)實(shí)驗(yàn)；對這些任務(wù)進(jìn)行排隊(duì)，并按到達(dá)順序放置到一個大小為64(64的仿真FPGA上。加載一個任務(wù)所需要的時間由芯片上空位置的可用性以及用于配置任務(wù)所需單元的時間確定，因此，每個單元的配置延遲也是一個參數(shù)，這里選擇固定值1/1 000時間單位。

首先，在不采用實(shí)時截止時間測試的情況下，對于相同的數(shù)據(jù)集，將本文提出的碎片度量和放置方法與傳統(tǒng)的放置策略左下角(BL，bottom-left)、第一匹配(FF，first first)和最佳匹配(BF，best fit)放置方法的性能進(jìn)行比較，其次，在實(shí)時環(huán)境下對失配率進(jìn)行測試。

圖5和圖6比較了傳統(tǒng)的放置策略BL、FF和BF與本文提出的碎片度量及任務(wù)放置方法的不同性能。采用的一組輸入數(shù)據(jù)任務(wù)側(cè)可達(dá)32個單元，服務(wù)時間最大為500個時間單位，得到的不同任務(wù)間到達(dá)時間對各種性能的影響。

圖5 性能測試1

圖6 性能測試2

圖5(a)所示為不同放置放法的等待時間的比較?？梢姡疚奶岢龅乃槠攘考叭蝿?wù)放置放法比BL平均降低了約10%，比FF平均降低了約25%，比BF平均降低了約13%；圖5(b)所示為不同放置放法的分配時間的比較?？梢?，本文提出的碎片度量及任務(wù)放置方法比BL平均減少了約5%，比FF平均減少了約9%，比BF平均減少了約6%；對于響應(yīng)時間，從圖6(a)可以看到，本文提出的碎片度量及任務(wù)放置方法比BL平均降低了約10%，比FF平均降低了約16%，比BF平均降低了約12%；對于芯片利用率，從圖6(b)可以看到，本文提出的碎片度量及任務(wù)放置方法比BL提高了約5%，比FF提高了約17%，比BF提高了約13%。

表1所示在實(shí)時環(huán)境下，本文提出的碎片度量及任務(wù)放置方法與BL、FF和BF相比在失配率方面的改進(jìn)。第一列的任務(wù)大小從1×1到32×32、第二列從8×8到32×32，等等。從表1可見，在第一列的任務(wù)大小中，任務(wù)間到達(dá)時間為90個時間單位時有最佳的改進(jìn)。隨著最小任務(wù)邊長的增加，失配率有更大的改進(jìn)，這是因?yàn)樾∪蝿?wù)可以放在芯片中的一些碎片中；當(dāng)最小任務(wù)側(cè)為24個單元時，本文提出的碎片度量及任務(wù)放置方法的失配率改進(jìn)效果較好。

表1 本文方法相比于BL、FF和BF的失配率改進(jìn) %

5 結(jié)束語

本文針對部分可重構(gòu)FPGA提出了一種多維碎片度量及任務(wù)的在線放置，并在二維結(jié)構(gòu)中采用這個度量來提高FPGA的區(qū)域利用率。實(shí)驗(yàn)結(jié)果表明，本文提出的碎片度量及任務(wù)在線放置方法與常用的放置策略如左下角、第一匹配和最佳匹配相比較，在芯片利用率方面提高了約5%～17%，在響應(yīng)時間方面降低了約10%～16%；在實(shí)時系統(tǒng)中的測試表明，失配率最大可改進(jìn)約9%。

將本文提出的放置方法應(yīng)用于異構(gòu)可重構(gòu)系統(tǒng)將是我們未來一段時間的研究方向。