晉高成，李丕丁

（上海理工大學(xué)醫(yī)療器械與食品學(xué)院，上海 200093）

0 引言

隨著網(wǎng)絡(luò)和通信技術(shù)的飛速發(fā)展，各式各樣的電子設(shè)備已廣泛應(yīng)用于人們的日常生活、工作及生產(chǎn)等方面。近年來，機器學(xué)習(xí)、人工智能、無人駕駛等研究不斷深入，使得人們對CPU 計算速度的要求不斷提升［1］。然而，單核處理器一般通過提高處理器的主頻以提升處理器運算速度，該方法導(dǎo)致處理器功耗不斷提升，進而導(dǎo)致處理器工作溫度相應(yīng)升高［2］。在需求和傳統(tǒng)處理器性能矛盾日益尖銳的情況下，多核處理器應(yīng)運而生［3］。在主頻不變的前提下，雙核處理器的運行速度在理論上是單核處理器的1 倍，這意味著在相同時間內(nèi)，雙核處理器可以做單核處理器兩倍的計算量，極大增加了處理器運行速率。并且，在單核處理器和雙核處理器達到相同性能時，雙核處理器的主頻甚至比單核處理的功耗低一半以上。多核處理器在性能和功耗上都比單核處理器表現(xiàn)更好，因此，越來越多的研究集中在多核處理器上［4］。

多核處理器又分為異構(gòu)多核處理器和同構(gòu)多核處理器。在同構(gòu)處理器中，所有處理器核結(jié)構(gòu)一致、功能相同、地位均等，相同程序在各處理器核上單獨運行所用的時間都相等［5］。正是由于以上特點，同構(gòu)多核處理器在運行應(yīng)用程序時并不能發(fā)揮最佳性能。每個處理器核的處理性能都相同，并不能為不同計算要求的應(yīng)用程序提供更快的計算速度。異構(gòu)多核處理器由多個不同類型的處理器核心構(gòu)成，每個核心結(jié)構(gòu)不同、功能也不同，針對某類運算具有較快處理速度，且每個核心都具有其擅長的功能［6］。如某個核心擅長浮點計算，另一個核心擅長任務(wù)切換。當(dāng)處理某個含有多種計算要求的應(yīng)用程序時，異構(gòu)多核處理器往往比同構(gòu)處理器表現(xiàn)得更好。盡管異構(gòu)多核處理器比同構(gòu)多核處理器在很多方面都表現(xiàn)得更好，但是異構(gòu)多核處理器核心在結(jié)構(gòu)和功能上都不相同，給硬件和軟件設(shè)計帶來了更多挑戰(zhàn)。目前，針對異構(gòu)多核處理器的硬件和軟件相關(guān)研究較多，高效的調(diào)度算法是研究重點，它能及時將任務(wù)分配到特定的處理器核心上，體現(xiàn)出異構(gòu)多核處理器的性能優(yōu)勢。本文主要介紹基于異構(gòu)多核的任務(wù)調(diào)度算法，與已有調(diào)度算法進行對比，并分析優(yōu)缺點。

1 異構(gòu)多核任務(wù)調(diào)度研究現(xiàn)狀

1.1 國外現(xiàn)狀

靜態(tài)啟發(fā)式表調(diào)度算法HEFT（Heterogeneous Earliest Finish Time）與CPOP（Critical Path on a Processor）算法是由Topcuoglu 等［7］提出的兩種異構(gòu)環(huán)境下的多核任務(wù)調(diào)度算法。其中，HEFT 算法是針對異構(gòu)多核數(shù)量有限情況下的任務(wù)調(diào)度算法，該算法分為兩個階段，分別為任務(wù)優(yōu)先級排序和任務(wù)分配階段。在第1 階段，對于所有任務(wù)優(yōu)先級，主要根據(jù)任務(wù)的向上排序進行計算；在第2 階段，調(diào)度器會根據(jù)在第1 階段計算的優(yōu)先級，按照非遞增順序為各任務(wù)選擇合適的處理器核，在該階段還會采取區(qū)間插入技術(shù)，以減少任務(wù)間的通信時間。相比于HEFT 算法，CPOP算法在優(yōu)先級計算上采取了不同的算法，它將任務(wù)的向上排序值和向下排序值作為任務(wù)優(yōu)先級，計算出優(yōu)先級后再將優(yōu)先級最高的任務(wù)到出口節(jié)點的路徑作為整個任務(wù)的關(guān)鍵路徑。在任務(wù)分配階段，CPOP 會將關(guān)鍵路徑上的任務(wù)映射到同一處理器核上，剩下的節(jié)點按照最早完成時間進行映射。

