基于最優(yōu)虛擬截止日期多處理器混合時(shí)序調(diào)度

高啟明，吳莉莉

(1.邯鄲學(xué)院 機(jī)電學(xué)院，河北 邯鄲 056005；2.燕山大學(xué) 機(jī)械工程學(xué)院，河北 秦皇島 066000)

0 引 言

隨著現(xiàn)代科學(xué)技術(shù)的進(jìn)步，半導(dǎo)體工藝水平的提升可有效提高處理器計(jì)算性能約20倍，處理器生產(chǎn)廠家可在單個(gè)處理器中實(shí)現(xiàn)更強(qiáng)的計(jì)算性能[1,2]。但是對于個(gè)別大數(shù)據(jù)量運(yùn)算情形，仍然需要用到多處理器協(xié)調(diào)配合。在多核處理器誕生以前，多處理器計(jì)算是最為常用的大數(shù)據(jù)處理方式[3]。

文獻(xiàn)[4]采用可遷移算法對運(yùn)行任務(wù)進(jìn)行調(diào)度處理，實(shí)現(xiàn)了任務(wù)運(yùn)行調(diào)度的動(dòng)態(tài)調(diào)整。文獻(xiàn)[5]基于公平博弈理論對多處理器的資源調(diào)度過程進(jìn)行設(shè)計(jì)，相對于現(xiàn)有算法實(shí)現(xiàn)了算法處理性能有效提升。文獻(xiàn)[6]提出一種基于分組策略的提高多處理器使用效率的調(diào)度算法，可有效確保多任務(wù)計(jì)算過程中的截止時(shí)間問題。文獻(xiàn)[7]提出一種基于遺傳算法的多處理器任務(wù)調(diào)度算法，但是算法計(jì)算復(fù)雜度過高。文獻(xiàn)[8]提出一種多處理器互連網(wǎng)絡(luò)負(fù)載均衡算法，實(shí)現(xiàn)了網(wǎng)絡(luò)負(fù)載的均衡配置，獲得了良好的效果。文獻(xiàn)[9]提出基于全局隊(duì)列調(diào)度的多處理器任務(wù)遷移調(diào)度算法，但是多處理器之間數(shù)據(jù)的頻繁遷移過程會(huì)造成算法計(jì)算復(fù)雜度大幅提升。而文獻(xiàn)[10]提出基于局部隊(duì)列調(diào)度的多處理器任務(wù)調(diào)度算法，解決了上述任務(wù)需要在處理器間進(jìn)行遷移的問題，但是處理器內(nèi)部單核的處理能力有限。

本文提出基于最優(yōu)虛擬截止日期的多處理器混合時(shí)序調(diào)度算法，采用新的時(shí)序保證技術(shù)，以確保系統(tǒng)在兩個(gè)不同臨界值之間進(jìn)行過渡，并將所提可調(diào)度性測試擴(kuò)展到混合臨界系統(tǒng)，設(shè)計(jì)一種最優(yōu)虛擬截止日期分配策略。

1 問題描述

1.1 系統(tǒng)模型

(1)在調(diào)度算法方面，考慮全局非搶占調(diào)度，其中任務(wù)的一個(gè)作業(yè)可以在與任務(wù)的另一個(gè)作業(yè)不同的處理器核心上并行執(zhí)行，任務(wù)在算法執(zhí)行期間具有相對獨(dú)立性，所占用處理器不能在執(zhí)行任務(wù)調(diào)度的同時(shí)被任何作業(yè)搶占，并且如果至少有一個(gè)作業(yè)準(zhǔn)備好執(zhí)行，則處理器不能處于空閑狀態(tài)。

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

1.2 可調(diào)度條件

圖1 PS(τ)的工作運(yùn)行機(jī)制

W(NP-EDF(τ),J(τ,q),[0,t+YTR))≥
W(PS(τ),J(τ,q),[0,t))

(10)

式中：J(τ,q) 表示τ中任務(wù)調(diào)用的q作業(yè)集合，其中q是最早的絕對截止日期。為解決PS(τ) 在LO和HI模式下的執(zhí)行速率過低的問題，考慮滿足以下條件任務(wù)集

(11)

(12)

2 多處理器混合臨界最優(yōu)分配

2.1 可調(diào)度性分析

(13)

