米　捷，王佳欣

MI Jie,WANG Jiaxin

河南工程學(xué)院 計(jì)算機(jī)學(xué)院，鄭州 451191

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

1　引言

可重構(gòu)計(jì)算機(jī)把算法映射到一些專門的硬件電路，這些硬件電路的配置和執(zhí)行一般基于靜態(tài)隨機(jī)存取存儲(chǔ)器（Static Random Access Memory，SRAM）的現(xiàn)場(chǎng)可編程門陣列（Field-Programmable Gate Array，F(xiàn)PGA），使得這些計(jì)算機(jī)通過硬件重新配置就變得更加靈活。對(duì)于許多計(jì)算密集型的應(yīng)用如數(shù)字信號(hào)處理領(lǐng)域，可重構(gòu)系統(tǒng)相比于一般的處理器，可獲得更高的性能和能量效率。

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

可重構(gòu)操作系統(tǒng)中的一個(gè)核心問題，就是部分可重構(gòu)資源的建模和運(yùn)行在可重構(gòu)資源上的任務(wù)的在線調(diào)度。一個(gè)多任務(wù)可重構(gòu)器件可以被看作是一個(gè)受額外全局資源約束的多處理器。對(duì)可重構(gòu)面的劃分從某種程度上可減輕這種資源約束并簡(jiǎn)化任務(wù)的調(diào)度，所以可重構(gòu)操作系統(tǒng)成為近些年來的研究熱點(diǎn)。

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

本文針對(duì)可重構(gòu)器件的操作系統(tǒng)層面進(jìn)行了研究，提出了一種有效的管理模型和在線調(diào)度算法。仿真結(jié)果表明，基于本文提出的資源管理模型和調(diào)度算法，不僅能優(yōu)化平均響應(yīng)時(shí)間和實(shí)現(xiàn)任務(wù)的有效調(diào)度，而且相比于其他調(diào)度算法，還能獲得更高的資源利用率。

2　可重構(gòu)資源管理模型

可重構(gòu)資源的管理通常用可配置邏輯塊的一個(gè)矩形陣列來建模，在其上執(zhí)行的任務(wù)也是用這種更小的邏輯塊矩形陣列來建模；可重構(gòu)資源區(qū)域模型與重構(gòu)面上的任務(wù)放置和調(diào)度問題的復(fù)雜性密切相關(guān)。因此本文先通過對(duì)兩種典型的區(qū)域模型的優(yōu)缺點(diǎn)進(jìn)行分析，然后提出一種新的可重構(gòu)資源管理模型。

2.1　二維區(qū)域模型

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

圖1　可重構(gòu)資源模型

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

2.2　一維區(qū)域模型

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

2.3　本文提出的可重構(gòu)資源管理模型

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

圖2　本文提出的可重構(gòu)資源管理模型

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

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

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

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

3　在線調(diào)度算法

在線調(diào)度問題主要是把任務(wù)放置在可重構(gòu)面上。鑒于任務(wù)在器件上的具體配置，不是每個(gè)就緒的任務(wù)都是可放置的，這樣可能會(huì)嚴(yán)重影響調(diào)度，因此任務(wù)的在線調(diào)度也是一個(gè)很重要的問題，對(duì)此，本文提出如下的調(diào)度算法。

假設(shè)任務(wù)集由n個(gè)不相關(guān)的任務(wù)構(gòu)成，每個(gè)任務(wù)tj由一個(gè)事先未知的到達(dá)時(shí)間aj來描述，其請(qǐng)求的區(qū)域用它的寬度wj、請(qǐng)求執(zhí)行時(shí)間cj和截止時(shí)間dj（可選）來表示，配置和回讀時(shí)間與任務(wù)寬度成正比。

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

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

圖3　在線調(diào)度算法的構(gòu)成

函數(shù)fSELECT實(shí)際上是選擇和放置下一個(gè)即將要執(zhí)行的任務(wù)。當(dāng)每次一個(gè)執(zhí)行任務(wù)終結(jié)，一個(gè)配置或回讀過程結(jié)束，或一個(gè)新的任務(wù)到達(dá)某個(gè)隊(duì)列頭部時(shí)fSELECT就被調(diào)用。在全部隊(duì)列頭部中，fSELECT選擇可以被分配和配置到能夠容納其大小的最小空閑塊的任務(wù)。

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

為了實(shí)現(xiàn)上述在線調(diào)度算法的思想，可采用非搶占式和搶占式調(diào)度方法。

3.1　非搶占式調(diào)度方法

非搶占式調(diào)度既不搶占在可重構(gòu)器件上運(yùn)行的任務(wù)，也不搶占配置過程本身。一旦fSELECT選擇一個(gè)任務(wù)，任務(wù)就被加載并運(yùn)行至終止。本文采用以下兩種方案來實(shí)現(xiàn)非搶占式目標(biāo)：

