一種可重構資源管理模型及其調度技術

米　捷，王佳欣

MI Jie,WANG Jiaxin

河南工程學院 計算機學院，鄭州 451191

College of Computers,Henan Institute of Engineering,Zhengzhou 451191,China

1　引言

可重構計算機把算法映射到一些專門的硬件電路，這些硬件電路的配置和執行一般基于靜態隨機存取存儲器（Static Random Access Memory，SRAM）的現場可編程門陣列（Field-Programmable Gate Array，FPGA），使得這些計算機通過硬件重新配置就變得更加靈活。對于許多計算密集型的應用如數字信號處理領域，可重構系統相比于一般的處理器，可獲得更高的性能和能量效率。

早期的FPGA在密度和重構能力方面有限，但隨著微處理器的發展，如今的器件/設備可提供數百萬門，且能實現部分重構和回讀，允許在器件/設備上配置和執行電路，而不會影響其他正在運行的電路。為了表達這種電路的動態特性，通常把這種電路表示為硬件任務。在許多基于可重構嵌入式系統的應用領域，如網絡化移動系統[1]和可穿戴計算系統[2]，不同任務的激活時間和頻率僅在運行時才知道，任務執行是通過用戶生成的事件和環境的變化來觸發的。在這種高度動態情形下，需要定義一組好的系統服務來支持可靠的應用以及管理運行時的可重構資源，通常把這些系統服務稱為可重構操作系統。

可重構操作系統中的一個核心問題，就是部分可重構資源的建模和運行在可重構資源上的任務的在線調度。一個多任務可重構器件可以被看作是一個受額外全局資源約束的多處理器。對可重構面的劃分從某種程度上可減輕這種資源約束并簡化任務的調度，所以可重構操作系統成為近些年來的研究熱點。

硬件多任務描述首先由文獻[3]提出，文獻[4]對包括設備分區、分配、放置和尋由的操作系統服務進行了研究；文獻[5]對硬件任務的優先權進行了研究；文獻[6]提出了一種可重構操作系統，操作系統的主要部分是資源管理單元，并針對資源管理單元提出了對應的在線調度和放置算法，其特點是資源的再利用和再配置；文獻[7]根據可重構平臺的任務特征以及資源特征，將對硬件任務和可重構資源的管理納入到操作系統的范疇，通過在系統中添加硬件函數庫以及定制軟件函數庫輔助完成任務調度和資源管理，并實現了基于可變窗口的任務調度算法和資源管理算法；文獻[8]采用預取（預重構）技術通過并行重構配置和其他任務執行來減少重構時延，在考慮任務之間的數據依賴關系的情況下優化重構調度，并用最短關鍵路徑算法減小重構開銷；文獻[9]針對一維可重構器件中硬件任務的調度問題，提出了一種基于邊界表的可重構資源管理方法，該方法用“邊界表”數據結構記錄R-T坐標系中的區域邊界及其位置關系，實現對可重構資源的管理，并提出了R-T坐標系下的任務調度及布局算法；文獻[10]提出了一種適用于二維可重構器件的雙仲裁時間片可重構硬件任務調度算法DATS（Double Arbiters Time-Sliced），算法采用兩個仲裁器對硬件資源進行管理，并根據空間和時間約束動態裁決任務布局位置，同時設計了雙仲裁時間片任務調度模式圖，對任務的調度和布局過程進行合理分離，使任務調度和布局過程相對獨立并簡化處理過程；文獻[11]提出了支持功能演進的可重構數據平面結構以及用戶功能定制的映射算法，通過插入用戶配置單元的方式對數據包解析、匹配和處理過程進行編程，從而支持用戶自定義的功能部署。

本文針對可重構器件的操作系統層面進行了研究，提出了一種有效的管理模型和在線調度算法。仿真結果表明，基于本文提出的資源管理模型和調度算法，不僅能優化平均響應時間和實現任務的有效調度，而且相比于其他調度算法，還能獲得更高的資源利用率。

