基于時(shí)空情境的可重構(gòu)高性能任務(wù)調(diào)度體系

涂春萍， 柴亞輝， 黃衛(wèi)春， 熊李艷

(華東交通大學(xué) 信息工程學(xué)院,江西 南昌 330013)

?

基于時(shí)空情境的可重構(gòu)高性能任務(wù)調(diào)度體系

涂春萍， 柴亞輝， 黃衛(wèi)春， 熊李艷

(華東交通大學(xué) 信息工程學(xué)院,江西 南昌 330013)

針對(duì)基于FPGA計(jì)算加速的異構(gòu)高性能計(jì)算平臺(tái)上的硬件任務(wù)調(diào)度需求，根據(jù)硬件任務(wù)的空間屬性與時(shí)間屬性，提出了一個(gè)基于時(shí)空情境CBTA的任務(wù)調(diào)度體系與相關(guān)算法。高性能計(jì)算平臺(tái)的分級(jí)調(diào)度將CBTA的調(diào)度分為平臺(tái)任務(wù)調(diào)度與節(jié)點(diǎn)任務(wù)調(diào)度。通過將任務(wù)與資源劃分為不同的時(shí)空情境，提出了一個(gè)基于情境轉(zhuǎn)化的自適應(yīng)任務(wù)調(diào)度策略，并給出了CBTA調(diào)度算法的并行優(yōu)化策略。最后通過實(shí)驗(yàn)來說明了算法在對(duì)用戶響應(yīng)時(shí)間、負(fù)載均衡以及任務(wù)拒絕率上的優(yōu)勢(shì)。

FPGA計(jì)算加速； 硬件任務(wù)調(diào)度； 時(shí)空情境； 自適應(yīng)調(diào)度

0 引 言

基于異構(gòu)架構(gòu)[1]的高性能計(jì)算，是當(dāng)今高性能計(jì)算的發(fā)展方向與熱點(diǎn)之一，而隨著FPGA的規(guī)模和性能的不斷提高，將FPGA計(jì)算器件作為高性能計(jì)算機(jī)上的運(yùn)算加速部件已經(jīng)成為當(dāng)前高性能計(jì)算研究方向的一個(gè)熱點(diǎn)。任務(wù)調(diào)度系統(tǒng)的目標(biāo)是要充分利用可重構(gòu)硬件資源，任務(wù)調(diào)度是可重構(gòu)操作系統(tǒng)[1]任務(wù)管理以及高性能計(jì)算平臺(tái)任務(wù)管理的核心功能。對(duì)FPGA上的硬件任務(wù)的調(diào)度除了要考慮其運(yùn)行時(shí)間外，更重要的是要在可重構(gòu)器件中找到合適的放置位置，使得多個(gè)硬件任務(wù)在可重構(gòu)器件上并行地執(zhí)行[2]。本文主要研究在基于FPGA計(jì)算加速的可重構(gòu)高性能計(jì)算平臺(tái)系統(tǒng)中硬件任務(wù)的在線調(diào)度與放置算法與體系結(jié)構(gòu)。

在FPGA上的基于二維的任務(wù)放置的研究已經(jīng)取得了不少的研究成果，一般的放置算法均可以直接作為調(diào)度算法使用，放置算法中早期的以BL[3]、QA[4]、RBL[5]等為代表, 該類算法具有完全識(shí)別能力, 但早期的算法復(fù)雜度較高, 與可重構(gòu)計(jì)算單元(Reconfigurable Computing Unit，RCU)數(shù)量成正比。

在硬件任務(wù)的調(diào)度上，除了空間因素之外，還需考慮時(shí)間屬性，因此基于預(yù)約的任務(wù)調(diào)度被提了出來。文獻(xiàn)[6]提出一種緊湊預(yù)約(Compact Reservation，CR)調(diào)度算法, 考慮所有的運(yùn)行任務(wù)和預(yù)約任務(wù)，計(jì)算到達(dá)任務(wù)的接受區(qū)域各RCU最早可用時(shí)間，選擇一個(gè)滿足到達(dá)任務(wù)截止期要求的放置點(diǎn), 該算法能夠在一定程度上提高任務(wù)截止期保證率。文獻(xiàn)[7]提出的Stuffing調(diào)度算法通過模擬未來時(shí)刻任務(wù)的終止和啟動(dòng)來為到達(dá)任務(wù)預(yù)約放置區(qū)域, 它是一種比較通用的算法，能夠和現(xiàn)有的基于空閑空間的放置算法融合。而在文獻(xiàn)[8]中作者提出一種基于時(shí)間窗口的Stuffing調(diào)度算法，從可以將Stuffing算法與掃描類放置算法進(jìn)行融合。在進(jìn)行任務(wù)調(diào)度時(shí)，通過在放置過程中，需要考慮FPGA的碎片化[9]程度來作為硬件任務(wù)放置到FPGA上的具體位置的一個(gè)決策依據(jù)，同時(shí)也會(huì)產(chǎn)生相應(yīng)的碎片化評(píng)估算法與策略。而有的算法則是將時(shí)間與空間上的平衡[10]作為硬件任務(wù)調(diào)度的算法制定基礎(chǔ)，而文獻(xiàn)[11]中則提出一種R-T坐標(biāo)體系，來構(gòu)建FPGA上的任務(wù)調(diào)度算法。

