基于動態任務調度的STDS算法設計研究

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150413.1505.001.html

基于動態任務調度的STDS算法設計研究

劉正

(哈爾濱工程大學 計算機科學與技術學院,黑龍江 哈爾濱 150001)

摘要：任務調度是計算機多核處理器系統獲得高性能的關鍵，而現有的多核任務調度算法研究，大多側重于靜態調度下的算法優化和負載均衡，對動態調度及動態負載均衡研究較少。針對動態調度，并結合異構多核的特點，提出一種基于核負載均衡的動態任務調度算法STDS。算法通過合理設定調度粒度，降低調度頻率，從而減少調度消耗時間；根據異構多核處理器各核處理性能的差異，設置內核負載上下限值，控制內核負載保持在同一水平，以達到負載均衡效果。算法依據等待時間長短、任務間通信大小和內核負載輕重因素對任務進行實時調度，并可通過實時因子、負載因子等參數設置3種因素的影響比重，以滿足系統的不同需求。仿真實驗顯示，在內核數目較多的系統中，STDS算法更加高效，在保證任務處理速度的同時有較好負載均衡。

關鍵詞：動態任務調度；負載均衡；調度粒度；等待時間；異構多核系統

DOI:10.3969/j.issn.1673-4785.201503013

中圖分類號：TP316.4文獻標志碼：A

收稿日期：2015-03-09. 網絡出版日期：2015-04-13.

基金項目：國家自然科學基金資助項目(61003036)；中央高校基本科研業務費專項資金資助項目(HEUCF100606).

作者簡介：

中文引用格式：劉正. 基于動態任務調度的STDS算法設計研究[J]. 智能系統學報， 2015, 10(2): 324-332.

英文引用格式：LIU Zheng. Research on STDS algorithm designing based on dynamic task scheduling[J]. CAAI Transactions on Intelligent Systems, 2015, 10(2): 324-332.

Research on STDS algorithm designing based on dynamic task scheduling

LIU Zheng

(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)

Abstract：Efficient task scheduling is the key for multi-core systems to achieve high performance. However, most of the existing multi-core researches on task scheduling algorithms focus on algorithm optimization and load balancing under the static scheduling rather than dynamic scheduling and dynamic load balancing. Scalable task duplication based scheduling (STDS) is a new dynamic-balanced algorithm based on core load balancing. STDS was put forward specifically for dynamic scheduling and integrating the characteristics of heterogeneous multi-core. It shortens scheduling time by reasonably setting the scheduling granularity and reducing the frequency of scheduling. STDS sets the maximum and minimum ranges of the kernel load according to the different processing performance of each core of the heterogeneous multi-core processor， therefore controlling the core load at the same level and achieving the effect of load balance. The wait time of task and communications between tasks and kernel load will be considered together to pick up the most appropriate task during scheduling. The importance of each element can be adjusted by assigning another value to the real-time factor and load factor enabling it to adapt to various environment. The experimental results verified that the STDS algorithm is more efficient in the system with the most kernels. It also keeps a good load balance while maintaining the speed of task execution processing.

Keywords：dynamic task scheduling; load balancing; scheduling granularity; waiting time; heterogeneous multi-core system

通信作者：劉正.E-mail：liuzheng528@hrbeu.edu.cn.

動態任務調度可以根據運行的時情況動態地將任務分配到各個內核上，由于需要實時地收集、存儲并分析狀態信息，動態調度的實施有一定的系統開銷，但這種開銷和付出通常是有回報的[1]。多核處理器系統中的任務調度已被證明是NP問題[2]，除個別特殊情況外，目前尚未有一種多項式時間算法可以求得最優解，只能得到一個最大限度接近最優解的解，因此改進算法的效率并構建任務調度實現機制成為研究重點，很多學者在這方面做了大量工作。

