FPGA中基于空間連續性的碎片度量及任務放置

饒 廣，饒云波

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

0 引言

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

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

圖1 FPGA區域的碎片化

圖2 碎片計算示例

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

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

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

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

1 系統模型

這部分給出本文所采用的部分可重構系統的任務和系統模型。

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

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

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

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

2 碎片度量

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

2.1 一維碎片度量

首先給出一些定義。

考慮一個一維結構S，由L個單元構成，每個單元可以是占用的或空閑的兩種狀態之一，稱這種結構為單元流。

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

備注：一個單元流表示一組連續的單元，而不考慮每個單元的狀態。

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

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

圖3 一維碎片度量說明

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

證明：當每個單元流的長度為1時，就會出現最大的單元流數量，即當單元序列中有一個空單元，然后是一個已占用的單元時，等等，就會發生這種情況?？諉卧臄盗勘硎締卧蛄械臄盗浚瑢τ谝粋€長度為L的單元流來說，它為L/2。

我們的度量指標測量在單元流內被占用區域的連續性，而不是測量有多少個單元是空的。因此，并不與具體的問題相關聯，而是一個通用的度量指標，可以在不同的情況下使用。測量單元流中被占用單元的連續性，可轉化為測量在單元流中有多少單元序列。具有小長度的許多單元序列的存在是高度碎片化的一個標志，我們建立在這一觀察的基礎上。

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

(1)

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

2.2 二維碎片度量

將上一節得到的一維碎片度量擴展到二維結構。考慮一個二維結構(陣列)A，由H×W個單元構成，每個單元可以是被占用的或空閑的兩種狀態之一。

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

(2)

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

(3)

同樣，每列對總碎片度量的貢獻值為：

(4)

令FC表示芯片中全部列的貢獻值，則：

(5)

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

(6)

2.3 高維碎片度量

現在將前面的結果推廣到n維結構，如超立方體。考慮一個n維單元陣列m1×m2×...×mn，令d1，d2，...，dn表示n維。這種結構中的基本單元是基本邏輯塊(單元)。每個單元要么被占用，要么是空的。我們將考慮每個維度，并計算這個維度對碎片度量的貢獻，將2.2節中的做法擴展到n維?？梢酝ㄟ^確定單元所在的每個維度中的值來定義陣列中的單元。例如，單元C(x1，x2，...，xn)是位于d1維的x1，d2維的x2等等的一個單元，其中0≤xi≤mi-1，1≤i≤n。令Fd1，Fd2，...，Fdn分別表示d1，d2，...，dn維對碎片度量的貢獻，令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節的結果進行擴展(這里1≤r≤n)，得到：

(8)

總的碎片度量是每維貢獻的總和：

(9)

當n=3時，這個度量的一個直接應用是測量超立方體中的活躍節點有多分散。

2.4 碎片度量計算及實例

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

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

圖4 計算碎片度量

芯片的碎片度量F2-d=FR+FC，其中，FR=1/4+1/1+1/2+1/3+1/2+1/4+1/1+1/4，FC=1/2+1/1+1/2+1/1+1/4+1/1+1/1+1/3+1/3+1/3。

3 基于碎片度量的任務在線放置

3.1 任務的添加和刪除

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

3.2 任務的在線放置

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

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

碎片度量采用前述的陣列R和C快速計算，主要是找到最佳候選位置來放置任務，以減少新狀態的碎片度量?？梢愿鶕蝿沾笮?、任務間到達時間和任務執行時間的不同分布，通過多次運行來觀察這些參數對系統性能的影響。

4 實驗結果

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

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

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

圖5 性能測試1

圖6 性能測試2

圖5(a)所示為不同放置放法的等待時間的比較?？梢?，本文提出的碎片度量及任務放置放法比BL平均降低了約10%，比FF平均降低了約25%，比BF平均降低了約13%；圖5(b)所示為不同放置放法的分配時間的比較。可見，本文提出的碎片度量及任務放置方法比BL平均減少了約5%，比FF平均減少了約9%，比BF平均減少了約6%；對于響應時間，從圖6(a)可以看到，本文提出的碎片度量及任務放置方法比BL平均降低了約10%，比FF平均降低了約16%，比BF平均降低了約12%；對于芯片利用率，從圖6(b)可以看到，本文提出的碎片度量及任務放置方法比BL提高了約5%，比FF提高了約17%，比BF提高了約13%。

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

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

5 結束語

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

將本文提出的放置方法應用于異構可重構系統將是我們未來一段時間的研究方向。