在考慮減少任務(wù)調(diào)度長度的同時，也需關(guān)注異構(gòu)處理器的能耗問題。Maurya 等［8］提出一種基于能耗感知的異構(gòu)多核，該算法主要是以較少的高優(yōu)先級任務(wù)通信時間降低總?cè)蝿?wù)調(diào)度能耗。此外，有一種結(jié)合動態(tài)電壓調(diào)節(jié)技術(shù)和關(guān)鍵路徑的調(diào)度算法，不僅可減少調(diào)度長度，還能降低能耗，由Baskiyar 等［9］提出。也有較多在HEFT 算法基礎(chǔ)上的改進算法，如Lookahead 算法［10］。

隨著對智能調(diào)度算法研究的不斷深入，研究者開始將目光聚焦于遺傳算法［11-13］、蟻群算法［14-15］、模擬退火算法［16-17］等。

1.2 國內(nèi)現(xiàn)狀

國內(nèi)對于異構(gòu)多核任務(wù)調(diào)度算法的研究要晚于國外，但也取得一系列成果。譚文安等［18］提出一種帶極值擾動的相關(guān)性粒子群優(yōu)化算法EDCPSO（Extremum Disturbed Correlative Particle Swarm Optimization）；石 威 等［19］結(jié) 合MCP 算法和EFT 算法，提出一種動態(tài)的表調(diào)度算法。該算法不僅考慮到關(guān)鍵路徑節(jié)點，也考慮了非關(guān)鍵節(jié)點，對Makesapn 影響最大的可運行任務(wù)賦予最高優(yōu)先級，極大減少異構(gòu)多核上的任務(wù)調(diào)度長度，提升異構(gòu)多核處理器性能；徐遠超等［20］實現(xiàn)了一種可在Linux 中運行的能進行感知的異構(gòu)多核調(diào)度算法。該算法在保證各處理器利用效率達到動態(tài)平衡的基礎(chǔ)上，減少其它處理器核心空閑時間，且算法時間復(fù)雜度低，在負載均衡時能夠進行感知。

2 3 種異構(gòu)多核任務(wù)調(diào)度算法

2.1 ICPOP 算法

傳統(tǒng)的CPOP 算法雖然在一定程度上減少了任務(wù)調(diào)度時間，但依然存在許多不足。CPOP 算法首先根據(jù)任務(wù)優(yōu)先級形成任務(wù)列表（基于異構(gòu)多核的混合式任務(wù)調(diào)度算法研究），然后將任務(wù)分配到處理器核上。但是優(yōu)先權(quán)僅僅分配了關(guān)鍵任務(wù)，任務(wù)之間的依賴和約束關(guān)系并沒有被充分考慮進去。在這種情況下，如果關(guān)鍵任務(wù)的父任務(wù)并沒有及時被分配運行，則關(guān)鍵任務(wù)的運行時間將被延后，這樣會對任務(wù)的總完成時間產(chǎn)生不利影響。并且，CPOP 算法會將所有關(guān)鍵任務(wù)分配到同一個處理器核，雖然該方法可以減少這些關(guān)鍵任務(wù)之間的通信開銷，并且可以讓這些任務(wù)具有最早完成時間，但是該方法會造成不同處理器之間負載的不均衡，導(dǎo)致許多處理器核在某個核心過于忙碌時處于空閑狀態(tài)，使得處理器核心利用不充分。針對以上不足，本文提出一種基于CPOP 的改進算法ICPOP（Im?provedCritical Path on a Processor）。

ICPOP 算法在整體上與CPOP 算法一樣，總共分為兩個階段：任務(wù)優(yōu)先級計算階段和處理器核分配階段。

Fig.1 Priority calculation process圖1 優(yōu)先級計算流程

任務(wù)優(yōu)先級計算階段：ICPOP 算法的優(yōu)先級計算流程如圖1 所示。在該階段之前，要先將DAG（Directed Acy?clic Graph）標(biāo)準化。一個標(biāo)準的DAG 僅僅包含一個入口任務(wù)和一個出口任務(wù)，入口任務(wù)是父任務(wù)集合為空的節(jié)點，出口任務(wù)是子任務(wù)集合為空的節(jié)點。為了構(gòu)建一個標(biāo)準的DAG，就需要保證該DAG 中只含有一個入口任務(wù)和一個出口任務(wù)。因此，要使原DAG 中所有父任務(wù)集合為空的點添加一個父任務(wù)集合為空的節(jié)點，并讓它成為之前父任務(wù)集合為空的節(jié)點的父節(jié)點。同理，對于所有子任務(wù)集合為空的節(jié)點，添加一個子任務(wù)集合為空的節(jié)點，并讓其成為上述節(jié)點的子節(jié)點，這樣便可以構(gòu)建一個標(biāo)準的DAG。