(14)

圖2 無虛擬截止日期PS(τ)運(yùn)行機(jī)制

(15)

(16)

(17)

2.2 最優(yōu)虛擬截止期分配

(18)

算法1： 系統(tǒng)級參數(shù)的最優(yōu)虛擬截止時(shí)間分配

輸入：m，n，U，CF，CP，ui，Ti

(2) ifLj=HI then

(4) else

(7) ifj≠j2then

(8)α←

(9) endif

(10) endif

(11) if 式(16)-式(17)成立 then

(12) return可調(diào)度；

(13) endif

(14) return不可調(diào)度；

(19)

(20)

(21)

算法1使用這3種情況計(jì)算α， 最終檢查可調(diào)度性(第(11)行-第(14)行)。然后，以下定理給出了算法1中α的虛擬截止時(shí)間分配的最優(yōu)性。

定理1 如果算法1返回不可調(diào)度結(jié)論，則對于任務(wù)τi∈τ|Li=HI情形下的αi=α和任務(wù)τi∈τ|Li=LOτi∈τ|Li=HI情形下的αi=1， 不存在α使得式(16)-式(17) 成立。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證所提多處理器任務(wù)調(diào)度算法的有效性，選取實(shí)驗(yàn)平臺(tái)為Revealer處理器，系統(tǒng)編譯軟件選取MPMD構(gòu)建實(shí)驗(yàn)平臺(tái)的前端編譯環(huán)境，同時(shí)選取GPU開源系統(tǒng)revealerel-gcc構(gòu)建實(shí)驗(yàn)平臺(tái)的后端編譯環(huán)境。本實(shí)驗(yàn)中所采用的硬件開發(fā)平臺(tái)如圖3所示。其中，共有10臺(tái)筆記本電腦，每個(gè)電腦模擬多個(gè)處理器實(shí)體，參與時(shí)序調(diào)度過程。選取第一排左側(cè)第一個(gè)電腦作為管理員主機(jī)，負(fù)責(zé)調(diào)度程序的運(yùn)行和過程調(diào)度，其余9臺(tái)電腦模擬任務(wù)處理過程，按照從前往后、從左至右的順序分別執(zhí)行任務(wù)如下：DCT、FFT、Gauss(Gau)、Histogram(His)、imgsmth(img)、MatricMult(Mat)、mergesort(mer)、shortEng(shor)、aveMotion(ave)。

圖3 實(shí)驗(yàn)平臺(tái)

對比算法：①程序流圖模塊多處理器調(diào)度算法(SGM)；②啟發(fā)式表多處理器調(diào)度算法(Heuristic)；③基本塊多處理器調(diào)度算法(Block)。其中，SGM算法本質(zhì)上是采用線性規(guī)劃策略的多處理器優(yōu)化調(diào)度算法，主要優(yōu)化目標(biāo)是多處理器任務(wù)處理的均衡，對于數(shù)據(jù)通信開銷指標(biāo)考慮較少；Heuristic算法采用的是一種表調(diào)度策略，考慮處理器承擔(dān)任務(wù)處理的優(yōu)先級問題，是一種多處理優(yōu)化調(diào)度的排隊(duì)策略。Block算法主要應(yīng)用在多處理器的流式處理系統(tǒng)開發(fā)中，基本特征是對基本塊設(shè)定了不能重復(fù)調(diào)度的限制。

3.2 實(shí)驗(yàn)對比

本實(shí)驗(yàn)中選取的對比指標(biāo)主要有4種：①啟動(dòng)時(shí)間；②實(shí)際執(zhí)行時(shí)間；③通信開銷；④存儲(chǔ)性能。實(shí)驗(yàn)對比結(jié)果如下：

實(shí)驗(yàn)1：(啟動(dòng)時(shí)間)多處理任務(wù)調(diào)度中，啟動(dòng)時(shí)間指標(biāo)越低，表明多處理器任務(wù)協(xié)調(diào)調(diào)度性能越好，此時(shí)多處理器進(jìn)行調(diào)度算法具有更高的線程執(zhí)行效率。圖4為選取的幾種對比算法在實(shí)驗(yàn)仿真平臺(tái)上的啟動(dòng)時(shí)間指標(biāo)實(shí)驗(yàn)結(jié)果對比情況。為了更清晰表征算法之間的實(shí)驗(yàn)結(jié)果差別，圖中所示數(shù)據(jù)為本文算法相對于對比算法在啟動(dòng)時(shí)間上降低的幅度比例。