縱觀以上的從不同的視角出發(fā)所構(gòu)建的關(guān)于FPGA上的硬件任務(wù)調(diào)度與管理算法，并沒有從在基于多個(gè)FPGA上的資源對(duì)任務(wù)的競(jìng)爭(zhēng)上來考慮任務(wù)調(diào)度算法的制定與構(gòu)建。而異構(gòu)高性能計(jì)算平臺(tái)上的FPGA硬件任務(wù)調(diào)度除了要考慮在節(jié)點(diǎn)上的任務(wù)調(diào)度之外，還要考慮任務(wù)如何在計(jì)算節(jié)點(diǎn)之間進(jìn)行抉擇，因此在本文中我們將研究如何通過基于時(shí)間與空間情境下的任務(wù)調(diào)度體系與算法。

1 任務(wù)調(diào)度模型

從調(diào)度系統(tǒng)的功能結(jié)構(gòu)上，基于FPGA的異構(gòu)高性能計(jì)算平臺(tái)上的硬件任務(wù)調(diào)度為一個(gè)多級(jí)任務(wù)調(diào)度系統(tǒng)，一般包括全局任務(wù)調(diào)度與節(jié)點(diǎn)任務(wù)調(diào)度兩級(jí)系統(tǒng)。根據(jù)本文的研究方向,對(duì)高性能計(jì)算平臺(tái)，其每個(gè)計(jì)算節(jié)點(diǎn)都是由通用處理器CPU和FPGA加速部件組成。CPU處理系統(tǒng)中的軟件任務(wù)，而FPGA加速部件則處理系統(tǒng)中的硬件任務(wù)。本文僅研究如何調(diào)度和處理系統(tǒng)中的硬件任務(wù)。該系統(tǒng)調(diào)度模型分為平臺(tái)任務(wù)調(diào)度與節(jié)點(diǎn)內(nèi)任務(wù)調(diào)度兩部分，調(diào)度系統(tǒng)軟件運(yùn)行在主處理器CPU上，而硬件任務(wù)則是運(yùn)行在可重構(gòu)器件FPGA上。

(1) 定義1：最大空閑矩形MFR。不能被其他任何一個(gè)空閑矩形所完全覆蓋的空閑矩形為最大空閑矩形(Maximal Free Rectangle,MFR)[12-15]。對(duì)MFR的表示有多種方式，如：矩形的4個(gè)頂點(diǎn)坐標(biāo)、矩形放置的左下角基點(diǎn)與矩形的長(zhǎng)寬等。本文使用(xF,yF,w,h)來表示一個(gè)MFR，(xF,yF)是MFR左下角RCU的坐標(biāo)，w與h是其寬與高。

(2) 定義2:硬件任務(wù)，包括待調(diào)度任務(wù)與正在運(yùn)行任務(wù)。一個(gè)待調(diào)度任務(wù)定義為5元組：T(w,h,a,e,d)。其中w與h代表任務(wù)運(yùn)行時(shí)占用的RCU的寬與高，則該任務(wù)面積AT=w*h，a為任務(wù)的到達(dá)時(shí)間，e為任務(wù)在FPGA上的預(yù)期運(yùn)行時(shí)間，d為任務(wù)的截止時(shí)間，實(shí)時(shí)硬件任務(wù)必須滿足時(shí)間約束關(guān)系a+e≤d。一個(gè)正在運(yùn)行任務(wù)定義為7元組：TR(xR,yR,w,h,tS,e,tR)。xR與yR為該任務(wù)左下角在FPGA上的坐標(biāo)點(diǎn)，tS為該任務(wù)在FPGA上的開始運(yùn)行時(shí)間，tR為該任務(wù)在時(shí)刻t0時(shí)的剩余運(yùn)行時(shí)間。

(3) 定義3：任務(wù)情境。將硬件任務(wù)根據(jù)其相關(guān)的屬性，如：面積、運(yùn)行時(shí)間、發(fā)生概率等，而將任務(wù)分為不同的情境。比如：根據(jù)任務(wù)的面積來劃分任務(wù)情境時(shí)，可以設(shè)定一個(gè)面積閾值VA，當(dāng)任務(wù)面積AT≥VA時(shí)，將該任務(wù)劃分入大面積任務(wù)情境，否則劃分入小面積任務(wù)情境。

(4) 定義4資源情境。將FPGA上的空閑資源根據(jù)其相關(guān)的屬性，如面積、所在位置、邊線組成情況等，將FPGA劃分為不同的情境。比如：根據(jù)MFR的邊線是否包含F(xiàn)PGA邊界來劃分MFR資源情境時(shí)，可以將MFR劃分為非臨邊情境(Inner MFR,IM)、臨邊情境(Border MFR,BM)與頂角情境(Corner MFR,CM)，如圖1所示。非臨邊情境IM指的是MFR的4條邊線中不包含F(xiàn)PGA的邊界線的子線段，如圖1中的R3所示。臨邊情境BM指的是MFR的4條邊中只有1條邊線為FPGA邊界線的子線段，如圖1中的R5所示。頂角情境CM所指的是MFR的4個(gè)頂角中至少有1個(gè)頂角是FPGA的頂角，如圖1中的R1、R2與R4所示。

圖1 MFR資源位置情境實(shí)例

2 CBTA算法

