基于動態(tài)任務調度的STDS算法設計研究

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

基于動態(tài)任務調度的STDS算法設計研究

劉正

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

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

關鍵詞：動態(tài)任務調度；負載均衡；調度粒度；等待時間；異構多核系統(tǒng)

DOI:10.3969/j.issn.1673-4785.201503013

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

收稿日期：2015-03-09. 網(wǎng)絡出版日期：2015-04-13.

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

作者簡介：

中文引用格式：劉正. 基于動態(tài)任務調度的STDS算法設計研究[J]. 智能系統(tǒng)學報， 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.

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

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

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

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

1模型

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

1.1系統(tǒng)模型

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

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

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

1.2任務模型

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

圖1數(shù)據(jù)項定義
Fig.1Definition of data element

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

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

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

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

Tia={…,Tj,…}：依賴任務Ti的任務集合，也叫后繼任務集合，只有Ti執(zhí)行完成后，其后繼任務才有機會變?yōu)榫途w狀態(tài)，從而調度執(zhí)行。當Ti完成后，需要將集合Tia中所有任務的Tidn屬性值減一；

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

Tit：任務就緒時間，即任務滿足調度條件變?yōu)榫途w狀態(tài)的時間。如果用t表示現(xiàn)在時間，則等待時間就是(t- Tit)，為避免存在長時間未能調度執(zhí)行的就緒任務，算法應優(yōu)先調度等待時間長的任務；

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

1.3調度器模型

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

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

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

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

2任務優(yōu)先級

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

(1)

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

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

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

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

(2)

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

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

(3)

(4)

(5)

0≤k≤m-1

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

(6)

(7)

(8)

(9)

(10)

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

3算法實現(xiàn)

在上節(jié)中詳細介紹了任務優(yōu)先級的計算，本節(jié)將介紹STDS算法的具體實現(xiàn)過程。

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

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

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

3)任務不可搶占。

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

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

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

STDS算法實現(xiàn)步驟：

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

1){for eachTi∈TLexe

2) {Tia[]←Ti;

3)for eachTj∈Tia

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

}/* end for eachTi∈TLexe*/

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

6) for eachTi∈TLready

7){for eachPk∈PList

8)Cik←式(10); /*任務Ti若在內(nèi)核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};/*選出最大優(yōu)先級的任務，設Tj就是選出的任務，且其對應內(nèi)核為Ps，即Tjp= Tjps*/

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

19) TLready←TLready-{Tj};

20) Tjc=s；

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

/*內(nèi)核Ps分配任務結束*/

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

}/* end for while*/

}

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

4實驗

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

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

4.1參數(shù)對調度算法的影響

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

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

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

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

雖然較大粒度下節(jié)省調度時間，但并不是l取最大值時STDS算法性能最優(yōu)，l取極大值時，調度頻度最小，但此時對于內(nèi)核Pk的請求，STDS算法會將全部就緒任務分配給Pk，從而造成各內(nèi)核上負載差別較大。表1說明了粒度對負載均衡的影響，在調度過程中對內(nèi)核負載進行采樣，每次采樣時，用此時內(nèi)核上任務隊列長度占所有內(nèi)核任務隊列長度之和的比例，評價負載均衡效果。表1中P0、P1、P2的處理速度為1GHz，P3的處理速度為2GHz，據(jù)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的大小決定了內(nèi)核Pk調度隊列長度下限lk_min的大小，lk_min較大時，內(nèi)核Pk的負載也相對較大，然而此時會引發(fā)另一個問題，雖然內(nèi)核Pk負載達到下限lk_min并請求分配任務，但此刻Pk依然有較多任務待執(zhí)行，當就緒任務不是很充足時，容易發(fā)生STDS算法頻繁響應分配請求。圖4是在δ2取不同值時的調度統(tǒng)計結果，固定調度粒度l=6，可以看出，調度次數(shù)隨著δ2的增大而增大。

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

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

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

表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

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

4.2算法對比實驗

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

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

表3不同內(nèi)核數(shù)目時的參數(shù)值

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

內(nèi)核數(shù)目lδ1δ2β231/32/30.1441/21/20.1861/32/30.11661/21/20.132103/107/100.1

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

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

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

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

5結束語

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

參考文獻:

[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]石威, 鄭緯民. 相關任務圖的均衡動態(tài)關鍵路徑調度算法[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]李仁發(fā), 劉彥, 徐成. 多處理器片上系統(tǒng)任務調度研究進展評述[J]. 計算機研究與發(fā)展, 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]耿曉中. 基于多核分布式環(huán)境下的任務調度關鍵技術研究[D]. 吉林: 吉林大學, 2013： .

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

[10]徐雨明，李肯立. 異構系統(tǒng)中DAG任務調度的雙螺旋結構遺傳算法[J]. 計算機研究與發(fā)展，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年生，講師，博士研究生，主要研究方向為性能優(yōu)化、信息安全與智能信息處理。