圖4 啟動(dòng)時(shí)間指標(biāo)對比

根據(jù)圖4啟動(dòng)時(shí)間指標(biāo)對比實(shí)驗(yàn)結(jié)果，從整體啟動(dòng)時(shí)間上看，本文算法在多處理任務(wù)調(diào)度的任務(wù)程序啟動(dòng)時(shí)間上，相對于選取的SGM算法、Heuristic算法以及Block算法分別降低4.3%-13.7%，4.6%-13.9%和12.5%-35.4%。從上述9種測試任務(wù)實(shí)驗(yàn)結(jié)果對比數(shù)據(jù)上看，在Histogram等相對簡單的測試任務(wù)上，本文算法相對于選取的SGM以及Heuristic兩種對比任務(wù)調(diào)度方案的啟動(dòng)時(shí)間性能提升幅度相對有限，僅約3.6%-5.9%，但是相對于選取的MatricMult、imgsmth等計(jì)算較為復(fù)雜的對比任務(wù)調(diào)度算法，其性能提升幅度相對更為明顯，所提算法具有更加優(yōu)異的性能表現(xiàn)。原因是這些任務(wù)程序具有更為復(fù)雜的計(jì)算流，可為本文算法提供更大的性能提升空間。

實(shí)驗(yàn)2：(執(zhí)行時(shí)間)該指標(biāo)主要測試所提算法的計(jì)算效率，對于多任務(wù)處理器任務(wù)調(diào)度算法，實(shí)時(shí)性指標(biāo)具有非常重要的實(shí)際應(yīng)用價(jià)值。圖5為選取的幾種對比算法在選取的實(shí)驗(yàn)仿真平臺(tái)上的執(zhí)行時(shí)間指標(biāo)實(shí)驗(yàn)結(jié)果對比情況。為了更清晰表征算法之間的實(shí)驗(yàn)結(jié)果差別，圖5數(shù)據(jù)為本文算法相對于對比算法在執(zhí)行時(shí)間上降低的幅度比例。

圖5 執(zhí)行時(shí)間指標(biāo)對比

根據(jù)圖5執(zhí)行時(shí)間指標(biāo)對比結(jié)果，本文算法在測試平臺(tái)上的執(zhí)行時(shí)間指標(biāo)要分別比選取的SGM算法、Heuristic算法以及Block算法降低6.5%-41.7%，7.6%-20.7%和40.3%-69.5%。主要原因是本文算法相對于SGM算法、Heuristic算法以及Block算法，在任務(wù)可調(diào)度性方面進(jìn)行了優(yōu)化設(shè)計(jì)，數(shù)據(jù)冗余計(jì)算現(xiàn)象降低，可獲得更小的計(jì)算開銷支出。SGM調(diào)度算法僅對多處理器任務(wù)調(diào)度的計(jì)算負(fù)載問題進(jìn)行考慮；Block算法在處理不同迭代過程中的線程處理時(shí)，并未統(tǒng)籌流水化操作，導(dǎo)致算法調(diào)度計(jì)算過程的開銷較大；與Heuristic算法相比，本文算法在處理器協(xié)調(diào)調(diào)度上具有一定優(yōu)勢，執(zhí)行時(shí)間指標(biāo)更加優(yōu)異，算法具有更佳應(yīng)用價(jià)值。

實(shí)驗(yàn)3：(通信開銷)多處理器間任務(wù)調(diào)度主要面臨的問題是不同處理器間數(shù)據(jù)的頻繁通信問題，合理的處理器調(diào)度算法可降低整體處理器協(xié)調(diào)調(diào)度的通信量，進(jìn)而降低通信帶寬的負(fù)擔(dān)。圖6為選取的幾種對比算法在選取的實(shí)驗(yàn)仿真平臺(tái)上的通信開銷指標(biāo)實(shí)驗(yàn)結(jié)果對比，為了更清晰表征算法之間的實(shí)驗(yàn)結(jié)果差別，圖6數(shù)據(jù)為本文算法相對于對比算法在通信開銷上降低幅度比例。

圖6 通信開銷指標(biāo)對比

