基于圖論技術的FPGA資源管理算法*

張宏烈 張國印

(1.哈爾濱工程大學計算機科學與技術學院,黑龍江哈爾濱 150001; 2.齊齊哈爾大學計算機與控制工程學院,黑龍江齊齊哈爾 161006)

可重構計算是一種兼有硬件的計算速度和軟件的靈活性的計算模式,它能夠有效提高系統(tǒng)的計算能力,因此在許多領域特別是嵌入式系統(tǒng)領域有著廣闊的應用前景.隨著可重構技術被關注程度的提高,面向應用的體系結構研究也越來越受到重視,研究面向應用的體系結構的一個重要課題就是可重構系統(tǒng),即由一個主處理器和可重構邏輯器件(如FPGA)組成的系統(tǒng).在可重構系統(tǒng)尤其是運行時可重構系統(tǒng)的應用中,由于FPGA具有動態(tài)可重構能力,可重構硬件資源的實時變化帶來了新的問題.為了解決任務在FPGA上的布局/調度,可重構硬件資源的動態(tài)分配和管理成了近年來的研究熱點.

可重構資源管理的重點是對空閑區(qū)域的管理.從 20世紀 80年代開始,不少學者提出了一些有效的空閑區(qū)域管理方法,現(xiàn)行的方法可以歸納為三類:不重疊空閑矩形列表,最大空閑矩形列表和頂點列表[1-2].Bazargan等[3]首先提出了互不交迭的空閑矩形的可重構資源管理方法,Walder等[4]通過延遲空閑矩形的形成和采用二維Hash函數(shù)對其進行了改進,該方法在大多數(shù)情況下不能標識出可重構硬件中的最大空閑區(qū)域,因此為任務分配資源時的成功率會受到較大影響.

與不重疊空閑矩形列表相比,使用最大空閑矩形列表管理空閑區(qū)域,資源利用率較高,但是尋找可重構芯片中最大空閑矩形的完全集卻很耗時. Handa等[5]提出了階梯算法來尋找最大空閑矩形的完全集,但存在時間復雜度高的問題;Cui等[6]提出了基本掃描線算法,該算法仍存在冗余計算和重復計算的問題.在已有的方案中,李濤等[7]提出的基于任務上邊界計算最大空閑矩形的算法,由于鏈表的更新和任務的運行過程并發(fā),故系統(tǒng)的計算性能得到了提高.

對于相互連通的空閑區(qū)域,可以采用位于空閑區(qū)域邊界上的所有頂點構成的鏈表來管理所有的空閑資源.由于任務的動態(tài)添加和刪除,使得頂點鏈表的管理和查找比較復雜.

針對現(xiàn)有算法存在的一些問題,文中將無向圖與FPGA區(qū)域模型有機結合,提出基于虛擬無向圖計算最大空閑矩形的新方法(KAMER_VU).該算法采用在虛擬無向圖中尋找有效回路和通路的手段間接完成尋找最大空閑矩形的任務;在算法的實現(xiàn)過程中,不以任務已占用區(qū)域的上邊界或頂點為基準,較好地改善了冗余計算和重復計算的問題,縮短了算法的有效損耗時間.

1 FPGA區(qū)域模型

任務如何布局到FPGA的空閑區(qū)域,FPGA的空閑區(qū)域如何管理,取決于FPGA的資源模型.文中將FPGA看作是二維陣列,采用二維區(qū)域模型.FPGA區(qū)域模型描述為:FPGA可看作是由W列H行基本配置邏輯單元CLB(Configurable Logic Block)構成的矩形區(qū)域模型,W、H分別是可重構芯片單行、單列具備CLB的個數(shù),如圖1所示.在該模型中,每個單元的位置編號假設為(i,j),其中1≤i≤W,1≤j≤H;每個單元的使用狀態(tài)有兩種:空閑狀態(tài)和占用狀態(tài),若存在多個CLB單元連續(xù)空閑的情況,所形成的區(qū)域稱為空閑連通區(qū)域.圖 2中的空白區(qū)域即為空閑連通區(qū)域.

