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

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

?

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

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

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

(4) 定義4資源情境。將FPGA上的空閑資源根據(jù)其相關(guān)的屬性，如面積、所在位置、邊線組成情況等，將FPGA劃分為不同的情境。比如：根據(jù)MFR的邊線是否包含F(xiàn)PGA邊界來劃分MFR資源情境時，可以將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個頂角中至少有1個頂角是FPGA的頂角，如圖1中的R1、R2與R4所示。

圖1 MFR資源位置情境實例

2 CBTA算法

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

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

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

2.1.1 任務(wù)情境劃分

對于任務(wù)情境我們從時間與空間的角度來對任務(wù)情境進行劃分。根據(jù)任務(wù)的面積w*h，來將任務(wù)劃分為N個不同的任務(wù)情境，N的取值取決于FPGA空間的大小與該平臺上的任務(wù)大小的分布及其發(fā)生的概率。在本文中我們的實例是將任務(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ù)運行時間來對任務(wù)劃分情境，根據(jù)某個時間閾值，將任務(wù)劃分為長運行時間任務(wù)(Long Run Time Task,LRTT)與短運行時間任務(wù)(Short Run Time Task,SRTT)。

2.1.2 資源情境劃分

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

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

圖2 長運行任務(wù)時間放置情境

對于資源情境，我們分為節(jié)點資源情境與節(jié)點上MFR資源情境。節(jié)點資源情境為最大的MFR資源情境，MFR資源情境按面積從大到小進行排序，排序順序為大面積MFR、極端矩形MFR、中面積MFR與小面積MFR。若當前MFR的最大資源情境為大面積MFR資源情境，則節(jié)點資源情境為大面積MFR資源情境。

2.2 CBTA調(diào)度體系

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

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

(2) 如何從多個計算節(jié)點選中一個合適的FPGA；

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

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

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

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

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

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

2.3 計算節(jié)點競爭策略

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

我們將時間維引入進負載率，將資源負載率LX重新定義：

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

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

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

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

對于大面積任務(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放置在另外一個MFR(設(shè)為MA)之后，其左下角坐標為(XH1,YH1)，硬件任務(wù)的寬與高為(WH,HH)。判斷該硬件任務(wù)TH是否入侵該MFR的計算如下：

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

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

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

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

最長相連實邊優(yōu)先算法MCREF，所謂相連實邊，指的是構(gòu)成MFR的實邊EM1(n1,m1)與EM2(n2,m2)，n到m的方向為從左向右或從上向下。如果兩條實邊相連，則一定有：n1==m2||m1==n2||n1==n2||m1==m2，且EM1與EM2的交點一定為MFR的頂點。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗?zāi)M

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

在任務(wù)調(diào)度中，設(shè)定FPGA為20*20，每個計算節(jié)點1個FPGA計算加速部件，大矩形任務(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；而長時間任務(wù)LRTT與短運行時間任務(wù)SRTT不設(shè)立單獨的隊列，根據(jù)其矩形的形狀分散于不同的矩形隊列處理的并行分支中。

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

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

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

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

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

測試條件如下：

C1：計算節(jié)點4個，任務(wù)集200；

C2：計算節(jié)點8個，任務(wù)集800；

C3：計算節(jié)點16個，任務(wù)集3 200；

C4：計算節(jié)點32個，任務(wù)集6 400。

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

圖3 串行與并行運行效果比較

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

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

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

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

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

圖5 負載均衡效果圖

4 結(jié) 語

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

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

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

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

[3] 莎爾瑪 D D, 普拉丹 D K. 一個快速有效子網(wǎng)格在網(wǎng)狀連接并行計算機內(nèi)的分配方法[C]: // 第五屆IEEE并行分布式處理會議論文集, 華盛頓DC, IEEE計算機學會, 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. 一個高效的極少開銷代價的二維網(wǎng)眼上的子網(wǎng)格分配框架[J]. IEEE并行與分布式系統(tǒng)匯刊, 1999, 10(3): 471-486.

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

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

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

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

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

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

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

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

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

[15] 李 濤, 劉培峰, 楊愚魯. 動態(tài)部分重配置及其FPGA實現(xiàn)[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

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

涂春萍(1970-)，女，江西南昌人，碩士，高級實驗師，研究方向為嵌入式系統(tǒng)。

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

TP 316

A

1006-7167(2015)03-0116-06