對(duì)于任務(wù)集ST，F(xiàn)PGA上的任務(wù)調(diào)度系統(tǒng)關(guān)心的是如何將該ST內(nèi)的所有的任務(wù)都盡量放置在本FPGA中，而盡量減少等待時(shí)間或減少任務(wù)拒絕率，而在高性能平臺(tái)中，對(duì)每個(gè)FPGA而言，其關(guān)心的是如何能夠讓該ST內(nèi)更多的任務(wù)來在“我”的FPGA上完成運(yùn)行，而如何完成ST內(nèi)所有任務(wù)的調(diào)度是平臺(tái)調(diào)度所關(guān)心的，如何讓多個(gè)節(jié)點(diǎn)共同來分擔(dān)一部份任務(wù)子集。對(duì)于計(jì)算節(jié)點(diǎn)間的負(fù)載是否均衡，對(duì)于FPGA上任務(wù)調(diào)度而言，無(wú)須關(guān)心，其只需關(guān)心在該FPGA上的碎片化、負(fù)載率等問題。而平臺(tái)任務(wù)調(diào)度，需要考慮不同計(jì)算節(jié)點(diǎn)間的負(fù)載均衡以及任務(wù)的吞吐量，而對(duì)于每個(gè)節(jié)點(diǎn)上的FPGA上的每個(gè)具體任務(wù)而言，則需要在任務(wù)平臺(tái)上如何分配或者說是拿到對(duì)自己而言是“利益最大”的那個(gè)任務(wù)。

2.1 任務(wù)情境與資源情境

在基于以上關(guān)于任務(wù)情況與FPGA二維空間與時(shí)間維上的綜合分析，我們提出了一個(gè)關(guān)于硬件任務(wù)放置與調(diào)度的基于時(shí)空情景(Context Based on Time and Area,CBTA)算法。

2.1.1 任務(wù)情境劃分

對(duì)于任務(wù)情境我們從時(shí)間與空間的角度來對(duì)任務(wù)情境進(jìn)行劃分。根據(jù)任務(wù)的面積w*h，來將任務(wù)劃分為N個(gè)不同的任務(wù)情境，N的取值取決于FPGA空間的大小與該平臺(tái)上的任務(wù)大小的分布及其發(fā)生的概率。在本文中我們的實(shí)例是將任務(wù)劃分為大面積任務(wù)(Large Square Rectangle Task,LSRT)、中面積任務(wù)(Middle Square Rectangle Task,MSRT)、小面積任務(wù)(Small Square Rectangle Task,SSRT)與極端矩形任務(wù)(Extreme Rectangle Task,ERT)。根據(jù)運(yùn)行時(shí)間來對(duì)任務(wù)劃分情境，根據(jù)某個(gè)時(shí)間閾值，將任務(wù)劃分為長(zhǎng)運(yùn)行時(shí)間任務(wù)(Long Run Time Task,LRTT)與短運(yùn)行時(shí)間任務(wù)(Short Run Time Task,SRTT)。

2.1.2 資源情境劃分

對(duì)于資源情境我們從空間與位置的角度來對(duì)MFR資源情境進(jìn)行劃分。對(duì)MFR資源的面積劃分與任務(wù)的面積w*h的劃分保持對(duì)應(yīng)，也對(duì)應(yīng)劃分為N個(gè)不同的MFR資源情境。同樣在本文中我們將MFR劃分為大面積MFR、中面積MFR、小面積MFR與極端矩形MFR。MFR沒有直接的與時(shí)間情境有關(guān)的屬性，但可以從其它的屬性中來獲取MFR上與時(shí)間相關(guān)的屬性，比如：對(duì)于一個(gè)運(yùn)行時(shí)間很長(zhǎng)的任務(wù)，如果將其放置在FPGA的中央?yún)^(qū)域時(shí)，會(huì)造成長(zhǎng)時(shí)間上的占據(jù)FPGA中間位置，而造成FPGA上的碎片化。而如果將其放置到FPGA上的邊線或頂角上，則對(duì)FPGA造成的碎片化影響是較小甚至是最小的，如圖2所示。

圖2中，F(xiàn)PGA上正在運(yùn)行多個(gè)任務(wù)，其中每個(gè)任務(wù)的小括號(hào)中為該任務(wù)的剩余運(yùn)行時(shí)間。而T13是即將放置到FPGA上的新任務(wù)，可以看出其運(yùn)行時(shí)間為120，有2個(gè)可以放置T13的MFR，分為R2與R3。R2的空間位置情境為IM，雖然其面積與T13的面積正好相等，但R3為CM情境，所以我們將T13放置到R3中。因?yàn)楫?dāng)20時(shí)間單位過去以后，如果T13在R2的位置上，則整個(gè)FPGA空間上所產(chǎn)生的新MFR的面積不會(huì)有很大的，而在R3的位置上，則MFR可以產(chǎn)生很大面積的新MFR。

圖2 長(zhǎng)運(yùn)行任務(wù)時(shí)間放置情境

對(duì)于資源情境，我們分為節(jié)點(diǎn)資源情境與節(jié)點(diǎn)上MFR資源情境。節(jié)點(diǎn)資源情境為最大的MFR資源情境，MFR資源情境按面積從大到小進(jìn)行排序，排序順序?yàn)榇竺娣eMFR、極端矩形MFR、中面積MFR與小面積MFR。若當(dāng)前MFR的最大資源情境為大面積MFR資源情境，則節(jié)點(diǎn)資源情境為大面積MFR資源情境。