比較經典的調度算法有Min-Min[3]、Max-Min[4]、MCT[5]、MET[6]算法。Min-Min算法實現簡單、執行速度快。算法首先通過計算待調度任務在任一可用內核上的最早完成時間，取最小值作為該任務的最早完成時間，然后選取所有待調度任務中最早完成時間最小的一個任務進行調度。缺點是如果任務集中存在過多的執行時間比較小的任務，那么大任務將無法得到及時的執行。Max-Min算法同Min-Min算法類似，同樣需要計算每一任務的最早完成時間，不同的是Max-Min算法首先調度最早完成時間最大的任務，將其分配到對應的內核上。缺點是小任務等待時間過長、影響執行效率，也可能造成負載不均衡。MCT算法以任務完成時間最早為目標進行調度，每次將到達的任務分配到完成時間最早的內核上，但該算法忽略了任務的執行時間，可能將任務分配到執行時間較長的處理機上運行。MET算法以任務執行時間最短為目標進行調度，每次將到達的任務分配到執行時間最短的內核上，其缺點是易造成較強內核負載過多任務，導致內核間負載不均衡，降低系統性能。

清華大學的石威等[7]提出了一種相關任務圖的均衡動態關鍵路徑調度算法，采用動態關鍵路徑技術并均衡考慮關鍵路徑結點和非關鍵路徑結點，優先調度對相關任務圖調度長度影響最大的就緒結點，從而極大地縮短任務圖的調度長度。李仁發[8]對多核處理器系統任務調度研究進展進行討論，對不同模型下的多核系統任務調度算法相關研究進行了分析總結，從調度算法分析和調度實現框架2個方面探討了近年來多核任務調度的國內外研究進展情況。文中對任務分配、任務模型優化、調度器實現和任務遷移等當前亟待解決的問題，進行了深入探討，并指出了下一步主要的研究方向，為多核處理器相關研究提供參考。吉林大學的耿曉中提出了一種動態負載均衡模型[9]，將影響多核處理器負載均衡的因素分為5類：多核系統的負載均衡環境、用戶提交的任務屬性、系統的負載評價、系統所采用的調度策略以及系統的調度評價指標，為多核動態調度的負載平衡研究提供了理論指導；徐雨明等[10]將遺傳算法和啟發式方法有機地結合，根據染色體雙螺旋結構模型，提出了一種異構系統中依賴任務調度的雙螺旋結構遺傳算法。該算法首先采用啟發式方法，產生較佳的任務調度優先隊列，然后模仿堿基互補配對方法，提高算法的有效性和收斂速度；Vinay等[11]提出一種多核處理器動態任務調度策略，調度思想是依據任務的執行時間和依賴此任務的任務數量確定此任務優先級，當某個內核空閑時，選擇一個優先級最高且為就緒狀態的任務分配給該內核。此策略結構簡潔，算法復雜度低，但每個內核上只分配一個任務，且調度時需要對數據段加鎖以保證數據一致性，當內核數目較多時，經常發生多個內核同時申請分配任務的情況，所以不可避免出現內核空閑等待現象，不能完全發揮多核處理器優勢。

文中對文獻[11]的動態調度策略進行改進，克服內核可能空閑等待問題，并綜合負載均衡策略，提出多核動態任務調度算法(shared task data structure，STDS)。算法通過分析任務等待時間、任務間通信開銷和內核負載等因素，確定任務優先級，并據此分配任務。通過仿真實驗驗證，該算法在保證任務處理速度的同時有較好負載均衡，比較適用于內核數目較多的系統。

1模型

在多核任務調度研究中，為便于研究理解，通常用抽象的任務調度模型描述任務調度系統。多核任務調度模型通常由系統模型、任務模型、任務調度算法和任務映射圖組成。

1.1系統模型

系統模型是指依據系統硬件環境構建出可進行數學量化分析的數學模型，文中用二元組SM(system model)={P, Rate}表示，其中：SM表示系統模型；P={P0,P1,…,Pk,…, Pm-1}為處理器內核集合，Pk表示第k個處理器內核，|P|=m為處理器中內核的總個數。多核處理器根據內核在執行能力方面的差別可劃分為同構和異構2類，同構多核處理器通過增加同種處理器內核數量提升性能，而異構多核處理器通過集成不同計算能力的內核來優化處理器，實現多核處理器性能發揮的最大化，在能耗、面積等方面有著巨大的優勢[12]。文中以有限數目的異構多核處理器為研究基礎，集合P中處理器內核速度并不完全相同，用spk表示內核Pk的處理速度。

Rate={…,Rates,t,…}表示處理器內核間數據傳輸速率集合，元素Rates,t表示處理器內核Ps與Pt間的數據傳輸速率。