對于異構(gòu)多核處理器，出口任務(wù)完成時間就是整個任務(wù)調(diào)度完成時間。計算任務(wù)優(yōu)先級時，需將最高優(yōu)先級賦予擁有最長路徑的關(guān)鍵任務(wù)，這樣可盡量保證完成時間最短。對于非關(guān)鍵任務(wù)，出口任務(wù)的父任務(wù)及其父任務(wù)的完成時間影響出口任務(wù)開始執(zhí)行時間，故若某任務(wù)到出口任務(wù)的開銷（計算開銷及通信開銷）越大，則該任務(wù)越需要提前執(zhí)行，因此賦予該任務(wù)較高的優(yōu)先級，以此縮短整個SAG 完成時間。然而，同一任務(wù)在不同處理器核心上計算開銷不同，計算差異較大的任務(wù)分配較高優(yōu)先權(quán)，以提升其獲得開銷最小處理器核的概率。綜上所述，在計算任務(wù)優(yōu)先級時，需計算出每個任務(wù)到出口任務(wù)的總開銷ε(Ni)以及當(dāng)前任務(wù)在不同處理器核上的計算開銷差異σ(Ni)，計算方法如式（1）所示。

從當(dāng)前任務(wù)Ni到出口任務(wù)的總開銷ε(Ni)計算公式如式（2）所示。其中,child(Ni)表示任務(wù)Ni的后繼任務(wù)集合。

由于異構(gòu)多核處理器各處理器核之間的計算速率各不相同，在計算優(yōu)先級時要計算任務(wù)在不同處理器核上的開銷差異，計算開銷差異用σ(Ni)表示，σ(Ni)的計算公式如式（3）所示。

在式（3）中，P 表示處理器核的數(shù)目，k 表示處理器序號。計算完任務(wù)優(yōu)先級后再根據(jù)計算出的優(yōu)先級按照非遞增順序?qū)θ蝿?wù)進行排序，以構(gòu)建任務(wù)調(diào)度列表。

處理器核分配階段：經(jīng)歷上述階段后，得到已經(jīng)排序好的調(diào)度列表，再利用區(qū)間插入技術(shù)對任務(wù)進行分配。不斷選取任務(wù)調(diào)度列表中優(yōu)先級最高的任務(wù)，然后將其放置在開始時間最接近的處理器核上執(zhí)行，重復(fù)上述操作，直到調(diào)度列表為空。處理器核分配流程如圖2 所示。在上述方法中，使用區(qū)間插入技術(shù)，該技術(shù)指將任務(wù)插入到同一處理器核心上兩個任務(wù)之間的空閑時間space，但是不能破壞任務(wù)之間的前驅(qū)后繼關(guān)系，必須滿足式（4）的任務(wù)才可采用區(qū)間插入技術(shù)。

在式（4）中，st（space）表示空閑區(qū)間開始時間，space_length 表示空閑區(qū)間大小，用st（Ni，pk）表示任務(wù)Ni在處理器核pk上的開始執(zhí)行時間，WO(Ni,pk)表示任務(wù)Ni在處理器核pk上的所有開銷。

為了比較ICPOP 算法和CPOP 算法性能，設(shè)置不同的任務(wù)節(jié)點數(shù)以及不同的異構(gòu)多核處理器，分別采用ICPOP算法和CPOP 算法進行對比實驗，比較在不同DAG 下的完成時間長短，結(jié)果如圖3 所示。

從圖3 可以看出，ICPOP 算法在大多數(shù)情況下比CPOP 算法減少了任務(wù)調(diào)度完成時間，ICPOP 算法獲得的任務(wù)調(diào)度長度更短。同時，在任務(wù)節(jié)點為50，核心數(shù)為2時，CPOP 算法比ICPOP 算法更加高效。

Fig.2 Processor core allocation process圖2 處理器核分配流程

Fig.3 Completion time of ICPOP algorithm and CPOP algorithm圖3 ICPOP 算法與CPOP 算法完成時間

2.2 智能蟻群調(diào)度算法