2.2 CBTA調(diào)度體系

在基于FPGA計(jì)算加速的異構(gòu)高性能計(jì)算平臺(tái)中，對(duì)任務(wù)的放置與調(diào)度策略，是在傳統(tǒng)的嵌入式系統(tǒng)上的進(jìn)一步擴(kuò)展，因此任務(wù)調(diào)度與放置將分為以下4個(gè)過程：

(1) 如何選擇滿足條件的候選計(jì)算節(jié)點(diǎn)；

(2) 如何從多個(gè)計(jì)算節(jié)點(diǎn)選中一個(gè)合適的FPGA；

(3) 如何從選中FPGA中選擇一個(gè)合適的MFR；

(4) 如何將任務(wù)放置到MFR資源的合適位置上。

由于一個(gè)硬件任務(wù)最終運(yùn)行在FPGA上要經(jīng)過上面的4個(gè)過程，那么在基于任務(wù)情境與資源情境下，我們對(duì)應(yīng)4個(gè)過程提出了一個(gè)CBTA調(diào)度體系。根據(jù)高性能計(jì)算平臺(tái)的體系結(jié)構(gòu)與本文模型的約定，我們?cè)O(shè)定如下調(diào)度模型。對(duì)于計(jì)算平臺(tái)上的每個(gè)計(jì)算節(jié)點(diǎn)而言，設(shè)定其FPGA上的所有RCU資源為一個(gè)租用對(duì)像，而在FPGA上運(yùn)行的任務(wù)，其占用的RCU資源作為一次租用，當(dāng)任務(wù)運(yùn)行結(jié)束時(shí)，租用結(jié)束，并按其租用的RCU數(shù)與時(shí)間進(jìn)行租金支付。因此，每個(gè)FPGA都希望自己能夠?qū)⒆约旱腞CU資源全部出租出去或者盡可能多接收任務(wù)。

從平臺(tái)的角度，希望用戶提交到平臺(tái)的任務(wù)盡可能全部被提交到FPGA上完成任務(wù)運(yùn)行，而同時(shí)也要保證每個(gè)FPGA之間的負(fù)載量維持在一個(gè)均衡的角度。從用戶的角度，則是希望所提交的任務(wù)能夠盡快地完成提交并看到任務(wù)開始運(yùn)行，至于是在哪個(gè)FPGA上，在FPGA的什么位置上用戶不需關(guān)心。

CBTA任務(wù)調(diào)度的基本策略為：對(duì)用戶提交的任務(wù)首先進(jìn)行任務(wù)情境檢測(cè)，根據(jù)其情境，放入到對(duì)應(yīng)的情境任務(wù)隊(duì)列；在資源端，每個(gè)計(jì)算節(jié)點(diǎn)在計(jì)算好自己的MFR資源全集后，對(duì)MFR進(jìn)行資源情境分類，并確定節(jié)點(diǎn)資源情境；在全局資源管理器端，根據(jù)每個(gè)節(jié)點(diǎn)資源情境，確定好節(jié)點(diǎn)資源隊(duì)列，然后在對(duì)應(yīng)的任務(wù)情境與資源情境間進(jìn)行資源匹配。以大面積任務(wù)隊(duì)列匹配大面積MFR節(jié)點(diǎn)資源隊(duì)列為例來說明任務(wù)調(diào)度策略，任務(wù)的調(diào)度不是由調(diào)度器任務(wù)去分配資源，而是由資源節(jié)點(diǎn)在任務(wù)隊(duì)列上來取任務(wù)。取節(jié)點(diǎn)資源隊(duì)列的當(dāng)前頭節(jié)點(diǎn)，然后依次在任務(wù)隊(duì)列上從頭節(jié)點(diǎn)開始匹配，如果當(dāng)前隊(duì)列節(jié)點(diǎn)上的任務(wù)能放置到該資源節(jié)點(diǎn)的MFR上，則取走該節(jié)點(diǎn)任務(wù)。繼續(xù)下一個(gè)資源頭節(jié)點(diǎn)，繼續(xù)在剩余的任務(wù)隊(duì)列上來取任務(wù)。而完成放置任務(wù)的資源節(jié)點(diǎn)，如果其資源情境沒有發(fā)生變化，則將其節(jié)點(diǎn)排在節(jié)點(diǎn)資源隊(duì)列的末尾。

在節(jié)點(diǎn)任務(wù)調(diào)度系統(tǒng)上，被節(jié)點(diǎn)資源選中的任務(wù)將根據(jù)一定的算法，在進(jìn)行MFR選定時(shí)，我們基于以下原則來進(jìn)行算法與策略的制定：①任務(wù)與資源對(duì)位匹配優(yōu)先原則；②長(zhǎng)運(yùn)行時(shí)間任務(wù)優(yōu)先放置到頂角MFR、臨邊MFR的原則；③大面積MFR入侵避免的原則；④如果資源節(jié)點(diǎn)上有滿足當(dāng)前任務(wù)TH的資源空間，則一定將調(diào)度該任務(wù)。在選定MFR之后，再根據(jù)任務(wù)所屬的任務(wù)情境與MFR的資源情境的具體對(duì)應(yīng)，而選擇不同的任務(wù)放置策略。

2.3 計(jì)算節(jié)點(diǎn)競(jìng)爭(zhēng)策略