2　可重構資源管理模型

可重構資源的管理通常用可配置邏輯塊的一個矩形陣列來建模，在其上執行的任務也是用這種更小的邏輯塊矩形陣列來建模；可重構資源區域模型與重構面上的任務放置和調度問題的復雜性密切相關。因此本文先通過對兩種典型的區域模型的優缺點進行分析，然后提出一種新的可重構資源管理模型。

2.1　二維區域模型

圖1（a）所示為最靈活的區域模型，它允許把矩形任務放置在二維可重構面上的任何地方。這種模型得到了廣泛采用，其優點是當多個任務可以打包處理時，有很高的資源利用率；但另一方面，該模型的高度靈活性，又使得任務放置和調度相當困難。在線放置算法的提出，找到一個很好的、甚至是可行的任務放置方法。文獻[12]對此進行了研究，并提出了一種高效的數據結構和啟發式算法。當任務被放置在任意位置時，其余的自由區域就是分散碎片化的。這種外部碎片可能會阻止一個新的任務的放置，盡管有足夠的可用資源。為了防止或減少這種外部碎片化，文獻[13]研究了去碎片整理技術，即局部重裝和有序壓縮；同時，圖1（a）所示的區域模型很難采用目前流行的FPGA技術-賽靈思（Xilinx Virtex）來實現。首先，任務需要外部導線連接到其他任務和I/O焊盤，相關研究或認為這種通信是通過配置和回讀（這是可行的但可能是低效的）建立在長方形任務區域內部，或提出在任務之間留出一些空間作為通信信道；其次，任務連接和I/O必須動態重新尋由，而且時間安排必須重新進行分析，這是目前的商業設計工具所不支持的。

圖1　可重構資源模型

圖1（b）所示為一個二維劃分模型，在這個模型中，可重構面被劃分成一個靜態的、數量固定的配置位置，即所謂的塊。每個塊可以一次容納一個任務。這種劃分技術由文獻[14-15]首次提出。這種區域劃分簡化了放置和調度，使得目前的技術實現更具現實性。由于塊有固定的位置，其余的區域就可以作為操作系統的資源。通信信道和I/O由操作系統專門提供。對于在線尋由和時序分析來說，在任務和操作系統之間就不需要采用固定接口。其不足之處就是內部碎片化，也就是說，當一個任務小于一個塊時，該區域就被浪費掉了。

2.2　一維區域模型

圖1（c）所示為一個一維區域模型，在這個模型中，任務可以沿水平方向尺寸的任何位置放置，垂直尺寸是固定的。這種模型首先由文獻[16]提出，可簡化放置和調度，適合在Xilinx Virtex上實現。然而，這種模型會導致內部和外部碎片化，需要去碎片整理技術；圖1（d）所示為一維塊劃分區域模型，這種模型將圖1（b）模型中簡化的調度和放置與圖1（c）模型中的可實現優勢結合了起來，其缺點在于內部的高度碎片化。

2.3　本文提出的可重構資源管理模型

本文提出的可重構資源管理模型如圖2所示。可重構器件由一個主CPU控制，主CPU運行在線調度器和放置器（放置器可工作在約束模式和選擇模式），并通過一個配置/回讀端口實現配置和回讀。配置和回讀時間取決于任務的寬度。該模型的實現主要包括三方面：首先，主CPU可以從外部連接到可重構器件；其次，主CPU和可重構區域可以被集成在一個芯片上的可配置系統（Configurable system on Chip，CsoC）里；第三，主CPU可以在可重構器件的操作系統區域實現為一個合成的軟芯。

圖2　本文提出的可重構資源管理模型

可重構器件由有相同垂直尺寸的固定大小的塊構成。考慮不同寬度的塊，即有寬度為l的m個塊，l≤m，不同寬度為w1,w1,…,wl，假設通信通過在操作系統區域預先分配的信道進行，調度和放置不受通信需求的限制。因此，不失一般性，可以這樣來安排塊：其寬度從左到右單調減小，即wj≥wi,j＞i。圖1（d）的區域模型就是本文提出的資源模型的一個特例。

