異構(gòu)多核調(diào)度算法研究綜述

晉高成，李丕丁

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

0 引言

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

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

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

1.1 國(guó)外現(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 算法是針對(duì)異構(gòu)多核數(shù)量有限情況下的任務(wù)調(diào)度算法，該算法分為兩個(gè)階段，分別為任務(wù)優(yōu)先級(jí)排序和任務(wù)分配階段。在第1 階段，對(duì)于所有任務(wù)優(yōu)先級(jí)，主要根據(jù)任務(wù)的向上排序進(jìn)行計(jì)算；在第2 階段，調(diào)度器會(huì)根據(jù)在第1 階段計(jì)算的優(yōu)先級(jí)，按照非遞增順序?yàn)楦魅蝿?wù)選擇合適的處理器核，在該階段還會(huì)采取區(qū)間插入技術(shù)，以減少任務(wù)間的通信時(shí)間。相比于HEFT 算法，CPOP算法在優(yōu)先級(jí)計(jì)算上采取了不同的算法，它將任務(wù)的向上排序值和向下排序值作為任務(wù)優(yōu)先級(jí)，計(jì)算出優(yōu)先級(jí)后再將優(yōu)先級(jí)最高的任務(wù)到出口節(jié)點(diǎn)的路徑作為整個(gè)任務(wù)的關(guān)鍵路徑。在任務(wù)分配階段，CPOP 會(huì)將關(guān)鍵路徑上的任務(wù)映射到同一處理器核上，剩下的節(jié)點(diǎn)按照最早完成時(shí)間進(jìn)行映射。

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

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

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

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

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

2.1 ICPOP 算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Fig.5 The result of ant colony optimization圖5 智能蟻群算法運(yùn)行結(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í)，根據(jù)優(yōu)先級(jí)構(gòu)造調(diào)度列表。在調(diào)度過程中采取任務(wù)復(fù)制技術(shù)，再將各任務(wù)節(jié)點(diǎn)分配到處理器核上執(zhí)行，提升處理器利用效率，可分為優(yōu)先級(jí)計(jì)算階段和任務(wù)分配階段。

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

異構(gòu)多核任務(wù)調(diào)度算法的關(guān)鍵在于如何合理調(diào)度，使得所有任務(wù)完成所用時(shí)間最短。該問題是一個(gè)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ù)量少時(shí)更具優(yōu)勢(shì)，非確定性算法在處理大規(guī)模任務(wù)時(shí)有更早的完成時(shí)間。目前，對(duì)于確定性任務(wù)調(diào)度算法中的列表調(diào)度算法使用最為廣泛，但是在處理大規(guī)模任務(wù)量時(shí)還是會(huì)采取蟻群算法、退火算法等非確定性算法。從上述算法中可以看出，未來發(fā)展趨勢(shì)是將非確定性算法和確定性算法相結(jié)合，實(shí)現(xiàn)優(yōu)勢(shì)互補(bǔ)。