當(dāng)任務(wù)少，而資源空間多或者當(dāng)節(jié)點(diǎn)資源隊(duì)列在確定每個(gè)資源節(jié)點(diǎn)的位置時(shí)，必然要發(fā)生資源競(jìng)爭(zhēng)問題，需要制定合理的任務(wù)與資源間的競(jìng)爭(zhēng)策略，為了更好地提高每個(gè)資源節(jié)點(diǎn)上的資源利用率與負(fù)載均衡，我們采用資源負(fù)載率低優(yōu)先的策略。

我們將時(shí)間維引入進(jìn)負(fù)載率，將資源負(fù)載率LX重新定義：

令tRi為當(dāng)前任務(wù)i的剩余運(yùn)行時(shí)間，tRi=tE-tC+tS。當(dāng)所有進(jìn)行比較的資源節(jié)點(diǎn)的LX，其值最小的將排在第一位，如果最小值相等，則隨機(jī)從其中選取一個(gè)節(jié)點(diǎn)。

2.4 資源情境與任務(wù)情境匹配算法

不同的任務(wù)情境在對(duì)應(yīng)不同的資源情境時(shí)，由于沒有一種算法能夠?qū)Ω鞣N任務(wù)情境都產(chǎn)生好的效果，因此在不同的任務(wù)情境與資源情境的對(duì)應(yīng)中，應(yīng)采取適合于本情境下的任務(wù)資源分配算法。

在大面積MFR資源情境(Large Square MFR Resource,LSMR)下，可以放置的任務(wù)有：大面積任務(wù)LSRT、極端矩形任務(wù)ERT、中面積任務(wù)MSRT、小面積任務(wù)SSRT。對(duì)于每一種任務(wù)的面積情境，還對(duì)應(yīng)著兩種附加時(shí)間情境：長(zhǎng)運(yùn)行時(shí)間情境LRTT與短運(yùn)行時(shí)間情境SRTT。

對(duì)于大面積任務(wù)情境LSRT，則采用大面積MFR入侵避免(Large MFR Invasion Avoiding First,LMIAF)與基于閾值碎片化(Defragmentation Threshold Based Best-Fit First,DTBBF)算法。

大面積MFR入侵避免算法LMIAF:設(shè)大面積MFR，其表示為ML(XL1,YL1,WL,HL)，而硬件任務(wù)TH放置在另外一個(gè)MFR(設(shè)為MA)之后，其左下角坐標(biāo)為(XH1,YH1)，硬件任務(wù)的寬與高為(WH,HH)。判斷該硬件任務(wù)TH是否入侵該MFR的計(jì)算如下：

ML的右上角坐標(biāo)為(XL3,YL3)=(XL1+WL-1,YL1+HL-1)，放置后的TH的右上角坐標(biāo)為(XH3,YH3) =(XH1+WH-1,YH1+HH-1)。IF (XH3>XL1&&XH1YL1&&YH1XL1&&XH1YL1&&YH1

閾值碎片化優(yōu)先算法DTBBF，即：MFR的寬與高，要么與所選中任務(wù)TH的寬與高相同，要么其寬與高和TH的寬與高的之差大于等于一個(gè)閾值VW與VH。

對(duì)于極端矩形任務(wù)情境ERT，則采用大面積MFR入侵避免算法LMIAF。

對(duì)于中面積任務(wù)情境MSRT，則采用大面積MFR入侵避免LMIAF與最長(zhǎng)相連實(shí)邊(Maximal Connected Real Edge First，MCREF)算法。

最長(zhǎng)相連實(shí)邊優(yōu)先算法MCREF，所謂相連實(shí)邊，指的是構(gòu)成MFR的實(shí)邊EM1(n1,m1)與EM2(n2,m2)，n到m的方向?yàn)閺淖笙蛴一驈纳舷蛳?。如果兩條實(shí)邊相連，則一定有：n1==m2||m1==n2||n1==n2||m1==m2，且EM1與EM2的交點(diǎn)一定為MFR的頂點(diǎn)。

MFS= max(LM1,LM2, …LMQ)，Q表示共有Q個(gè)候選MFR。

對(duì)于小面積任務(wù)情境SSRT，則采用大面積MFR入侵避免算法LMIAF與最長(zhǎng)相連實(shí)邊算法MCREF。

在極端矩形MFR資源情境(Extreme MFR Resource,EMR)下，可能可以放置的任務(wù)有：極端矩形任務(wù)ERT、中面積任務(wù)MSRT、小面積任務(wù)SSRT。

對(duì)于極端矩形任務(wù)情境ERT，則采用基于Best-Fit的算法。

對(duì)于中面積任務(wù)情境MSRT，則采用基于同高或同寬優(yōu)先SWSHF(Same Width or Same Height First)算法。

同高或同寬優(yōu)先算法SWSHF，即任務(wù)的高與寬至少要有一個(gè)與MFR的高與寬要相等，如果沒有條件滿足其要求，則選隊(duì)列中的第一個(gè)能放置的下的MFR。

IF (TH.W==ML.W||TH.H==ML.H)，則選擇該ML放置該硬件任務(wù)TH。

對(duì)于小面積任務(wù)情境SSRT，則采用最長(zhǎng)相連實(shí)邊算法MCREF。

在中面積MFR資源情境(Middle Square MFR Resource,MSMR)下，可以放置的任務(wù)有：中面積任務(wù)MSRT、小面積任務(wù)SSRT。