采用不同大小的塊的目的是為了在資源和任務之間實現更好的匹配。讓塊寬度適應任務寬度可以減少內部的碎片化，并可得到更高的平均資源利用率。盡管在一個任務集的調度過程中塊寬度是固定的，但仍然能夠在一個較長的時間尺度上改變寬度。例如，如果一個即將到達的任務集的最大任務寬度已知，則可以對器件重新劃分，把其最大塊寬度限制為最大任務的寬度，從而增加可用塊的數量。

可見，劃分技術決定著塊的數量和寬度，也起著至關重要的作用。一個合理的劃分方法會得到好的調度結果，比如減少一個任務集的總執行時間。假設一組任務必須執行，調度目標是使總的執行時間最小化，全部任務在同一時間到達，其寬度在[wmin,wmax]上服從均勻分布，其執行時間也為均勻分布，放置器工作在約束模式，可重構器件被劃分成寬度為w1,w2,…,wl的塊，每一寬度的塊數目分別為m1,m2,…,ml。約束模式將任務進行分類，一個類由一個寬度間隔如(wi-1,wi]來確定，進入這個寬度間隔的任務獲得mi個塊來執行。定義δi=wi-wi-1、Δ=wmax-wmin。被調度給(wi-1,wi]的任務的百分比為δi/Δ，這就是類(wi-1,wi]總的執行時間請求的度量。如果有mi個塊被分配給類(wi-1,wi]，則可得到類(wi-1,wi]的總的執行時間的度量為δi/(Δ·mi)。任務集的總的執行時間是全部類的執行時間的最大值。因此，劃分技術應選擇參數wi和mi以滿足：

例如，考慮一個可重構器件的Wˉ=80，wmin=4，wmax=20 ，則劃分{3×20，2×10}得到的執行時間度量劃分{2×20，2×15，1×10}得到的執行時間度量，可見，第一個劃分對于所描述的情形來說有更好的性能。

3　在線調度算法

在線調度問題主要是把任務放置在可重構面上。鑒于任務在器件上的具體配置，不是每個就緒的任務都是可放置的，這樣可能會嚴重影響調度，因此任務的在線調度也是一個很重要的問題，對此，本文提出如下的調度算法。

假設任務集由n個不相關的任務構成，每個任務tj由一個事先未知的到達時間aj來描述，其請求的區域用它的寬度wj、請求執行時間cj和截止時間dj（可選）來表示，配置和回讀時間與任務寬度成正比。

調度器采用圖3所示的結構，它由多個隊列和兩個函數fSPLIT和fSELECT構成。隊列的數量和位置取決于器件的塊劃分。如果靠近右邊的下一個塊bi有更小的寬度，即wj＞wi，則生成隊列qj并把它分配給塊bj。最右邊的塊b1總是獲取所分配的隊列q1。

函數fSPLIT的工作分為兩個步驟：首先，它將一個塊寬度wx分配給最右邊隊列到達的任務tx（wx足以容納tx）；其次，fSPLIT按照某個排序規則將任務插入到隊列。

圖3　在線調度算法的構成

函數fSELECT實際上是選擇和放置下一個即將要執行的任務。當每次一個執行任務終結，一個配置或回讀過程結束，或一個新的任務到達某個隊列頭部時fSELECT就被調用。在全部隊列頭部中，fSELECT選擇可以被分配和配置到能夠容納其大小的最小空閑塊的任務。

fSELECT中的放置器可以工作在兩種模式：在約束模式下，隊列qi中的任務只能被放置到對應于qi的塊中；在選擇模式下，放置器可以把一個任務分配給能容納它的任何塊。因此，隊列qj中等待的任務可被分配給塊bj,…,bm，而不是塊b1,b2,…,bi。圖3的示例就表示選擇模式，來自q3的任務可以放置在b4和b3中，而q1中的任務可以放置在任何塊中。

