基于最優虛擬截止日期多處理器混合時序調度

高啟明，吳莉莉

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

0 引 言

隨著現代科學技術的進步，半導體工藝水平的提升可有效提高處理器計算性能約20倍，處理器生產廠家可在單個處理器中實現更強的計算性能[1,2]。但是對于個別大數據量運算情形，仍然需要用到多處理器協調配合。在多核處理器誕生以前，多處理器計算是最為常用的大數據處理方式[3]。

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

本文提出基于最優虛擬截止日期的多處理器混合時序調度算法，采用新的時序保證技術，以確保系統在兩個不同臨界值之間進行過渡，并將所提可調度性測試擴展到混合臨界系統，設計一種最優虛擬截止日期分配策略。

1 問題描述

1.1 系統模型

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

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

1.2 可調度條件

圖1 PS(τ)的工作運行機制

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

(10)

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

(11)

(12)

2 多處理器混合臨界最優分配

2.1 可調度性分析

(13)

(14)

圖2 無虛擬截止日期PS(τ)運行機制

(15)

(16)

(17)

2.2 最優虛擬截止期分配

(18)

算法1： 系統級參數的最優虛擬截止時間分配

輸入：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可調度；

(13) endif

(14) return不可調度；

(19)

(20)

(21)

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

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

3 實驗分析

3.1 實驗設置

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

圖3 實驗平臺

對比算法：①程序流圖模塊多處理器調度算法(SGM)；②啟發式表多處理器調度算法(Heuristic)；③基本塊多處理器調度算法(Block)。其中，SGM算法本質上是采用線性規劃策略的多處理器優化調度算法，主要優化目標是多處理器任務處理的均衡，對于數據通信開銷指標考慮較少；Heuristic算法采用的是一種表調度策略，考慮處理器承擔任務處理的優先級問題，是一種多處理優化調度的排隊策略。Block算法主要應用在多處理器的流式處理系統開發中，基本特征是對基本塊設定了不能重復調度的限制。

3.2 實驗對比

本實驗中選取的對比指標主要有4種：①啟動時間；②實際執行時間；③通信開銷；④存儲性能。實驗對比結果如下：

實驗1：(啟動時間)多處理任務調度中，啟動時間指標越低，表明多處理器任務協調調度性能越好，此時多處理器進行調度算法具有更高的線程執行效率。圖4為選取的幾種對比算法在實驗仿真平臺上的啟動時間指標實驗結果對比情況。為了更清晰表征算法之間的實驗結果差別，圖中所示數據為本文算法相對于對比算法在啟動時間上降低的幅度比例。

圖4 啟動時間指標對比

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

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

圖5 執行時間指標對比

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

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

圖6 通信開銷指標對比

根據圖6通信開銷指標對比實驗結果可知，本文算法在測試平臺上的通信開銷指標要分別比選取的SGM算法、Heuristic算法以及Block算法降低24.5%-79.7%，24.3%-77.8%，22.4%-75.3%。其中，在Gauss、FFT等任務程序調度上，本文算法相對于對比算法的通信開銷指標性能提升幅度并不大，大約僅可實現10%左右的性能提升，主要是因為這些任務程序的操作本身就不復雜，所需要的通信開銷不大，因此算法提升幅度不是很明顯。而在aveMotion等指標上，本文算法相對于選取的對比算法具有顯著的性能提升，體現了算法的有效性。

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

圖7 存儲性能指標對比

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

4 結束語

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