（1）先到先服務(wù)（First-Come First-Serve，F(xiàn)CFS）

對(duì)于FCFS來說，fSPLIT分配一個(gè)時(shí)間戳給每個(gè)到達(dá)的任務(wù)并將這個(gè)任務(wù)插入到合適的隊(duì)列。排序規(guī)則是先進(jìn)先出（First-In First-Out，F(xiàn)IFO）；fSELECT的選擇規(guī)則是挑選具有最早到達(dá)時(shí)間戳的任務(wù)。

（2）最短作業(yè)優(yōu)先（Shortest Job First，SJF）

對(duì)于SJF來說，fSPLIT根據(jù)任務(wù)的執(zhí)行時(shí)間來對(duì)隊(duì)列進(jìn)行排序。在每個(gè)隊(duì)列中，頭部記錄識(shí)別具有最小執(zhí)行時(shí)間的任務(wù)；fSELECT的選擇規(guī)則是挑選具有最小執(zhí)行時(shí)間的任務(wù)。

3.2　搶占式調(diào)度方法

搶占式調(diào)度搶占在可重構(gòu)器件上運(yùn)行的任務(wù)來分配給具有更高優(yōu)先級(jí)的任務(wù)，而且配置和回讀過程也可以被搶占（負(fù)載中斷和卸載中斷），如圖4所示為任務(wù)狀態(tài)圖。配置過程總是被更高優(yōu)先級(jí)的任務(wù)所中斷。只有當(dāng)更高優(yōu)先級(jí)的任務(wù)即將被加載到一個(gè)不同于bl的塊時(shí)，卸載塊bl的回讀過程才被中斷；否則，回讀繼續(xù)，bl必須卸載完。本文采用以下兩種方案來實(shí)現(xiàn)搶占式目標(biāo)：

圖4　搶占式調(diào)度的任務(wù)狀態(tài)

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

對(duì)于SRPT來說，fSPLIT根據(jù)任務(wù)的剩余執(zhí)行時(shí)間來對(duì)隊(duì)列進(jìn)行排序。fSELECT的選擇規(guī)則是挑選具有最小剩余執(zhí)行時(shí)間的任務(wù)。

（2）最早截止時(shí)間優(yōu)先（Earliest Deadline First，EDF）

對(duì)于EDF來說，fSPLIT根據(jù)任務(wù)的截止時(shí)間來對(duì)隊(duì)列進(jìn)行排序。在每個(gè)隊(duì)列中，頭記錄識(shí)別具有最早截止時(shí)間的任務(wù)。fSELECT的選擇規(guī)則是挑選具有最早截止時(shí)間的任務(wù)。

當(dāng)全部塊都是等寬度時(shí)，只有一個(gè)隊(duì)列被分配給最右邊的塊。在這種情況下，F(xiàn)CFS、SJF、SRPT和EDF完全表現(xiàn)出和單處理器一樣的功能；因此，不同大小的塊實(shí)際上構(gòu)成了一個(gè)附加的資源約束，這個(gè)約束可能會(huì)削弱調(diào)度算法的性能。例如，F(xiàn)CFS可在一個(gè)更早到達(dá)的更大任務(wù)之前調(diào)度一個(gè)稍后到達(dá)的更小的任務(wù)，這就是對(duì)不同的任務(wù)要采用不同調(diào)度算法的原因。

4　仿真實(shí)驗(yàn)

通過仿真實(shí)驗(yàn)來評(píng)價(jià)本文提出的資源模型和在線調(diào)度算法的運(yùn)行情況和性能。

仿真實(shí)驗(yàn)在一個(gè)基于PC的XESS XSV-800板上進(jìn)行，板上安裝有一個(gè)Virtex XCV-800 FPGA。任務(wù)采用VHDL來設(shè)計(jì)，用商業(yè)設(shè)計(jì)工具Xilinx Foundation來實(shí)現(xiàn)FPGA比特流，從這些完整的比特流中提取了部分比特流；然后在部分比特流內(nèi)設(shè)置并存儲(chǔ)狀態(tài)位的位置；在FPGA上創(chuàng)建一個(gè)操作系統(tǒng)并把剩余區(qū)域劃分成許多塊，每個(gè)塊有一個(gè)復(fù)位信號(hào)。主機(jī)PC可以執(zhí)行下列操作系統(tǒng)功能。

（1）任務(wù)負(fù)荷：任務(wù)是通過修改部分比特流的幀地址重新放置的，然后把部分比特流寫入到FPGA，當(dāng)塊復(fù)位信號(hào)被激活，就加載初始狀態(tài)并開始任務(wù)執(zhí)行。

（2）任務(wù)搶占：正在運(yùn)行任務(wù)的狀態(tài)被搶占是通過激活FPGA上的搶占信號(hào)來實(shí)現(xiàn)的，然后，具有該狀態(tài)的任務(wù)被回讀，最后，運(yùn)行環(huán)境被提取并通過訪問回讀比特流中的狀態(tài)位保存下來。

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