為了實現上述在線調度算法的思想，可采用非搶占式和搶占式調度方法。

3.1　非搶占式調度方法

非搶占式調度既不搶占在可重構器件上運行的任務，也不搶占配置過程本身。一旦fSELECT選擇一個任務，任務就被加載并運行至終止。本文采用以下兩種方案來實現非搶占式目標：

（1）先到先服務（First-Come First-Serve，FCFS）

對于FCFS來說，fSPLIT分配一個時間戳給每個到達的任務并將這個任務插入到合適的隊列。排序規則是先進先出（First-In First-Out，FIFO）；fSELECT的選擇規則是挑選具有最早到達時間戳的任務。

（2）最短作業優先（Shortest Job First，SJF）

對于SJF來說，fSPLIT根據任務的執行時間來對隊列進行排序。在每個隊列中，頭部記錄識別具有最小執行時間的任務；fSELECT的選擇規則是挑選具有最小執行時間的任務。

3.2　搶占式調度方法

搶占式調度搶占在可重構器件上運行的任務來分配給具有更高優先級的任務，而且配置和回讀過程也可以被搶占（負載中斷和卸載中斷），如圖4所示為任務狀態圖。配置過程總是被更高優先級的任務所中斷。只有當更高優先級的任務即將被加載到一個不同于bl的塊時，卸載塊bl的回讀過程才被中斷；否則，回讀繼續，bl必須卸載完。本文采用以下兩種方案來實現搶占式目標：

圖4　搶占式調度的任務狀態

（1）最短剩余處理時間（Shortest Remaining Processing Time，SRPT）

對于SRPT來說，fSPLIT根據任務的剩余執行時間來對隊列進行排序。fSELECT的選擇規則是挑選具有最小剩余執行時間的任務。

（2）最早截止時間優先（Earliest Deadline First，EDF）

對于EDF來說，fSPLIT根據任務的截止時間來對隊列進行排序。在每個隊列中，頭記錄識別具有最早截止時間的任務。fSELECT的選擇規則是挑選具有最早截止時間的任務。

當全部塊都是等寬度時，只有一個隊列被分配給最右邊的塊。在這種情況下，FCFS、SJF、SRPT和EDF完全表現出和單處理器一樣的功能；因此，不同大小的塊實際上構成了一個附加的資源約束，這個約束可能會削弱調度算法的性能。例如，FCFS可在一個更早到達的更大任務之前調度一個稍后到達的更小的任務，這就是對不同的任務要采用不同調度算法的原因。

4　仿真實驗

通過仿真實驗來評價本文提出的資源模型和在線調度算法的運行情況和性能。

仿真實驗在一個基于PC的XESS XSV-800板上進行，板上安裝有一個Virtex XCV-800 FPGA。任務采用VHDL來設計，用商業設計工具Xilinx Foundation來實現FPGA比特流，從這些完整的比特流中提取了部分比特流；然后在部分比特流內設置并存儲狀態位的位置；在FPGA上創建一個操作系統并把剩余區域劃分成許多塊，每個塊有一個復位信號。主機PC可以執行下列操作系統功能。

（1）任務負荷：任務是通過修改部分比特流的幀地址重新放置的，然后把部分比特流寫入到FPGA，當塊復位信號被激活，就加載初始狀態并開始任務執行。

（2）任務搶占：正在運行任務的狀態被搶占是通過激活FPGA上的搶占信號來實現的，然后，具有該狀態的任務被回讀，最后，運行環境被提取并通過訪問回讀比特流中的狀態位保存下來。

（3）任務恢復：這與任務加載基本相同，唯一的區別在于把先前提取的狀態插入到加載前的部分比特流。