對(duì)于中面積任務(wù)情境MSRT，則采用最長(zhǎng)相連實(shí)邊MCREF與基于閾值碎片化算法DTBBF。

對(duì)于小面積任務(wù)情境SSRT，則采用最長(zhǎng)相連實(shí)邊算法MCREF。

在小面積MFR資源情境(Small Square MFR Resource,SSMR)下，可以放置的任務(wù)有：小面積任務(wù)SSRT。

對(duì)于小面積任務(wù)情境SSRT，則采用最長(zhǎng)相連實(shí)邊算法MCREF。

因此，我們需要有一個(gè)動(dòng)態(tài)的情境任務(wù)調(diào)度算法庫(kù)(Dynamic Context Task Schedule Library,DCTSAL)，來保存各種不同任務(wù)與資源情境匹配下的任務(wù)調(diào)度與任務(wù)放置算法，以供任務(wù)在線調(diào)度時(shí)及時(shí)調(diào)用。

3 實(shí)驗(yàn)?zāi)M

本文實(shí)驗(yàn)用抽象模型的模擬調(diào)度來評(píng)估算法的調(diào)度性能。仿真環(huán)境是在Windows下用VC++開發(fā)的實(shí)驗(yàn)?zāi)M程序。每個(gè)實(shí)驗(yàn)是在多次運(yùn)行以后得到的平均值，因?yàn)樵趯?shí)驗(yàn)環(huán)境的參數(shù)中，多次使用隨機(jī)函數(shù)產(chǎn)生的相關(guān)數(shù)據(jù)，因此采用多次運(yùn)算的平均值。

在任務(wù)調(diào)度中，設(shè)定FPGA為20*20，每個(gè)計(jì)算節(jié)點(diǎn)1個(gè)FPGA計(jì)算加速部件，大矩形任務(wù)LSRT的面積AL≥8*8=64,且WL≥8 andHL≥8；中矩形任務(wù)MSRT的面積AM≥4*4，且4≤WM<8 and 4≤HM<8；小矩形任務(wù)SSRT的面積AM<4*4，且1≤WM<4 and 1≤HM<4；其它情況為極端矩形任務(wù)ERT；而長(zhǎng)時(shí)間任務(wù)LRTT與短運(yùn)行時(shí)間任務(wù)SRTT不設(shè)立單獨(dú)的隊(duì)列，根據(jù)其矩形的形狀分散于不同的矩形隊(duì)列處理的并行分支中。

試平臺(tái)環(huán)境為4核，采用OpenMPI的基于ShareMemory的編程模式，考慮到在任務(wù)的不同情境中所出現(xiàn)的概率與在等待任務(wù)隊(duì)列中大任務(wù)與極端任務(wù)出現(xiàn)等待的情況要遠(yuǎn)遠(yuǎn)高于中矩形與小矩形任務(wù)，因此，在對(duì)并行隊(duì)列的并行處理上將到達(dá)與等待隊(duì)列結(jié)合起來，分配策略如下：

到達(dá)大面積任務(wù)隊(duì)列ALRTQ + 等待大面積任務(wù)隊(duì)列WLRTQ；

到達(dá)極端矩形任務(wù)隊(duì)列AERTQ + 等待極端矩形任務(wù)隊(duì)列WERTQ；

到達(dá)中面積任務(wù)隊(duì)列AMRTQ + 等待中面積任務(wù)隊(duì)列WMRTQ；

到達(dá)小面積任務(wù)隊(duì)列ASRTQ + 等待小面積任務(wù)隊(duì)列WSRTQ。

測(cè)試條件如下：

C1：計(jì)算節(jié)點(diǎn)4個(gè)，任務(wù)集200；

C2：計(jì)算節(jié)點(diǎn)8個(gè)，任務(wù)集800；

C3：計(jì)算節(jié)點(diǎn)16個(gè)，任務(wù)集3 200；

C4：計(jì)算節(jié)點(diǎn)32個(gè)，任務(wù)集6 400。

在圖3中，X方向上測(cè)試條件C1～C4，在Y方向上則是算法在平臺(tái)級(jí)的運(yùn)行時(shí)間(μs)，該時(shí)間不包含任務(wù)在節(jié)點(diǎn)上的調(diào)度與放置時(shí)間，也不包含等待任務(wù)運(yùn)行完成的時(shí)間?？梢钥闯觯谥挥?個(gè)節(jié)點(diǎn)時(shí)，任務(wù)調(diào)度的串行與并行計(jì)算效果并沒有太大差別，但隨著計(jì)算資源的增大以及對(duì)應(yīng)的任務(wù)到達(dá)并發(fā)數(shù)目的增加，并行計(jì)算的優(yōu)勢(shì)逐漸顯現(xiàn)。

圖3 串行與并行運(yùn)行效果比較

我們另一個(gè)測(cè)試比較是在基于非情境算法的調(diào)度性能參數(shù)比較。在一般的基于高性能計(jì)算平臺(tái)上的任務(wù)調(diào)度算法并不適用于基于FPGA加速的高性能計(jì)算平臺(tái)上的硬件任務(wù)調(diào)度，在基于FPGA上的任務(wù)放置中，我們常用的算法有Best-Fit，F(xiàn)irst-Fit等。我們選基于Best-Fit的調(diào)度算法作為調(diào)度測(cè)試性能的依據(jù)。