為了實(shí)現(xiàn)調(diào)試，讓塊訪問連接到外部發(fā)光二極管的I/O引腳；仿真參數(shù)包括可重構(gòu)器件的規(guī)模大小、一個(gè)器件列的配置和回讀時(shí)間以及塊劃分，在仿真中忽略CPU所需的運(yùn)行時(shí)間。仿真框架包括仿真器模塊、一個(gè)任務(wù)發(fā)生器、一個(gè)數(shù)據(jù)采集和統(tǒng)計(jì)分析（含甘特圖查看器）模塊，以及配置情況和隊(duì)列負(fù)荷的圖形化顯示。

4.1　劃分和放置方法的評(píng)價(jià)

本節(jié)仿真用于分析劃分和放置方法對(duì)非搶占式調(diào)度算法FCFS性能的影響進(jìn)行評(píng)價(jià)。假設(shè)任務(wù)獨(dú)立，因此調(diào)度算法的性能就可以通過一個(gè)任務(wù)集的平均響應(yīng)時(shí)間來度量。任務(wù)ti的響應(yīng)時(shí)間為：

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

如圖5所示為兩種放置器模式（即約束模式和選擇模式）和五種不同劃分時(shí)得到的仿真結(jié)果。對(duì)于兩種放置器模式來說，劃分[1×20，2×15，3×10]表現(xiàn)出最好的性能。在約束模式，劃分[2×20，2×15，1×10]對(duì)于較小的任務(wù)明顯表現(xiàn)出瓶頸，而選擇模式有更好的結(jié)果，因?yàn)檩^小的任務(wù)也能夠被分配給較大的塊。劃分[1×20，10×6]是一種不正常的情形，因?yàn)閷挾葹?的10個(gè)塊都是很低效的。在這種情況下，總負(fù)荷的88%將被調(diào)度到一個(gè)大的塊，因此，平均響應(yīng)時(shí)間急劇增加。

圖5　FCFS的平均響應(yīng)時(shí)間

4.2　搶占式調(diào)度EDF的仿真分析

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

圖6　搶占式EDF調(diào)度算法的甘特圖

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

在時(shí)刻4，配置/回讀端口被T2釋放，T1開始重新配置到b1；在時(shí)刻8，比T1和T2有更高優(yōu)先級(jí)的T3到達(dá)。由于兩個(gè)塊已經(jīng)被使用，故調(diào)度器選擇T1被搶占，因?yàn)門1的截止時(shí)間較長(zhǎng)，b1上的T1的回讀開始；在時(shí)刻9，全部任務(wù)中具有最高優(yōu)先級(jí)的T4到達(dá)，T4只能被放置在b2上，因此T2必須被搶占。在當(dāng)前處理過程中的T1的回讀被停止（卸載中止），而由T2的回讀開始取代，T1恢復(fù)在b1上的執(zhí)行；在時(shí)刻11，T2的回讀已經(jīng)完成，T4被加載到b1。

可見，調(diào)度算法能很好地對(duì)到達(dá)任務(wù)實(shí)現(xiàn)有效的調(diào)度。

4.3　不同調(diào)度算法的資源利用率比較分析

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

圖7　不同調(diào)度算法的資源利用率比較

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

本文研究了可重構(gòu)器件的區(qū)域模型，提出了一種基于塊劃分的資源管理模型，并設(shè)計(jì)了一種在線調(diào)度算法，采用非搶占式和搶占式策略來調(diào)度任務(wù)；同時(shí)，給出了仿真實(shí)驗(yàn)來評(píng)價(jià)具體的劃分、放置和調(diào)度算法的性能。

參考文獻(xiàn)：

[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，F(xiàn)rance，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òng)態(tài)可重構(gòu)平臺(tái)操作系統(tǒng)中的資源管理問題研究[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2014.

[8]張吉昕.基于FPGA部分動(dòng)態(tài)可重構(gòu)技術(shù)的劃分和調(diào)度算法研究[D].武漢：武漢理工大學(xué)，2014.

[9]余國(guó)良，伍衛(wèi)國(guó)，楊志華，等.一種采用邊界表進(jìn)行可重構(gòu)資源管理及硬件任務(wù)調(diào)度的算法[J].計(jì)算機(jī)研究與發(fā)展，2011，48（4）：699-708.

[10]楊志華，伍衛(wèi)國(guó)，王濤，等.一種基于雙仲裁時(shí)間片策略的可重構(gòu)硬件任務(wù)調(diào)度算法[J].計(jì)算機(jī)學(xué)報(bào)，2013，36（9）：1850-1867.

[11]段通，蘭巨龍，胡宇翔，等.一種支持網(wǎng)絡(luò)功能演進(jìn)的可重構(gòu)數(shù)據(jù)平面[J].電子學(xué)報(bào)，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，F(xiàn)rance，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.