核間互連技術是多核處理器設計的關鍵，當前多核處理器核間互連方式主要有總線共享、交叉開關互連和片上網絡3種。文中對多核處理器核間互連技術不做具體研究，默認任意2個處理器內核間均存在數據通信通路，即對于任意的s(0≤s≤m-1)和t(0≤s≤m-1)，Rates,t≠0。為簡化環境模型，假設同一時刻，內核Pk只能與一個內核進行通信。

1.2任務模型

任務模型是描述任務屬性和特征的一種數學模型，它包含任務調度過程中的狀態和控制等信息。STDS算法構建了一個可以共享訪問的TDS(task data structure)結構，TDS由若干數據項構成，每個數據項唯一對應一個任務，數據項記錄該任務的相關信息，其定義如圖1所示。

圖1數據項定義
Fig.1Definition of data element

圖1中，Ti為任務編號，唯一標識任務；Tis為任務狀態，STDS算法將任務狀態分為等待、就緒和已執行3種，用1表示等待，0表示就緒，2表示已執行。如果任務處于就緒態，說明已分配除CPU外所有必要資源，允許調度程序將其調度分配；等待狀態的任務因需要等待某一事件的發生，比如等待其前驅任務執行完畢，而暫不能被調度程序調度；任務執行完畢后的狀態為已執行狀態，此狀態下，如果其他所有任務都不再需要此任務信息，就將其對應的數據項刪除，以節省內存空間；

Tid={…,Tj,…}：依賴任務集合，也叫前驅任務集合，任務Ti必須在其依賴任務全部執行完成之后執行；

Tidn：依賴任務剩余數量，表示任務Ti的依賴任務集合中尚未執行完畢的任務數量，即依賴任務集合Tid中，還有多少依賴任務沒有執行完成。其初值是集合Tid的長度，即Tidn=|Tid|，每當一個依賴任務執行完畢，Tidn值減1，直到Tidn=0，而Tidn=0是Tis=0(就緒)的必要條件；

Tidd={…,Datai,j,…}：與依賴任務通信數據量集合，記錄任務Ti與其依賴任務Tid通信的數據大小，Datai,j表示任務Ti與依賴任務Tj通信的數據大小，如果任務Ti、Tj分別分配到內核Ps、Pt上，則任務Ti與Tj的通信時間就可用Datai,j/Rates,t表示；

Tia={…,Tj,…}：依賴任務Ti的任務集合，也叫后繼任務集合，只有Ti執行完成后，其后繼任務才有機會變為就緒狀態，從而調度執行。當Ti完成后，需要將集合Tia中所有任務的Tidn屬性值減一；

Tip：任務優先級，表示任務優先調度程度，任務優先級越高，被優先調度的可能性越大。任務優先級取決于任務就緒時間、通信開銷以及內核負載等因素。系統運行過程中，就緒時間和內核負載等是動態變化的，所以任務優先級不是某一定值，它隨著系統狀態的改變而動態變化；

Tit：任務就緒時間，即任務滿足調度條件變為就緒狀態的時間。如果用t表示現在時間，則等待時間就是(t- Tit)，為避免存在長時間未能調度執行的就緒任務，算法應優先調度等待時間長的任務；

Tic：任務映射，表示任務和內核的對應關系，即任務Ti分配到哪個內核上執行。STDS算法用-1表示任務尚未分配內核資源，用整數0,1,…,m-1分別表示在內核P0, P1,…, Pm-1上執行。

1.3調度器模型

文中設計的調度器模型采用集中式調度模式，如圖2所示。圖中指定了一個內核專門執行調度程序，稱為中心調度器，中心調度器負責收集調度信息和執行任務調度，其余內核只負責執行任務。

圖2　調度器模型 Fig.2　Scheduler model

建立維護等待隊列和就緒隊列2個全局任務列表，調度器在任務調度時只需要檢索就緒任務隊列，節省了調度時間開銷，等待隊列中的任務滿足就緒條件時可以變為就緒態等待調度。每個內核都有一個可以緩存一定數目任務的局部隊列，當內核需要調度任務時直接從緩存中獲取；而當局部隊列中的任務過少時開始請求調度器為局部隊列分配任務，降低了調度器調度頻率，而且中心調度器與各內核可以并行地運行。全局調度隊列和局部調度隊列結合的方式在整體上是全局隊列方式，與集中式調度策略配合使用易于實現負載均衡；在底層實現上是局部隊列方式，降低了系統對隊列共享性要求，克服了集中式調度模式的性能瓶頸問題。

