基于動態(tài)任務(wù)調(diào)度的STDS算法設(shè)計研究

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

基于動態(tài)任務(wù)調(diào)度的STDS算法設(shè)計研究

劉正

(哈爾濱工程大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001)

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

關(guān)鍵詞：動態(tài)任務(wù)調(diào)度；負(fù)載均衡；調(diào)度粒度；等待時間；異構(gòu)多核系統(tǒng)

DOI:10.3969/j.issn.1673-4785.201503013

中圖分類號：TP316.4文獻(xiàn)標(biāo)志碼：A

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

基金項目：國家自然科學(xué)基金資助項目(61003036)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項資金資助項目(HEUCF100606).

作者簡介：

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

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

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

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

1模型

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

1.1系統(tǒng)模型

系統(tǒng)模型是指依據(jù)系統(tǒng)硬件環(huán)境構(gòu)建出可進(jìn)行數(shù)學(xué)量化分析的數(shù)學(xué)模型，文中用二元組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í)行能力方面的差別可劃分為同構(gòu)和異構(gòu)2類，同構(gòu)多核處理器通過增加同種處理器內(nèi)核數(shù)量提升性能，而異構(gòu)多核處理器通過集成不同計算能力的內(nèi)核來優(yōu)化處理器，實現(xiàn)多核處理器性能發(fā)揮的最大化，在能耗、面積等方面有著巨大的優(yōu)勢[12]。文中以有限數(shù)目的異構(gòu)多核處理器為研究基礎(chǔ)，集合P中處理器內(nèi)核速度并不完全相同，用spk表示內(nèi)核Pk的處理速度。

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

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

1.2任務(wù)模型

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

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

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

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

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

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

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

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

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

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

1.3調(diào)度器模型

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

圖2　調(diào)度器模型 Fig.2　Scheduler model

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

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

2任務(wù)優(yōu)先級

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

(1)

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

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

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

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

(2)

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

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

(3)

(4)

(5)

0≤k≤m-1

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

(6)

(7)

(8)

(9)

(10)

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

3算法實現(xiàn)

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

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

1)假設(shè)任務(wù)間的依賴關(guān)系固定不變；

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

3)任務(wù)不可搶占。

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

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

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

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

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

1){for eachTi∈TLexe

2) {Tia[]←Ti;

3)for eachTj∈Tia

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

}/* end for eachTi∈TLexe*/

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

6) for eachTi∈TLready

7){for eachPk∈PList

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

}/* 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)先級的任務(wù)，設(shè)Tj就是選出的任務(wù)，且其對應(yīng)內(nèi)核為Ps，即Tjp= Tjps*/

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

19) TLready←TLready-{Tj};

20) Tjc=s；

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

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

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

}/* end for while*/

}

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

4實驗

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

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

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

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

1)調(diào)度粒度對STDS算法調(diào)度頻度和負(fù)載影響

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

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

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

表1調(diào)度粒度對負(fù)載均衡影響

Table1Changeofloadbalancinginthesituationofdifferentschedulinggranularities

調(diào)度粒度P0/%P1/%P2/%P3/%219.6120.4420.3739.58820.1119.8021.1938.901422.5119.1320.9137.45

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

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

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

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

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

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

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

βAWTofTop100/msAWTofAll/ms運(yùn)行時間/ms07603.11689.446325620.46752.751084.344342500.86179.30901.595349221.04838.11882.158351252.04517.32911.572357565.04497.84926.48535998

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

4.2算法對比實驗

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

由圖5可以看出在內(nèi)核數(shù)目較少時，Vinay算法比較高效，這是因為Vinay算法實現(xiàn)簡單，算法復(fù)雜度低，每個內(nèi)核分配一個任務(wù)，不需要考慮負(fù)載均衡等問題。隨著內(nèi)核數(shù)目增加，STDS算法優(yōu)勢逐步體現(xiàn)，這是因為Vinay算法一次調(diào)度分配一個任務(wù)，調(diào)度較頻繁，內(nèi)核數(shù)目較多時，會發(fā)生多個內(nèi)核同時請求調(diào)度，但同一時刻只有一個內(nèi)核可以調(diào)度成功，其他內(nèi)核不得不等待。STDS算法為每個內(nèi)核設(shè)置一個任務(wù)隊列，每次調(diào)度會分配若干個任務(wù)，這樣雖然增大了算法復(fù)雜度，但減少了調(diào)度次數(shù)且最大限度避免了內(nèi)核等待現(xiàn)象，所以總時間較小。STDS算法比較適合內(nèi)核數(shù)目較多的系統(tǒng)，但值得注意的是在內(nèi)核數(shù)目較多的系統(tǒng)中，對任務(wù)量的要求也較大，否則難以充分發(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算法復(fù)雜度與Min-Min算法相當(dāng)，但調(diào)度運(yùn)行時間比Min-Min算法稍長，原因是Min-Min算法將運(yùn)行時間作為其唯一考慮因素，優(yōu)先選取最早完成時間最小的任務(wù)進(jìn)行調(diào)度。但Min-Min算法中執(zhí)行時間較長的任務(wù)得不到及時執(zhí)行，圖6是STDS算法與Min-Min算法等待時間的對比結(jié)果。

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

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

5結(jié)束語

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

參考文獻(xiàn):

[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]石威, 鄭緯民. 相關(guān)任務(wù)圖的均衡動態(tài)關(guān)鍵路徑調(diào)度算法[J]. 計算機(jī)學(xué)報, 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)任務(wù)調(diào)度研究進(jìn)展評述[J]. 計算機(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)境下的任務(wù)調(diào)度關(guān)鍵技術(shù)研究[D]. 吉林: 吉林大學(xué), 2013： .

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

[10]徐雨明，李肯立. 異構(gòu)系統(tǒng)中DAG任務(wù)調(diào)度的雙螺旋結(jié)構(gòu)遺傳算法[J]. 計算機(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]陳銳忠,齊德昱,林偉偉.一種面向非對稱多核處理器的綜合性調(diào)度算法. 軟件學(xué)報, 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中基于可信評價的資源調(diào)度研究[J]. 計算機(jī)學(xué)報, 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)化、信息安全與智能信息處理。