為了實現調試，讓塊訪問連接到外部發光二極管的I/O引腳；仿真參數包括可重構器件的規模大小、一個器件列的配置和回讀時間以及塊劃分，在仿真中忽略CPU所需的運行時間。仿真框架包括仿真器模塊、一個任務發生器、一個數據采集和統計分析（含甘特圖查看器）模塊，以及配置情況和隊列負荷的圖形化顯示。

4.1　劃分和放置方法的評價

本節仿真用于分析劃分和放置方法對非搶占式調度算法FCFS性能的影響進行評價。假設任務獨立，因此調度算法的性能就可以通過一個任務集的平均響應時間來度量。任務ti的響應時間為：

式中，fi為任務的完成時間，ai為任務的到達時間。假設一個列的配置或回讀需159 μs，可用列為96列，其中只有80列為塊可用列，剩余的16列被操作系統占用。采取隨機生成有100個任務的任務集，任務寬度均勻分布在[4，20]列之間，執行時間在[2，200]ms之間，到達時間在[0.5，500]ms之間，仿真器分辨率即一個時鐘周期的時間設置為500 μs。

如圖5所示為兩種放置器模式（即約束模式和選擇模式）和五種不同劃分時得到的仿真結果。對于兩種放置器模式來說，劃分[1×20，2×15，3×10]表現出最好的性能。在約束模式，劃分[2×20，2×15，1×10]對于較小的任務明顯表現出瓶頸，而選擇模式有更好的結果，因為較小的任務也能夠被分配給較大的塊。劃分[1×20，10×6]是一種不正常的情形，因為寬度為6的10個塊都是很低效的。在這種情況下，總負荷的88%將被調度到一個大的塊，因此，平均響應時間急劇增加。

圖5　FCFS的平均響應時間

4.2　搶占式調度EDF的仿真分析

如圖6所示為調度器運行搶占式調度算法EDF、放置器工作在選擇模式時的甘特圖查看器截圖。可重構面被劃分成兩個塊b1和b2，其寬度分別為w1=5、w2=10，調度的任務集Tx(ax,wx,cx,dx)由四個任務構成：T1（1，5，8，26），T2（2，5，8，24），T3（8，5，4，23），T4（9，8，4，20）。

圖6　搶占式EDF調度算法的甘特圖

任務T1、T2和T3的配置和回讀時間是兩個時間單位，任務T4的配置和回讀時間是三個時間單位。從圖6可見，在時刻1，T1到達并開始配置到b1；在時刻2，T2到達，并獲得一個比T1更高的優先級，放置器工作在選擇模式把T2放置到b2，即T1的配置被搶占（配置中斷），T2被配置到b2。

在時刻4，配置/回讀端口被T2釋放，T1開始重新配置到b1；在時刻8，比T1和T2有更高優先級的T3到達。由于兩個塊已經被使用，故調度器選擇T1被搶占，因為T1的截止時間較長，b1上的T1的回讀開始；在時刻9，全部任務中具有最高優先級的T4到達，T4只能被放置在b2上，因此T2必須被搶占。在當前處理過程中的T1的回讀被停止（卸載中止），而由T2的回讀開始取代，T1恢復在b1上的執行；在時刻11，T2的回讀已經完成，T4被加載到b1。

可見，調度算法能很好地對到達任務實現有效的調度。

4.3　不同調度算法的資源利用率比較分析

本節對本文提出的非搶占式調度算法FCFS和搶占式調度算法EDF與文獻[6]和[7]的調度算法在資源利用率方面進行比較，如圖7所示為可重構資源利用率比較曲線。從圖7可見，基于本文提出的可重構資源模型和劃分技術，采用搶占式調度算法的資源利用率最高，可達90%以上，非搶占式調度算法次之，文獻[6-7]的調度算法的資源利用率明顯要低于本文的兩種調度算法；而且隨著任務負荷的增加，本文的兩種算法表現出更好的性能，主要是本文提出的資源模型考慮了不同塊的大小，讓塊的寬度自適應任務的寬度，從而可減少內部的碎片化，同時在已知到達任務集的最大任務寬度時，劃分技術可以對器件重新劃分，把其最大塊寬度限制為最大任務的寬度，從而增加可用塊的數量，減少總的任務執行時間。