文中通過重載和輕載閥值確定調度時機，當內核處于輕載狀態時請求任務調度，處于重載時不允許再向內核分配任務，這種策略在保證一定負載均衡效果的同時提高了內核執行效率。

2任務優先級

將任務分配到最合適的內核上是任務調度的核心問題，而任務優先級計算是任務分配的關鍵，任務優先級表明任務被優先調度程度。在多核環境下，各內核的狀態不盡相同，STDS算法為評價任務與內核的適合程度，首先計算任務相對于一個確定內核的優先級Tipk，然后取其在所有內核上的最大值作為任務優先級Tip，表示為式(1)：

(1)

式中：m為內核數量，Tipk表示任務Ti相對于內核Pk的優先級。STDS算法在計算Tipk時，綜合考慮等待時間、任務間通信開銷和內核負載狀態因素。等待時間為當前時間與就緒時間的差值，任務間通信開銷是任務Ti與其所有依賴任務Tid通信時間之和，而內核負載狀態用于實現內核負載均衡。

多核處理器的負載均衡要求避免出現一個或多個內核負載較低甚至空閑，而其他內核處于高負載狀態的情況，從而充分發揮多核處理器優勢。STDS算法使用任務隊列長度|TLk|作為內核負載指標，內核的任務隊列越長，說明分配的任務越多，所以其負載越大。

為實現負載均衡引入調度粒度，內核Pk的調度粒度定義為一次調度過程中為Pk分配的任務數量，這里的一次調度過程是指一個內核請求調度，調度算法為其分配任務的過程，在實際運行中，可能出現調度算法一次性處理多個內核調度請求，調度的任務數量等于為每個內核分配的任務數量之和。粒度大小要根據系統模型而定，調度粒度過大，不能充分發揮動態調度優勢，而粒度過小，會引發頻繁調度，增大調度程序運行時間開銷，降低處理器效率。對于異構多核處理器，調度粒度與內核處理速度是正比關系。STDS算法將調度粒度定義為式(2)：

lk=l·spk，0≤k≤m-1

(2)

式中：lk表示內核Pk的調度粒度，l表示粒度因子，spk表示內核Pk的處理速度。對于一個實際的處理器系統，內核速度是確定的已知量，調度粒度lk的大小，可以通過粒度因子l調節，粒度因子與具體的運行狀況有關，它起到將內核的計算速度轉換為內核調度任務數量功能。

STDS算法通過限制內核任務隊列長度實現負載均衡，為有效發揮調度隊列作用，算法引入2個負載因子，分別確定隊列的上限和下限，具體定義如式(3)～(5)：

(3)

(4)

(5)

0≤k≤m-1

上述闡述了計算任務優先級時的內核隊列上下限問題，式(6)～(10)則是對任務優先級計算時的等待時間、通信開銷和內核負載均衡因素的描述。STDS算法在計算任務優先級時，綜合考慮等待時間、通信開銷和內核負載均衡因素，式(1)中Tipk表示任務Ti分配到內核Pk適合程度，其計算公式為：

(6)

(7)

(8)

(9)

(10)

綜上所述，任務優先級值的計算，是對等待時間、通信開銷和內核負載3個因素綜合考量的過程，其結果可能不是單一因素中最優的，但一定是綜合考慮全部3種因素后最優的選擇。

3算法實現

在上節中詳細介紹了任務優先級的計算，本節將介紹STDS算法的具體實現過程。

為了使任務調度算法得到較理想的實現，STDS算法的研究基于以下假設條件：

1)假設任務間的依賴關系固定不變；

2)同一內核上任務間通信開銷忽略不計；

3)任務不可搶占。