根據(jù)圖6通信開銷指標(biāo)對比實(shí)驗(yàn)結(jié)果可知，本文算法在測試平臺(tái)上的通信開銷指標(biāo)要分別比選取的SGM算法、Heuristic算法以及Block算法降低24.5%-79.7%，24.3%-77.8%，22.4%-75.3%。其中，在Gauss、FFT等任務(wù)程序調(diào)度上，本文算法相對于對比算法的通信開銷指標(biāo)性能提升幅度并不大，大約僅可實(shí)現(xiàn)10%左右的性能提升，主要是因?yàn)檫@些任務(wù)程序的操作本身就不復(fù)雜，所需要的通信開銷不大，因此算法提升幅度不是很明顯。而在aveMotion等指標(biāo)上，本文算法相對于選取的對比算法具有顯著的性能提升，體現(xiàn)了算法的有效性。

實(shí)驗(yàn)4：(存儲(chǔ)性能)存儲(chǔ)性能是驗(yàn)證所提算法性能優(yōu)勢的重要指標(biāo)，其對任務(wù)程序的流水性能具有直接限制。實(shí)驗(yàn)中，選取存儲(chǔ)容量的變化范圍是2 kB到64 kB，然后利用算法在64 kB存儲(chǔ)容量下的存儲(chǔ)性能指標(biāo)作為基準(zhǔn)，對實(shí)驗(yàn)結(jié)果進(jìn)行歸一化。圖7為選取的幾種對比算法在選取的實(shí)驗(yàn)仿真平臺(tái)上的存儲(chǔ)性能指標(biāo)實(shí)驗(yàn)結(jié)果對比，為了更清晰表征算法之間的實(shí)驗(yàn)結(jié)果差別，圖中所示數(shù)據(jù)為本文算法相對于對比算法在存儲(chǔ)性能上降低的幅度比例。

圖7 存儲(chǔ)性能指標(biāo)對比

根據(jù)圖7存儲(chǔ)性能指標(biāo)對比實(shí)驗(yàn)結(jié)果，隨著存儲(chǔ)容量的增加，選取的幾種對比算法的性能均呈現(xiàn)出單調(diào)遞增的趨勢。主要原因是，如果存儲(chǔ)容量有限，會(huì)導(dǎo)致算法執(zhí)行過程中，部分?jǐn)?shù)據(jù)存儲(chǔ)在片外存儲(chǔ)器上，片外存儲(chǔ)器相對于片內(nèi)存儲(chǔ)器在數(shù)據(jù)的存儲(chǔ)速度上要慢很多，這會(huì)導(dǎo)致算法數(shù)據(jù)傳輸存在較大的延遲現(xiàn)象，會(huì)直接影響任務(wù)程序的流水性能。此外，shortEnergy、DCT等任務(wù)程序隨著存儲(chǔ)容量的變化幅度較小，主要原因是這些程序需要的操作較為簡單，需要的數(shù)據(jù)存儲(chǔ)量本身不大，造成片外存儲(chǔ)器與片內(nèi)存儲(chǔ)器性能差別不是非常明顯，因此存儲(chǔ)容量增加對于算法的性能提升幅度相對更為有限。

4 結(jié)束語

本文針對混合臨界多處理器系統(tǒng)開發(fā)了可調(diào)度性測試方法，主要貢獻(xiàn)總結(jié)如下：①將已有可調(diào)度性測試推廣到混合臨界系統(tǒng)，得到了混合臨界多處理器系統(tǒng)非搶占調(diào)度的第一個(gè)可調(diào)度性測試；②對所提問題模型進(jìn)行可調(diào)度性測試擴(kuò)展，并提出了一個(gè)虛擬期限分配問題；③提出了一種基于系統(tǒng)級截止期縮減參數(shù)的最優(yōu)虛擬截止期分配策略。后續(xù)工作中，計(jì)劃針對混合臨界多處理器系統(tǒng)的非搶占式調(diào)度的其它現(xiàn)有可調(diào)度性測試，并為混合臨界多處理器系統(tǒng)開發(fā)更嚴(yán)格的可調(diào)度性測試。同時(shí)，在多處理器運(yùn)行過程中的協(xié)調(diào)調(diào)度算法研究上進(jìn)一步提升算法性能。