圖1 FPGA區(qū)域模型Fig.1 FPGA region model

圖2 空閑連通區(qū)域Fig.2 Free connected region

2 無向圖與FPGA空閑區(qū)域的映射關系

無向圖是一個有序二元組G=(V,E),對于FPGA資源的空閑區(qū)域,假設存在以下映射關系:

(1)一個CLB塊映射為無向圖的一個頂點;

(2)兩個CLB塊的相鄰關系映射為無向圖的一個邊.

若空閑區(qū)域內(nèi)部CLB塊不予考慮,可以將空閑區(qū)域邊界映射成一個無向圖,且該無向圖是由若干條水平和垂直通路構成的規(guī)則連通圖.以圖 2為例,其對應的無向圖如圖3所示,用Cij來表示位置編號為(i,j)的CLB塊對應的頂點.

圖3 空閑區(qū)域映射的無向圖Fig.3 Undigraph of free regionmapping

將FPGA空閑區(qū)域映射成無向圖后,在FPGA空閑區(qū)域尋找最大空閑矩形的問題轉化為在無向圖中尋找最大矩形的問題.

根據(jù)前面的分析可知,最大空閑矩形列表法是對空閑區(qū)域管理的最有效方法.采用適當?shù)乃惴ㄔ诳臻e區(qū)域中可以搜索到若干最大空閑矩形,為任務布局提供快速的分配方案.

定義1(最大空閑矩形) 不能被其它任何一個空閑矩形所完全覆蓋的空閑矩形為最大空閑矩形(MER).可用4維向量mer(x,y,w,h)描述,其中(x,y)代表MER左下角的CLB的位置編號,w、h分別代表MER的寬和長.

在圖 2中符合最大空閑矩形定義的集合中包含5個MER,分別是(2,2,5,1)、(6,1,6,1)、(6,5,1, 6)、(3,3,3,2)、(6,4,2,5).集合中的最大空閑矩形構成可以歸納為兩大類:一類是單排或單列結構,即最大空閑矩形是由若干個CLB塊一字排列構成,如(2,2,5,1)、(6,1,6,1)、(6,5,1,6),該類最大空閑矩形映射到無向圖中,對應一條水平或垂直通路;另一類是矩形結構,即最大空閑矩形是由若干排若干列 CLB塊構成,如(3,3,3,2)、(6,4,2,5),該類最大空閑矩形映射到無向圖中,對應一個回路.從以上映射關系中可以得出一個結論:尋找最大空閑矩形的問題在無向圖中轉化為尋找滿足條件的回路和通路的問題.

3 KAMER_VU算法

KAMER_VU算法根據(jù)虛擬無向圖計算和保持最大空閑矩形.設G=(V,E)是一個虛擬無向圖,為G中n個頂點的集合,頂點Vs的坐標為(i,j),即CLB塊的位置編號.若V1,V2,…,VK是V中K個連續(xù)頂點,則有定義如下.

定義2(水平通路) 對于所有1≤s≤k滿足Vs縱坐標取值相等,則G中V1,V2,…,Vk構成的通路稱為水平通路.在圖 3中,就是兩個水平通路.

定義3(垂直通路) 對于所有1≤s≤k滿足Vs橫坐標取值相等,則G中V1,V2,…,Vk構成的通路稱為垂直通路.在圖 3中,就是兩個垂直通路.

對于連通的虛擬無向圖而言,圖中只有一個最大回路,即能包容全部度數(shù)為 2的頂點和邊的回路,如圖 3所示,最大回路是.

定義4(最長水平通路) 水平通路中經(jīng)過的所有頂點不完全是最大回路中的頂點.如圖3中,V=是最長水平通路.而 C61、C62、C63、C66不是最大回路中的頂點.

定義5(最長垂直通路) 垂直通路中經(jīng)過的所有頂點不完全是最大回路中的頂點.如圖3中,V=是最長垂直通路,但 C15不是最大回路中的頂點.