系統運行時首先將任務初始化，構造TDS，由于算法中大多計算只針對就緒任務，特別是任務分配時，所以為了節約計算開銷，算法初始化時會生成一個就緒任務列表和一個等待任務列表。當內核Pk任務隊列長度|Tlk|≤lk_min時，就向調度程序請求分配任務，調度程序遍歷就緒列表，計算相對于內核Pk的優先級，選擇優先級Tip值最大的任務分配到Pk上，重復執行此過程，直到內核Pk任務隊列長度|Tlk|≥lk。若同時有多個內核請求任務分配，調度程序分配任務時需要響應這幾個內核的請求，計算優先級時需要計算相對于這幾個內核的優先級，然后取最大值作為最終優先級，調度程序選擇優先級最大的任務分配到對應的內核。

值得注意的是在動態調度過程中，為了保證數據實時有效，STDS算法在每個任務分配完成或執行結束時對數據進行更新。當任務Ti分配給內核Pk后，需要將任務Ti對應數據項中的Tic置為k，此時內核Pk負載也相應改變；當任務Ti執行完成時，如果任務Tj依賴任務Ti，需要將任務Tj的Tidn值減1，若減1后Tidn=0，將任務Tj狀態置為就緒態并從等待列表移到就緒列表。為了降低復雜度節省時間，STDS算法采用先記錄再批量執行的方式，即在任務執行期間暫時將完成的任務編號記錄，在任務調度程序執行時批量更新數據；如果任務Ti執行完畢且所有依賴Ti的任務也執行完畢，就將任務Ti的信息從TDS中刪除，從而釋放內存節省空間。

如果就緒列表為空，調度程序不會響應內核的任務分配請求，當就緒列表和等待列表全為空時，說明任務全部執行完畢，調度結束。

STDS算法實現步驟：

Procedure STDS(SM,TDS,PList,TLexe)/*SM表示處理器內核系統；TDS是所有任務信息；PList是需要分配任務的內核列表, TLexe是執行完畢但還未進行信息更新的任務列表*/

1){for eachTi∈TLexe

2) {Tia[]←Ti;

3)for eachTj∈Tia

4)Tjdn←Tjdn-1; /*執行完畢的任務信息更新，將其后繼任務的依賴任務數量減一*/

}/* end for eachTi∈TLexe*/

5)TLready[]←TDS;/*就緒任務放入就緒隊列*/

6) for eachTi∈TLready

7){for eachPk∈PList

8)Cik←式(10); /*任務Ti若在內核Pk上與前驅任務的通信開銷，只需計算一次 */

}/* end for eachTi∈TLready*/

9)while(TLready≠? andPList≠?)

10){for each Ti∈TLready

11){PWi←式(7);

12) for each Pk∈PList

13) {PCik←式(8);

14)Lk←式(9);

15)Tipk←式(6);

}/* end for eachPk∈PList*/

16) Tip=max{Tipk};

}/* end for eachTi∈TLready*/

17)Tj←max{ Tip};/*選出最大優先級的任務，設Tj就是選出的任務，且其對應內核為Ps，即Tjp= Tjps*/

18)TLs←TLs+{Tj};/*任務Tj分配給內核Ps*/

19) TLready←TLready-{Tj};

20) Tjc=s；

21) if |TLs|=ls_maxthenPList←PList-{Ps};

/*內核Ps分配任務結束*/

22)if TLready≠? then return; /*沒有就緒任務*/

}/* end for while*/

}

其中1)～5)是算法對執行完畢但未進行數據更新的任務進行處理，將其后繼任務的Tidn屬性值減1，且減為0時放入就緒隊列等待調度。算法中有兩重循環，外層循環遍歷TLexe列表，內層循環遍歷后繼任務列表，所以時間復雜度為O(n)×O(logn)=O(nlogn)。而任務更新發生在每次任務分配時，次數大約為任務數量與調度粒子比值即n/l，而在具體應用環境中調度粒子為定值，所以數據更新總時間復雜度為O(n2logn)。6～20是進行任務分配，其中優先級計算是關鍵。計算每個任務相對于每個請求分配任務內核的優先級，其時間復雜度為O(mn)，其中m是內核數量，n是就緒任務數量。而算法最終需要將任務全部分配完成，所以任務分配的總時間復雜度為O(mn)×O(n)=O(mn2)。因此STDS算法的時間復雜度為O(n2logn)+O(mn2)= Max(O(n2logn),O(mn2))，而經典Min-Min算法的時間復雜度為O(mn2)[13]，兩者處于同一量級。