隨著并行執(zhí)行模型的發(fā)展和完善，文獻［6］提出Code?let 模型，該模型是一種事件驅(qū)動的、細粒度的、混合控制流的并行執(zhí)行模型。

該算法針對異構(gòu)多核的Codelet 計算環(huán)境，結(jié)合HEFT算法和蟻群算法，提出一種智能蟻群調(diào)度策略（Samrt Ant Colony Task Scheduling）。該算法執(zhí)行流程如圖4 所示。

如圖4 所示，該算法首先輸入CDG、數(shù)據(jù)傳輸時間開銷C 以及人物執(zhí)行開銷ETC，然后根據(jù)HEFT 算法計算每個節(jié)點的靜態(tài)優(yōu)先級Rank，螞蟻從Codelet 節(jié)點開始出發(fā)，依照動態(tài)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個調(diào)度的Codelet 節(jié)點，再將該節(jié)點分配給最早時間空閑的處理器核，開始執(zhí)行該節(jié)點，跟新動態(tài)因子，重復(fù)上述步驟，直到調(diào)度達到最大迭代次數(shù)。該算法的參數(shù)和初始化值如表1 所示。

Fig.4 Scheduling strategy of ant colony optimization圖4 智能蟻群調(diào)度策略算法流程

Table 1 Parameters and initialization values表1 參數(shù)與初始化值

該算法中每個節(jié)點的靜態(tài)優(yōu)先級可以采用ICPOP 算法中的優(yōu)先級計算方法，計算每個節(jié)點的靜態(tài)優(yōu)先級。該算法中螞蟻通過狀態(tài)轉(zhuǎn)移規(guī)則決定下一個COdelet 任務(wù)，該動態(tài)規(guī)則由式（5）計算得出。

其中，τ（i，w）為（i，w）邊上的信息素強度，該值越大，該節(jié)點被選擇的概率越大。該算法通過調(diào)整動態(tài)因子q0控制收斂速度，q0越小，蟻群選擇的多樣性越好。q0由式（6）計算得出。

在構(gòu)造解的過程中，每個螞蟻都會對自己選擇的邊更新局部信息素。該做法的目的在于防止完成一次迭代后，其它螞蟻會得到同樣的解。因此，需不斷更新對應(yīng)的信息素τ（t，n），更新公式如式（7）所示。

該算法運行結(jié)果如圖5 所示。其中，Robot 擁有88 個節(jié)點，Sparse 有96 個節(jié)點，F(xiàn)pppp 有334 個節(jié)點。Static 為靜態(tài)調(diào)度策略，Dynamic 為原生動態(tài)導(dǎo)讀策略，SACTS 為智能蟻群調(diào)度策略?？梢钥闯?，在解決大規(guī)模任務(wù)調(diào)度問題時，智能蟻群調(diào)度策略比原生動態(tài)調(diào)度和靜態(tài)調(diào)度策略擁有更高效率，并縮短了任務(wù)執(zhí)行時間。

Fig.5 The result of ant colony optimization圖5 智能蟻群算法運行結(jié)果

2.3 一種啟發(fā)式綜合任務(wù)調(diào)度算法

IHTSGMP（Integrated Heuristic Task Scheduling Algo?rithm for Heterogeneous Multicore Processer）算法以表調(diào)度算法為基礎(chǔ)，首先構(gòu)建任務(wù)調(diào)度優(yōu)先級，根據(jù)優(yōu)先級構(gòu)造調(diào)度列表。在調(diào)度過程中采取任務(wù)復(fù)制技術(shù)，再將各任務(wù)節(jié)點分配到處理器核上執(zhí)行，提升處理器利用效率，可分為優(yōu)先級計算階段和任務(wù)分配階段。

優(yōu)先級計算階段：在該階段開始時，需根據(jù)現(xiàn)有任務(wù)節(jié)點，構(gòu)建一個DAG，表示任務(wù)執(zhí)行和依賴關(guān)系。計算優(yōu)先級的方法大致類似，都是根據(jù)關(guān)鍵路徑法，首先需找到關(guān)鍵路徑節(jié)點最高優(yōu)先級。對于其它節(jié)點，IHTSHMP 算法的優(yōu)先級由式（8）計算得出。

其中，weighti表示節(jié)點i的優(yōu)先級權(quán)值，ncp表示當(dāng)前任務(wù)節(jié)點的直接后繼關(guān)鍵路徑節(jié)點。cp_value(ni)的定義如式（9）所示。