進一步分析可得:最長水平通路和最長垂直通路“逆映射”到FPGA中,恰恰就是具有單排或單列結構的最大空閑矩形;最大回路可以按照掃描方法得到若干個部分重疊的子回路,該子回路“逆映射”到FPGA中,恰恰就是具有若干排若干列CLB塊構成的最大空閑矩形.圖 3中構造兩個部分重疊的子回路對應兩個最大空閑矩形.

基于虛擬無向圖計算最大空閑矩形的算法流程如圖 4所示.在圖 4的算法中,搜索最大回路是算法的一個關鍵,最大回路的搜索過程分為3個步驟.

圖4 KAMER_VU算法流程圖Fig.4 Flowchartof KAMER_VU algorithm

3.1 無向圖的預處理

在由相關頂點和邊構成的無向圖中,每個頂點的度數(shù)都為 2的連通圖稱為回路.因此,圖 3中需要將度數(shù)為 1的懸掛頂點以及與它關聯(lián)的懸掛邊裁剪掉,連續(xù)進行裁剪后,得到圖5所示的無向圖.

圖5 預處理后的無向圖Fig.5 Preprocessed undigraph

3.2 建立無向圖鄰接矩陣

根據(jù)圖5建立鄰接矩陣M 1,由于鄰接矩陣是對稱方陣,存儲時只需存儲矩陣的上三角矩陣.

3.3 搜索最大回路

對于連通的無向圖,最大回路只有一個.引入方向矢量交角[8],可以在無向圖中很快找到最大回路,具體搜索過程如下:

(1)確定搜索出發(fā)點和起始邊.假設無向圖上全部頂點均有相應坐標,搜索出 x坐標最小的頂點,即最左邊的某一頂點作為搜索的出發(fā)點,在圖 5中是頂點C23.根據(jù)鄰接矩陣,求該點鄰接邊相對于x軸的方向矢量交角,找出方向矢量交角最小的邊＜C23,C33＞作為搜索起始邊,該邊必然為最大回路中的一條邊,將鄰接矩陣 M 1中對應元素 M141減 1, C33作為下一次搜索的起始頂點.

(2)搜索與當前搜索邊相鄰的所有邊.根據(jù)鄰接矩陣M 1和頂點坐標,求與頂點C33的所有鄰接邊相對于當前搜索邊 ＜C23,C33＞的方向矢量交角,找出方向矢量交角最小的邊 ＜C33,C34＞,該邊也一定是最大回路的一邊,將鄰接矩陣 M 1中對應元素M154減 1.搜索出的邊 ＜C33,C34＞作為下次搜索的起始邊,該邊的終點C34作為下次搜索的起點.

(3)重復步驟(2),直到搜索邊的終點回到出發(fā)點為止,鄰接矩陣演化為 M 2,所形成的回路即為最大回路,如圖6所示,即

圖6 最大回路Fig.6 Themost large loop

4 仿真

為了測試KAMER_VU算法的性能,文中在一個FPGA仿真環(huán)境中進行實驗,仿真環(huán)境最小時間單位為10ms,大小為96×64個CLB塊.任務生成器隨機產(chǎn)生20000個硬件任務,存儲在隊列里,硬件任務的寬度和長度范圍是 2到8個 CLB,布局器根據(jù)First Fit(FF)適應策略為到達的硬件任務選擇合適的最大空閑矩形.分別采用KAMER_VU算法與SL (Scan Line)算法仿真,結果如表1所示.

表1 KAMER_VU算法與SL算法的執(zhí)行時間Table1 Execution time of KAMER_VU and SL algorithms

由表1可見,KAMER_VU的平均執(zhí)行時間約為SL算法的 1/2.由此可以判斷,由于掃描線算法有冗余計算的問題,隨著可重構芯片規(guī)模的增長,KAMER_VU的優(yōu)勢將更明顯.