4實驗

任務調度目前還沒有形成統一規范的性能測試方案[14]，大多數對調度算法的研究都是采用隨機DAG圖生成器來生成各種不同形狀的DAG圖集合作為任務調度算法的測試用例。

文中借助TGFF工具生成隨機任務圖，并以此完成TDS初始化，用內核上任務長度表示負載情況，通過任務總執行時間和負載均衡等衡量算法優劣，在Simics[15]模擬平臺上對本文算法性能進行模擬實驗測試。為了測試本文提出的算法對并行任務調度問題的求解效果，采用下面2類實驗來驗證。

4.1參數對調度算法的影響

STDS算法用到的參數有：粒度因子l、負載因子δ1和δ2、實時性因子β。l的大小決定一次調度過程分配的任務數量，進而決定調度頻度；l、δ1和δ2共同影響著負載均衡；β主要調節算法實時性。下面分別通過實驗數據說明參數l、δ1、δ2、β對STDS算法性能的影響。

1)調度粒度對STDS算法調度頻度和負載影響

通過TGFF工具分別生成具有3000個任務和5000個任務的隨機任務圖，測試這2類任務在不同調度粒度下的調度效果，為屏蔽其他因素影響，設置參數β=0，lk_min=lk(1-δ2)=2，結果如圖3所示。由圖3可以看出，調度次數隨著調度粒度增大而減小，進而降低STDS調度算法消耗時間；粒度較小時調度次數減少幅度較大，而在較大粒度情況下效果較弱。

圖3　調度粒度對調度次數影響 Fig.3　Change of scheduling times in the situation of different scheduling granularities

雖然較大粒度下節省調度時間，但并不是l取最大值時STDS算法性能最優，l取極大值時，調度頻度最小，但此時對于內核Pk的請求，STDS算法會將全部就緒任務分配給Pk，從而造成各內核上負載差別較大。表1說明了粒度對負載均衡的影響，在調度過程中對內核負載進行采樣，每次采樣時，用此時內核上任務隊列長度占所有內核任務隊列長度之和的比例，評價負載均衡效果。表1中P0、P1、P2的處理速度為1GHz，P3的處理速度為2GHz，據STDS算法設定，P3的負載應為P0、P1、P2的2倍。從表1可以看出，負載均衡效果隨調度粒度的增大而降低。

表1調度粒度對負載均衡影響

Table1Changeofloadbalancinginthesituationofdifferentschedulinggranularities

調度粒度P0/%P1/%P2/%P3/%219.6120.4420.3739.58820.1119.8021.1938.901422.5119.1320.9137.45

2)負載因子對算法性能影響

δ1是負載上限因子，δ2是負載下限因子，δ1和δ2滿足公式(5)約束條件：δ1+δ2=1，當δ2確定時，δ1的值也是確定的。δ2的大小決定了內核Pk調度隊列長度下限lk_min的大小，lk_min較大時，內核Pk的負載也相對較大，然而此時會引發另一個問題，雖然內核Pk負載達到下限lk_min并請求分配任務，但此刻Pk依然有較多任務待執行，當就緒任務不是很充足時，容易發生STDS算法頻繁響應分配請求。圖4是在δ2取不同值時的調度統計結果，固定調度粒度l=6，可以看出，調度次數隨著δ2的增大而增大。

圖4　負載因子對調度次數影響 Fig.4　Change of scheduling times in the situation of different load factor

3)實時性因子對算法性能影響

STDS算法設立實時性因子主要是解決就緒任務長時間得不到內核資源的“饑餓”現象。由式(6)可知，任務優先級是任務等待時間、任務間通信和內核負載3種因素共同決定的，通過實時性因子可以調節等待時間因素的重要程度，實時性因子反映了系統對等待時間的容忍程度。表2是在β取不同值時對STDS算法平均等待時間和總運行時間的影響，其中AWT(average of wait time)表示平均等待時間，此時設置l=6，δ1=1/3，δ2=2/3以消除其他因素影響。由表2可以看出，隨著β值的增大，等待時間最大的100個任務的平均等待時間減小，而全部任務的平均等待時間的趨勢不能確定，因為此時通信開銷不是最小的，所以算法總執行時間增大，從而會造成某些任務的等待時間增大。在β取較大值(>2.0)時，STDS算法性能基本不再變化，此時STDS算法近似于先來先服務(FIFO)算法。所以β應取滿足系統對實時性要求前提下的最小值。