圖7　不同調度算法的資源利用率比較

5　結束語

本文研究了可重構器件的區域模型，提出了一種基于塊劃分的資源管理模型，并設計了一種在線調度算法，采用非搶占式和搶占式策略來調度任務；同時，給出了仿真實驗來評價具體的劃分、放置和調度算法的性能。

參考文獻：

[1]Rudy L.Creating a world of smart re-configurable devices[C]//Proceedings of the 12th International Conference on Field-Programmable Logic and Applications：Reconfigurable Computing Is Going Mainstream，Montpellier，France，2002：790-794.

[2]Plessl C，Enzler R，Walder H，et al.Reconfigurable hardware in wearable computing nodes[C]//Proceedings of the 6th International Symposium on Wearable Computers，Seattle，USA，2002：215-222.

[3]Brebner G.A virtual hardware operating system for the Xilinx XC6200[C]//Proceedings of the 6th International Workshop on Field-Programmable Logic and Applications，New Paradigms and Compilers，Darmstadt，Germany，1996：327-336.

[4]Wigley G，Kearney D.The development of an operating system for reconfigurable computing[C]//Proceedings of the 9th IEEE Annual Symposium on FPGAs for Custom Computing Machines，California，USA，2001：249-250.

[5]Simmler H，Levinson L，Manner R.Multitasking on FPGA coprocessors[C]//Proceedings of the 10th International Workshop on Field-Programmable Logic and Applications：The Roadmap to Reconfigurable Computing，Villach，Austria，2000：121-130.

[6]Bassiri M M，Shahhoseini H S.Mitigating reconfiguration overhead in on-line task scheduling for reconfigurable computing systems[C]//Proceedings of the 2nd IEEE International Conference on Computer Engineering and Technology，2010：397-402.

[7]張軍能.動態可重構平臺操作系統中的資源管理問題研究[D].合肥：中國科學技術大學，2014.

[8]張吉昕.基于FPGA部分動態可重構技術的劃分和調度算法研究[D].武漢：武漢理工大學，2014.

[9]余國良，伍衛國，楊志華，等.一種采用邊界表進行可重構資源管理及硬件任務調度的算法[J].計算機研究與發展，2011，48（4）：699-708.

[10]楊志華，伍衛國，王濤，等.一種基于雙仲裁時間片策略的可重構硬件任務調度算法[J].計算機學報，2013，36（9）：1850-1867.

[11]段通，蘭巨龍，胡宇翔，等.一種支持網絡功能演進的可重構數據平面[J].電子學報，2016，44（7）：1721-1727.

[12]Bazargan K，Kastner R，Sarrafzadeh.Fast template placement for reconfigurable computing systems[J].IEEE Design and Test of Computers，2000，17（1）：68-83.

[13]Diessel O，ElGindy H，Middendorf M，et al.Dynamic scheduling of tasks on partially reconfigurable FPGAs[J].IEEEProceedingsonComputersandDigitalTechniques，2000，147（3）：181-188.

[14]Merino P，Jacome M，Lopez J C.A methodology for task based partitioning and scheduling of dynamically reconfigurable systems[C]//Proceedings of the IEEE Symopsium on FPGAs for Custom Computing Machines，Tallinn，Estonia，1998：324-325.

[15]Marescaux T，Andrei B，Dideriek V，et al.Interconnection networks enable fine-grain dynamic multi-tasking on FPGAs[C]//Proceedings of the 12th International Conference on Field-Programmable Logic and Applications：Reconfigurable Computing is Going Mainstream，Montpellier，France，2002：795-805.

[16]Brebner G，Diessel O.Chip-based reconfigurable task management[C]//Proceedings of the 11th International Workshop on Field-Programmable Logic and Applications，Belfast，Northern Ireland，UK，2001：182-191.