任務(wù)分配階段：IHTSHMP 算法采用任務(wù)復(fù)制以及區(qū)間插入方法。首先選擇最早完成任務(wù)的處理器內(nèi)核，然后根據(jù)第一階段計算出的優(yōu)先級，選擇優(yōu)先級最好的節(jié)點，再分別計算該節(jié)點在被選擇的核心上采用和不采用任務(wù)復(fù)制技術(shù)的最早完成時間，選擇最早完成時間最短的方案。任務(wù)復(fù)制流程如圖6 所示。

Fig.6 The process of task copy圖6 任務(wù)復(fù)制流程

其中，est(ni,pu)和est2(ni,pu)分別為不采用任務(wù)復(fù)制和采用任務(wù)復(fù)制的最早完成時間。在任務(wù)復(fù)制策略基礎(chǔ)上，采用在ICPOP 算法中敘述的區(qū)間插入技術(shù)，進一步提升處理器利用效率。

該算法運行效果如圖7 和圖8 所示。該實驗對比了前驅(qū)復(fù)制算法CPFD（Critical Path Fast Duplication）［21］和選擇性任務(wù)復(fù)制的表調(diào)度算法STDH（Selected Task Duplica?tion for Heterogenous System）［22］?？梢钥闯?，相比于CPFD算法和STDH 算法，IHTSHMP 算法在不同任務(wù)數(shù)下都保持著較高調(diào)度效率。

Fig.7 Comparison of average speedups of different tasks圖7 不同任務(wù)數(shù)下的平均加速比對比

Fig.8 Comparison of average accelerations with different CCRs圖8 不同CCR 下的平均加速比對比

3 調(diào)度算法總結(jié)

ICPOP 算法在優(yōu)先級計算和處理器核分配上對CPOP算法作出改進。在任務(wù)優(yōu)先級計算時，不僅考慮了當(dāng)前任務(wù)到出口任務(wù)的開銷，還計算了此任務(wù)在不同處理器核上的計算開銷差值，相對于CPOP 算法，保證差值大的任務(wù)節(jié)點可以被優(yōu)先調(diào)度，縮短任務(wù)調(diào)度時間；在處理器核分配階段，采用區(qū)間插入技術(shù)，減少處理器在任務(wù)和任務(wù)之間的縫隙，提升處理器利用效率，從而縮短任務(wù)調(diào)度長度。

智能蟻群算法結(jié)合靜態(tài)啟發(fā)式調(diào)度算法HEFT 和改進蟻群算法，在優(yōu)先級計算階段采用與HEFT 算法相同的優(yōu)先級計算方法，隨后采用蟻群算法，改進動態(tài)狀態(tài)轉(zhuǎn)移規(guī)則，更加有效地選取下個待運行節(jié)點。

IHTSHMP 算法是一種啟發(fā)式綜合任務(wù)調(diào)度算法。該算法綜合任務(wù)復(fù)制算法和表調(diào)度算法。計算優(yōu)先級時考慮任務(wù)拓撲圖結(jié)構(gòu)，進一步優(yōu)化優(yōu)先級計算，提升調(diào)度效率；任務(wù)分配階段采用任務(wù)復(fù)制技術(shù)，比較復(fù)制和不復(fù)制對整體的影響，然后選擇是否采取復(fù)制，該方法減少了依賴任務(wù)通信延遲，充分發(fā)揮了異構(gòu)處理器的優(yōu)勢。

4 結(jié)語

異構(gòu)多核任務(wù)調(diào)度算法的關(guān)鍵在于如何合理調(diào)度，使得所有任務(wù)完成所用時間最短。該問題是一個NP（Nondeterministic Polynomial Complete）問題，目前還沒有一種能確保每次都可獲得最優(yōu)解的算法，只能是不斷地逼近最優(yōu)解。異構(gòu)多核任務(wù)調(diào)度算法主要分為確定性算法和非確定性算法，本文提到的任務(wù)復(fù)制算法和表調(diào)度算法為確定性調(diào)度算法，蟻群調(diào)度算法為非確定性調(diào)度算法。確定性算法在任務(wù)數(shù)量少時更具優(yōu)勢，非確定性算法在處理大規(guī)模任務(wù)時有更早的完成時間。目前，對于確定性任務(wù)調(diào)度算法中的列表調(diào)度算法使用最為廣泛，但是在處理大規(guī)模任務(wù)量時還是會采取蟻群算法、退火算法等非確定性算法。從上述算法中可以看出，未來發(fā)展趨勢是將非確定性算法和確定性算法相結(jié)合，實現(xiàn)優(yōu)勢互補。