文獻[9]中給出了任務拒絕率TRR,執(zhí)行時間PT和有效耗損時間VCT等概念,且VCT是TRR和PT之積.由定義可知,當任務拒絕率高而且執(zhí)行時間長的時候,有效耗損時間就長.分別觸發(fā)不同數(shù)目的硬件任務,測試KAMER_VU算法和SL算法的VCT,結果如圖7所示.由圖7可知,KAMER_VU算法的VCT是SL算法的60%左右,性能更優(yōu).

圖7 KAMER_VU算法和SL算法的VCT值Fig.7 VCT values of KAMER_VU and SL algorithms

5 結語

文中利用FPGA資源模型特征,將無向圖與FPGA模型有機結合,分析了二者之間的映射關系,提出了基于虛擬無向圖計算最大空閑矩形的算法.該算法將尋找最大空閑矩形問題轉化為求解有效回路和通路的問題,使空閑區(qū)域劃分過程大大簡化.仿真結果表明,應用KAMER_VU算法解決問題是可行的,且該算法的性能優(yōu)于SL算法.

將圖論技術應用于可重構資源管理領域,目前在國內(nèi)報道不多,文中在這個方面進行了初步探索,且仿真結果比較理想,但在算法結構和計算復雜度等方面還存在不足,有待于進一步改進.

[1] Tabero J,Step tien J,Mecha H,et al.Task placementheuristic based on 3D-adjacency and look-ahead in reconfigurab le systems[C]∥Proceedings of the 11th Asia and South Pacific Design Automation Conference 2006.Yokohama:IEEE Circuits and Systems Society ACM SIGDA, 2006:169-174.

[2] 齊驥,李曦.基于硬件任務頂點的可重構系統(tǒng)資源管理算法[J].電子學報,2006,34(11):2094-2098.

Qi Ji,LiXi.Algorithms of resourcemanagement for reconfigurable systems based on hardware task vertexes[J]. Acta Electronica Sinica,2006,34(11):2094-2098.

[3] Bazargan K,Kastner R,Sarrafzadeh M.Fast temp late placement for reconfigurable computing systems[J].IEEE Design and Testof Computers,2000,17(1):68-83.

[4] Walder H,Steiger C,Platzner M.Fast online task p lacment on FPGAs:free space partitioning and 2D hashing [C]∥International Parallel and Distributed Processing Symposium.New York:IEEE Computer Society,2003: 209-224.

[5] Handa M,Vemuri R.An efficientalgorithm for finding em pty space for online FPGA placement[C]∥Field Programmab le Logic and App lication:14th International Conference.Berlin:Sp ringer,2004:444-453.

[6] Cui Jin,Deng Qingxu,He Xiuqiang,et al.An efficient algorithm for online management of 2D area of partially reconfigurable FPGAs[C]∥2007 Design,Automation and Test in Europe Conference and Exposition.Nice: EDAA EDAC IEEE Computer Society TTTC,2007:129-134.

[7] 李濤,楊愚魯.可重構資源管理及硬件任務布局的算法研究 [J].計算機研究與發(fā)展,2008,45(2):375-382.

Li Tao,Yang Yu-lu.Algorithms of recon figurab le resource management and hardware task p lacement[J].Journal of Computer Research and Development,2008,45(2):375-382.

[8] 付志紅,俞集輝,蘇向豐.引入方向因子的最小回路、最大回路搜索算法 [J].重慶大學學報:自然科學版, 2002,25(3):64-67.

Fu Zhi-hong,Yu Ji-hui,Su Xiang-feng.The algorithm of searching out the leastandmost loop bymaking use of direction factor[J].Journal of Chongqing University:Natural Science Edition,2002,25(3):64-67.

[9] 龔育昌,齊驥.一種支持動態(tài)可重構系統(tǒng)的布局碎片量化方法 [J].小型微型計算機系統(tǒng),2007,28(5): 944-947.

Gong Yu-chang,Qi Ji.An app roach to quantify p lacement fragments for dynam ic recon figurable systems[J].Journal of Chinese Computer Systems,2007,28(5):944-947.