基于Best-Fit調(diào)度算法調(diào)度過程如下，采用一個(gè)統(tǒng)一的全局資源隊(duì)列，來保存所有的計(jì)算節(jié)點(diǎn)上的MFR，對(duì)每個(gè)MFR除了標(biāo)記其大小空間屬性，還標(biāo)記其屬于哪個(gè)計(jì)算節(jié)點(diǎn)。當(dāng)有任務(wù)到達(dá)時(shí)，從資源隊(duì)列RQ中選擇一個(gè)面積、寬與高都相差最小的一個(gè)MFR作為要放置任務(wù)的MFR，之后更新MFR情況，并重新更新資源隊(duì)列，并繼續(xù)接收新任務(wù)。CBTA調(diào)度算法的參數(shù)與上面的參數(shù)相同，測(cè)試情況為相同的負(fù)載概率，測(cè)試條件也為設(shè)計(jì)算節(jié)點(diǎn)為16節(jié)點(diǎn)，任務(wù)集為1 000，2 000，3 000，4 000。

圖4為在不同的高負(fù)荷下的RCU數(shù)平均拒絕效果圖，X方向?yàn)檫\(yùn)行的任務(wù)集，Y方向上平均RCU數(shù)。由圖中可以看出，因?yàn)锽est-Fit為非情境模式，不能用并行程序?qū)崿F(xiàn)，而CBTA則是用并行程序?qū)崿F(xiàn)。而在基于自適應(yīng)的節(jié)點(diǎn)任務(wù)調(diào)度策略中，通過根據(jù)不同的情境，對(duì)應(yīng)不同的任務(wù)調(diào)度與放置算法，因此，在任務(wù)的吞吐率與響應(yīng)時(shí)間上，體現(xiàn)了較高的優(yōu)勢(shì)。當(dāng)任務(wù)集增加以后，非情境的Best-Fit算法的計(jì)算時(shí)間與響應(yīng)時(shí)間明顯增加，因?yàn)闆]有分情境，所以以串行的方式進(jìn)行計(jì)算，而CBTA則是以4核并行計(jì)算，同時(shí)，大面積矩形任務(wù)的拒絕率的下降最為顯著。

圖4 任務(wù)拒絕RCU數(shù)效果圖

圖5為負(fù)載均衡效果圖。X方向上為任務(wù)集，Y方向上為平均負(fù)載率差，即最高負(fù)載節(jié)點(diǎn)的負(fù)載率-最低負(fù)載節(jié)點(diǎn)的負(fù)載率，比如：某時(shí)刻t0時(shí)，最高負(fù)載節(jié)點(diǎn)為節(jié)點(diǎn)5，其負(fù)載率為82%，而最低負(fù)載節(jié)點(diǎn)為節(jié)點(diǎn)13，其負(fù)載率為40%，則負(fù)載率差為82%-40%=42%。在負(fù)載率差上，我們?nèi)〔煌?0個(gè)時(shí)刻時(shí)的負(fù)載率差之后的平均值?？梢钥闯?，在CBTA算法下，節(jié)點(diǎn)之間的平均負(fù)載率差相對(duì)比較穩(wěn)定，且負(fù)載均衡遠(yuǎn)遠(yuǎn)好于Best-Fit算法。

圖5 負(fù)載均衡效果圖

4 結(jié) 語(yǔ)

本文中，針對(duì)基于FPGA計(jì)算加速的異構(gòu)高性能計(jì)算平臺(tái)上的硬件任務(wù)調(diào)度需求，根據(jù)硬件任務(wù)的空間屬性與時(shí)間屬性，提出了一個(gè)基于時(shí)空情境CBTA的任務(wù)調(diào)度算法。高性能計(jì)算平臺(tái)的分級(jí)調(diào)度將CBTA的調(diào)度分為平臺(tái)任務(wù)調(diào)度與節(jié)點(diǎn)任務(wù)調(diào)度，我們將任務(wù)與資源劃分為不同的時(shí)空情境，提出了一個(gè)基于情境轉(zhuǎn)化的自適應(yīng)任務(wù)調(diào)度算法，并根據(jù)不同的任務(wù)與資源情境分別提出了適合對(duì)應(yīng)情境的任務(wù)調(diào)度與放置算法，并給出了CBTA調(diào)度算法的并行優(yōu)化策略，通過實(shí)驗(yàn)來說明了算法在對(duì)用戶響應(yīng)時(shí)間、負(fù)載均衡以及任務(wù)拒絕率上的優(yōu)勢(shì)。

在下一步的研究中，我們將更好地對(duì)分級(jí)調(diào)度中的任務(wù)與資源情境進(jìn)行進(jìn)一步研究，以更好地適應(yīng)基于任務(wù)上的空間與時(shí)間上的調(diào)度算法。同時(shí)我們將對(duì)高性能計(jì)算架構(gòu)進(jìn)一步的進(jìn)行擴(kuò)展，包括的架構(gòu)如每個(gè)計(jì)算節(jié)點(diǎn)上有多個(gè)FPGA加速部件時(shí)，當(dāng)FPGA之間的性能具有差異時(shí)，如何能實(shí)現(xiàn)更高效的任務(wù)調(diào)度與放置等。

[1] 周 博,王石記,邱衛(wèi)東,等. SHUM-UCOS:基于統(tǒng)一多任務(wù)模型可重構(gòu)系統(tǒng)的實(shí)時(shí)操作系統(tǒng)[J].計(jì)算機(jī)學(xué)報(bào), 2006, 29(2): 208-218.