表2實時性因子對算法性能影響

Table 2Change of performance in the situation of different real-time factors

βAWTofTop100/msAWTofAll/ms運行時間/ms07603.11689.446325620.46752.751084.344342500.86179.30901.595349221.04838.11882.158351252.04517.32911.572357565.04497.84926.48535998

綜上所述，參數會對算法的調度時間、調度次數、負載均衡效果以及實時性產生影響，對于不同應用環境，應適當調整參數大小，在滿足系統要求前提下充分發揮算法性能。對于實時性要求不嚴格系統，可以減少實時因子大小，降低總調度時間；對于規模較大系統，應增大調度粒度在減小調度次數，盡量減少調度器的調度壓力，適當增大負載下限因子，保證在調度器調度不及時情況下，內核依然有充足的任務可以執行；反之亦然。本文沒有明確參數值的具體大小，此工作需要通過大量具體的實際實驗完成。

4.2算法對比實驗

為有效評價STDS算法性能，將其與Min-Min算法和文獻[11]的Vinay算法進行比較。對于每個固定的內核數，通過TGFF工具隨機產生10組5000節點的DAG圖，記錄其調度執行時間，然后求出其平均值。由于內核數目改變，系統模型發生變化，所以實驗時適當調節STDS算法參數，以充分發揮算法性能，表3是不同內核數目時STDS算法參數取值，內核數目較多時，增大調度粒度l，雖然負載均衡效果有所下降，但降低了調度次數。圖5是STDS算法、Min-Min和Vinay算法在不同內核數目下執行時間的比較結果。

由圖5可以看出在內核數目較少時，Vinay算法比較高效，這是因為Vinay算法實現簡單，算法復雜度低，每個內核分配一個任務，不需要考慮負載均衡等問題。隨著內核數目增加，STDS算法優勢逐步體現，這是因為Vinay算法一次調度分配一個任務，調度較頻繁，內核數目較多時，會發生多個內核同時請求調度，但同一時刻只有一個內核可以調度成功，其他內核不得不等待。STDS算法為每個內核設置一個任務隊列，每次調度會分配若干個任務，這樣雖然增大了算法復雜度，但減少了調度次數且最大限度避免了內核等待現象，所以總時間較小。STDS算法比較適合內核數目較多的系統，但值得注意的是在內核數目較多的系統中，對任務量的要求也較大，否則難以充分發揮多核系統和STDS算法性能。

表3不同內核數目時的參數值

Table 3Value of parameters in the situation of different quantity of cores

內核數目lδ1δ2β231/32/30.1441/21/20.1861/32/30.11661/21/20.132103/107/100.1

圖5　STDS、Min-Min、Vinay算法執行時間 Fig.5　Comparison of running time among STDS，Min-Min andVinay

STDS算法復雜度與Min-Min算法相當，但調度運行時間比Min-Min算法稍長，原因是Min-Min算法將運行時間作為其唯一考慮因素，優先選取最早完成時間最小的任務進行調度。但Min-Min算法中執行時間較長的任務得不到及時執行，圖6是STDS算法與Min-Min算法等待時間的對比結果。

圖6　STDS算法與Min-Min算法等待時間對 Fig.6　Comparison of waiting time between STDS and Min-Min

可以看出STDS算法中任務最大等待時間明顯小于Min-Min算法。由此也可以得出STDS算法的另一大優勢，就是可以通過調整參數取值，從而適應不同的系統要求。為了排除偶然因素影響，本文通過生成另外9組不同結構的3000 個節點與5000個節點的DAG圖，進行相同的實驗，實驗結果與上述描述吻合。

5結束語

文中研究了異構多核動態任務調度算法，結合設計的調度模型，提出了動態任務調度STDS算法。該算法分析了調度粒度對任務調度的影響可以根據當前內核負載和任務狀態調整任務優先級，從而將高優先級的任務合理高效地分配到內核，并通過限定內核任務隊列的上下限值達到負載均衡的目的。通過引入實時性因子使任務總能及時得到執行處理，減少了過長的等待時間。實驗表明，STDS算法在內核較大情況下效率較高，且能夠保持負載均衡。