[2] 周學(xué)功, 梁 樑, 黃勛章, 等. 可重構(gòu)系統(tǒng)中的實(shí)時(shí)任務(wù)在線調(diào)度與放置算法[J].計(jì)算機(jī)學(xué)報(bào), 2007, 30(11):1901-1908.

[3] 莎爾瑪 D D, 普拉丹 D K. 一個(gè)快速有效子網(wǎng)格在網(wǎng)狀連接并行計(jì)算機(jī)內(nèi)的分配方法[C]: // 第五屆IEEE并行分布式處理會(huì)議論文集, 華盛頓DC, IEEE計(jì)算機(jī)學(xué)會(huì), 1993: 682-689.

[4] YOO S M, YOUNG H Y, SHIRAZIB. 2D網(wǎng)眼架構(gòu)上的高效任務(wù)分配框架[J]. IEEE并行與分布式系統(tǒng)匯刊, 1997, 8(9): 934-942.

[5] CHIU G M, CHEN S K. 一個(gè)高效的極少開銷代價(jià)的二維網(wǎng)眼上的子網(wǎng)格分配框架[J]. IEEE并行與分布式系統(tǒng)匯刊, 1999, 10(3): 471-486.

[6] 周學(xué)剛, 王 英, 黃新章. 可重構(gòu)設(shè)備上快速任務(wù)放置與調(diào)度[C] //2007年國(guó)際可編程陣列邏輯與應(yīng)用國(guó)際會(huì)議論文集, 華盛頓DC, IEEE, 2007:132-138.

[7] 施泰格 C, 瓦爾德 H, 普拉則內(nèi) M. 部分可重構(gòu)設(shè)備上實(shí)時(shí)任務(wù)在線調(diào)度與放置[C] // 第24屆國(guó)際實(shí)時(shí)系統(tǒng)會(huì)議論文集, 華盛頓DC, IEEE計(jì)算機(jī)學(xué)會(huì), 2003:224-235.

[8] 周學(xué)剛, 王 英, 黃新章. 可重構(gòu)計(jì)算機(jī)系統(tǒng)實(shí)時(shí)任務(wù)在線調(diào)度[C] // 2006年國(guó)際可編程陣列邏輯與應(yīng)用國(guó)際會(huì)議論文集, IEEE, 2006: 57-64.

[9] 艾哈邁德 A E, 埃爾伯達(dá) M, 沙辛 S I. 碎片化敏感的可重構(gòu)設(shè)備任務(wù)放置[C] // 第六屆片上系統(tǒng)實(shí)時(shí)應(yīng)用國(guó)際會(huì)議, 華盛頓DC, IEEE, 2006: 37-44.

[10] 伊圖爾貝 X, 貝殼里德 K, 阿斯蘭 T, 等. 基于區(qū)間-時(shí)間反應(yīng)平衡的實(shí)時(shí)硬件任務(wù)調(diào)度算法[C] // 2010年IEEE現(xiàn)場(chǎng)可編程技術(shù)國(guó)際會(huì)議, 北京, 2010: 224-232.

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

[12] 柴亞輝, 沈文楓, 徐煒民, 等. 基于CPTR的FPGA空閑矩形資源全集查找研究[J]. 上海大學(xué)學(xué)報(bào)(英文版), 2011, 15(5): 391-394.

[13] 柴亞輝, 張勝輝, 黃衛(wèi)春, 等. 動(dòng)態(tài)部分可重構(gòu)系統(tǒng)空閑資源全集管理研究[J]. 計(jì)算機(jī)科學(xué), 2013, (2): 20-23.

[14] 李 濤, 楊愚魯. 基于最大空閑矩形的可重構(gòu)資源管理方法[J]. 計(jì)算機(jī)工程, 2008, 34(3): 46-48.

[15] 李 濤, 劉培峰, 楊愚魯. 動(dòng)態(tài)部分重配置及其FPGA實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程, 2006, 32(14):224-226.

Research on Task Schedule Architecture of Reconfigurable High Performance Computing Based on Time and Area Context

TUChun-ping,CHAIYa-hui,HUANGWei-chun,XIONGLi-yan

(College of Information Engineering, East China Jiao Tong University, Nanchang 330013, China)

According to the requirement of hardware task scheduling of heterogeneous high performance computing platform, based on FPGA computing accelerate, a task scheduling system is developed based on CBTA of time and area context. The development contains system architecture and related algorithms. The multi-level of task schedule on high performance platform divides the CBTA into platform task schedule and node task schedule. Classifying the task and resource into different time and area contexts, a self-adaptive task schedule strategy based on the resource context transform is proposed. Then a parallel optimization strategy is put forward. Finally through the experiment, the advantages of CBTA on response time, load balance and task reject ratio are shown.

FPGA computing accelerate; hardware task schedule; time and area contexts; self-adaptive schedule

2014-03-27

江西省自然科學(xué)基金項(xiàng)目(2014BAB201028)；華東交通大學(xué)校立基金(11XX04)

涂春萍(1970-)，女，江西南昌人，碩士，高級(jí)實(shí)驗(yàn)師，研究方向?yàn)榍度胧较到y(tǒng)。

Tel.：13970948355；E-mail：tcp@ecjtu.jx.cn，915412273@qq.com

TP 316

A

1006-7167(2015)03-0116-06