參考文獻:

[1]GENG X, XU G, ZHANG Y. Dynamic load balancing scheduling model based on multi-core processor[C]//2010 Fifth International Conference on Frontier of Computer Science and Technology (FCST). [S.l.]，2010: 398-403.

[2]GRAY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. New York: W H Freeman and Company, 1979： 92-115.

[3]JIN H, CHEN H, CHEN J, et al. Real-time strategy and practice in service grid[C]//Proceedings of the 28th Annual International on Computer Software and Applications Conference, 2004. 2004: 161-166.

[4]HE X S, SUN X H,VON LASZEWSKI G . A QoS guided scheduling algorithm for grid computing[J]. Journal of Computer Science and Technology, 2003,18(4): 442-451.

[5]FREUND R F, GHERRITY M, AMBROSIUS S, et al. Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet[C]//Proceedings on Heterogeneous Computing Workshop. , 1998: 184-199.

[6]ARMSTRONG R, HENSGEN D, KIDD T. The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions[C]//Proceedings on Heterogeneous Computing Workshop. , 1998: 79-87.

[7]石威, 鄭緯民. 相關任務圖的均衡動態關鍵路徑調度算法[J]. 計算機學報, 2001, 24(9): 991-997.

SHI Wei, ZHENG Weimin. The balanced dynamic critical path scheduling algorithm of dependent task graph[J]. Chinese Journal of Computers, 2001, 24(9): 991-997.

[8]李仁發, 劉彥, 徐成. 多處理器片上系統任務調度研究進展評述[J]. 計算機研究與發展, 2008, 45(9): 1620-1629.

LI Renfa, LIU Yan, XU Cheng. A survey of task scheduling research progress on multiprocessor system-on-chip[J]. Journal of Computer Research and Development, 2008, 45(9): 1620-1629.

[9]耿曉中. 基于多核分布式環境下的任務調度關鍵技術研究[D]. 吉林: 吉林大學, 2013： .

GENG Xiaozhong. Research on key techniques of task scheduling based on multi-core distributed environment[D]. Jilin: Jilin University, 2013.

[10]徐雨明，李肯立. 異構系統中DAG任務調度的雙螺旋結構遺傳算法[J]. 計算機研究與發展，2014,51(6): 1240-1252.

XU Yuming, LI Kenli. A structure genetic algorithm for task scheduling double-helix on heterogeneous computing systems [J]. Journal of Computer Research and Development, 2014, 51(6): 1240-1252.

[11]VAIDYA V G, RANADIVE P, SAH S. Dynamic scheduler for multi-core systems[C]// International Conference on Software Technology and Engineering, 2010 2nd. Puerto Rico: IEEE, 2010, 1: V1-13-V1-16.

[12]陳銳忠,齊德昱,林偉偉.一種面向非對稱多核處理器的綜合性調度算法. 軟件學報, 2013, 24(2): 34-3357.

CHEN Ruozhong, QI Deyu, LIN Weiwei. Comprehensive scheduling algorithm for asymmetric multi-core processors[J]. Journal of Software， 2013, 24(2): 34-3357.

[12]鄧曉衡, 盧錫城, 王懷民. iVCE中基于可信評價的資源調度研究[J]. 計算機學報, 2007, 30: 1750-1762.

DENG Xiaoheng, LU Xicheng, WANG Huaimin. Study on trust evaluation based resource scheduling in iVCE[J]. Chinese Journal of Computers, 2007, 30: 1750-1762.

[12]KWOK Y K, AHMAD I. Benchmarking the task graph scheduling algorithms[C]//Parallel Processing Symposium, 1998. IPPS/SPDP 1998. Proceedings of the First Merged International... and Symposium on Parallel and Distributed Processing 1998. IEEE, 1998: 531-537.

[12]FORSGREN D, ESKILSON J, CHRISTENSSON M, et al. Simics:a full system simulation platform[J]. IEEE Computer, 2002, 35(2): 50-58.

劉正, 男，1983年生，講師，博士研究生，主要研究方向為性能優化、信息安全與智能信息處理。