1、關(guān)于任務(wù)調(diào)度相關(guān)研究文獻(xiàn)綜述隨著多核處理器的出現(xiàn)，多核處理器任務(wù)調(diào)度已成為當(dāng)前高性能處理器研究的熱點(diǎn)之一。任務(wù)調(diào)度是指系統(tǒng)為確定一系列任務(wù)的執(zhí)行順序所采取的調(diào)度策略。隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，學(xué)術(shù)界對任務(wù)調(diào)度問題的討論也逐漸深入，旨在通過減少通信開銷、改變?nèi)蝿?wù)執(zhí)行順序，以縮短整個任務(wù)的調(diào)度長度1。近年來，由于多處理器的廣泛應(yīng)用，如何充分利用多處理器的計(jì)算性能成為了大家關(guān)注的焦點(diǎn)，針對多處理器的任務(wù)調(diào)度問題突顯出來。在多處理器任務(wù)調(diào)度算法研究的早期，P Dutot24等人在研究中指出，對于異構(gòu)計(jì)算環(huán)境下的任務(wù)調(diào)度問題是NP 難問題，難以在多項(xiàng)式時間內(nèi)尋求最優(yōu)解。正是該問題的重要性和復(fù)雜性，吸引了

2、一大批專家學(xué)者對其進(jìn)行研究，并提出了大量經(jīng)典的算法。一、國外研究現(xiàn)狀計(jì)算機(jī)任務(wù)調(diào)度的研究早在上世紀(jì)60年代就已開始。1967年，芝加哥大學(xué)的Manacher G.K在ACM期刊上第一次提出了“任務(wù)”的概念，并利用列表法和甘特圖進(jìn)行了基本的多核多任務(wù)調(diào)度算法研究，提出了能夠保證調(diào)度穩(wěn)定性的算法。同時文章對軟實(shí)時系統(tǒng)和硬實(shí)時系統(tǒng)也給出了定義和說明。但是由于文章發(fā)表年代較為久遠(yuǎn)，文中提出的是同構(gòu)多核處理器的模型，并不適用于當(dāng)今迅速發(fā)展的異構(gòu)多核處理器之間的任務(wù)調(diào)度。隨后，劉炯朗和Layland在已有工作基礎(chǔ)上提出了周期任務(wù)模型的概念，該模型對任務(wù)進(jìn)行了較好的抽象，對周期性任務(wù)做出了一些假設(shè)，忽略計(jì)算

3、機(jī)體系結(jié)構(gòu)的復(fù)雜性以及應(yīng)用程序的具體實(shí)現(xiàn)，可以借助各種數(shù)學(xué)方法對任務(wù)的可調(diào)度性進(jìn)行分析。文中提出了可在單處理器上運(yùn)行的三種調(diào)度算法：單調(diào)速率算法RM(rate monotonic algorithm)、最早結(jié)束優(yōu)先 EDF(earliest deadline first)算法1以及兩者的混合算法。在 RM 算法中，根據(jù)任務(wù)的需求速度賦予其一定的優(yōu)先級，即所謂的固定優(yōu)先級。在 EDF 算法中，任務(wù)最終期限值較小的賦予更高的優(yōu)先級，即動態(tài)調(diào)整任務(wù)的優(yōu)先級。而綜合算法將任務(wù)分開對待，分別使用上述的算法。文章分析了在上述幾種任務(wù)調(diào)度算法下，CPU能夠達(dá)到的最大利用率，并用數(shù)學(xué)方法給予了證明。為后來的研

4、究奠定了基礎(chǔ)。后續(xù)又提出了許多經(jīng)典算法，包括時間片輪轉(zhuǎn)(Round Robin，RR)算法、先到先服務(wù)(First Come First Served，F(xiàn)CFS)算法、截止期單調(diào)調(diào)度(Deadline Monotonic Scheduling, DMS) 算法等。在這些算法中，任務(wù)的優(yōu)先級都是基于任務(wù)的某些特征參數(shù)，如截止期、空閑時間或關(guān)鍵性等計(jì)算而得。然而，如果優(yōu)先級僅由某個特征參數(shù)來確定是不夠的，因?yàn)榻刂蛊诨蛘呖臻e時間短的任務(wù)不一定是最關(guān)鍵的。而且這些算法主要是針對單核處理器，并不適用于多核處理器的任務(wù)調(diào)度。對于異構(gòu)計(jì)算環(huán)境下的任務(wù)調(diào)度問題是NP完全問題，難以在多項(xiàng)式時間內(nèi)尋求最優(yōu)解。正是

5、該問題的重要性和復(fù)雜性，吸引了一大批專家學(xué)者對其進(jìn)行研究，并提出了大量經(jīng)典的算法。Haluk Topcuoglu和Salim Hariri等人通過對異構(gòu)環(huán)境下的任務(wù)調(diào)度進(jìn)行大量分析，在1999年提出了兩種到目前為止公認(rèn)的調(diào)度效率較高的算法：基于處理器關(guān)鍵路徑算法8 (Critical Path On a Processor，CPOP)和異構(gòu)最早結(jié)束時間算法8 (Heterogeneous Earliest Finish Time, HEFT)，是異構(gòu)多處理器任務(wù)調(diào)度十分經(jīng)典的調(diào)度算法。后期許多任務(wù)調(diào)度的算法都是在這兩種算法的基礎(chǔ)上提出的。這些算法都使用有向無環(huán)圖(Directed Acycli

6、c Graph，DAG)來表示任務(wù)模型，節(jié)點(diǎn)上和節(jié)點(diǎn)間都根據(jù)時間開銷賦予一個權(quán)值。在任務(wù)排序和任務(wù)分配兩個階段采用不同的方法來提高任務(wù)調(diào)度的效率。HEFT算法思想描述如下：在任務(wù)排序階段，每個任務(wù)根據(jù)自身的運(yùn)行時間和與后繼任務(wù)的通信時間計(jì)算出一個向上排序值ranku(n)，根據(jù)ranku(n)降序排列每個任務(wù)；在任務(wù)分配階段則根據(jù)最早完成時間進(jìn)行分配，這種機(jī)制降低了算法復(fù)雜度，但同時處理器的利用率有待提高。與其它基于最早完成時間的調(diào)度算法有所不同，HEFT算法采用了區(qū)間插入技術(shù)，在同一處理器兩個相鄰任務(wù)間可能插入其它任務(wù)間隙處，插入一個新的任務(wù)來提高多核處理器的并行性和利用率，從而提高調(diào)度效率

7、。但是該算法存在一些明顯的缺點(diǎn)：任務(wù)排序只考慮到與后繼任務(wù)的通信開銷，讓一些向上排序值高的節(jié)點(diǎn)優(yōu)先運(yùn)行，但沒有從整體的拓?fù)浣Y(jié)構(gòu)考慮任務(wù)的關(guān)鍵程度，某節(jié)點(diǎn)向上排序值高并不代表此節(jié)點(diǎn)在整體拓?fù)浣Y(jié)構(gòu)的關(guān)鍵路徑上，也就是說，有些關(guān)鍵節(jié)點(diǎn)可能得不到較高的優(yōu)先級；能夠利用區(qū)間插入技術(shù)插入到某個空閑時段的任務(wù)可能并不多；沒有考慮較大任務(wù)間的通信開銷，如果兩個較大任務(wù)被分配到不同的處理器，任務(wù)間的通信開銷可能遠(yuǎn)遠(yuǎn)超過任務(wù)本身的運(yùn)行開銷。HEFT算法的時間復(fù)雜度是O(n2*p),n表示任務(wù)個數(shù)，p表示處理器個數(shù)?？紤]到HEFT算法存在的問題，Haluk Topcuoglu等人又提出了一種CPOP算法。該算法在任

8、務(wù)排序階段不僅考慮了向上排序值ranku(n)，而且還考慮了向下排序值rankd(n)，通過兩者的綜合加上自身運(yùn)行開銷，計(jì)算每個節(jié)點(diǎn)的優(yōu)先級權(quán)值，并且得到一個關(guān)鍵路徑，然后選擇一個串行執(zhí)行這些關(guān)鍵路徑任務(wù)時間最短的處理器CPP。任務(wù)分配階段，把屬于關(guān)鍵路徑上的任務(wù)分配到CPP，非關(guān)鍵路徑上的任務(wù)分配到具有最早完成時間的處理器上，后者結(jié)合了區(qū)間插入技術(shù)。關(guān)鍵路徑是任務(wù)圖中距離最長的路徑，關(guān)鍵路徑長度決定了整個任務(wù)圖的完成時間，所以CPOP算法的目的是給關(guān)鍵路徑上的任務(wù)更高的優(yōu)先級，保證關(guān)鍵任務(wù)優(yōu)先調(diào)度，以此來縮短整個任務(wù)完成時間。但CPOP算法同樣存在一些不足：只考慮了提高關(guān)鍵路徑節(jié)點(diǎn)的優(yōu)先級，

9、有可能忽視了某些關(guān)鍵節(jié)點(diǎn)的父節(jié)點(diǎn)，但這些父節(jié)點(diǎn)又不在關(guān)鍵路徑上，CPOP算法中該類非關(guān)鍵路徑節(jié)點(diǎn)的優(yōu)先級可能很低，非關(guān)鍵路徑節(jié)點(diǎn)的延遲調(diào)度將會影響關(guān)鍵路徑的完成時間，降低整個調(diào)度算法的效率；同時，這種分配機(jī)制導(dǎo)致執(zhí)行關(guān)鍵路徑的處理器負(fù)載偏重，而其它處理器利用率并不一定很高，從而降低了處理器的利用率，導(dǎo)致處理器負(fù)載不均。此外，在異構(gòu)多處理器任務(wù)調(diào)度算法中，經(jīng)典的啟發(fā)式算法還有Max-min、Min-min、Sufferage等。Tracy D.Braun等人對這些算法做了比較和實(shí)驗(yàn)，給出了各種算法的實(shí)際性能12。 Max-min算法首先計(jì)算任務(wù)的預(yù)期完成時間(Expected Earliest

10、Completion Time, EECT)，然后優(yōu)先調(diào)度EECT最大的任務(wù)，優(yōu)先對其進(jìn)行資源分配。這種調(diào)度方法可以保證顆粒大的任務(wù)較好地被執(zhí)行，能夠在一定程度上實(shí)現(xiàn)負(fù)載均衡。但該方法沒有考慮任務(wù)的執(zhí)行頻率，對于那些執(zhí)行頻繁的小任務(wù)，提高它的執(zhí)行優(yōu)先級可能會取得更好的整體性能。同Max-min算法相似，Min-min算法也是根據(jù)任務(wù)的EECT來確定任務(wù)調(diào)度優(yōu)先級。不過，Min-min算法將EECT最小的任務(wù)對應(yīng)最高的優(yōu)先級，即將顆粒小的任務(wù)優(yōu)先分配到最佳處理器上，依次完成任務(wù)的劃分。該算法實(shí)現(xiàn)簡單、復(fù)雜度較低。但算法策略單一，在按EECT從小到大順序?qū)θ蝿?wù)劃分時，容易引起處理器負(fù)載不平衡。Su

11、fferage算法在Max-min和Min-min算法的基礎(chǔ)之上進(jìn)行改進(jìn)。對于每個任務(wù)，計(jì)算其次早完成時間(放在次優(yōu)處理器上執(zhí)行的時間)與最早完成時間的差值，該差值命名為Sufferage值，反映出各個任務(wù)的調(diào)度代價。Sufferage算法按Sufferage值從大到小確定任務(wù)的優(yōu)先級，以保證調(diào)度所帶來的代價最小。但該算法只考慮任務(wù)單次執(zhí)行的情況，沒能考慮任務(wù)的執(zhí)行頻率，從而沒有不能計(jì)算在一段時間內(nèi)的總代價，不能取得很好地負(fù)載均衡。同時沒有考慮任務(wù)最早完成時間，故系統(tǒng)總的執(zhí)行時間難以最優(yōu)。另外，Sanjoy Baruah教授及其小組在任務(wù)調(diào)度與分析領(lǐng)域的研究比較活躍，相繼發(fā)表了一系列有影響的文

12、章567。同時，各研究者根據(jù)不同的應(yīng)用需求，提出了多類調(diào)度算法。為了減少任務(wù)之間的通信開銷，許多學(xué)者提出了基于任務(wù)復(fù)制(Task Duplication Based, TDB)及分組等多種調(diào)度算法。Kwok和Ahmed提出了關(guān)鍵路徑快速復(fù)制(Critical Path Fast Duplication，CPFD)算法20，Bansal等提出了有限復(fù)制的調(diào)度算法21，Shin等人提出了最小復(fù)制算法22。這些算法都屬于基于任務(wù)的調(diào)度算法，通過在多個處理器之間對任務(wù)進(jìn)行復(fù)制，從而減少處理器之間的通信量。Abdelzaher和Shin在文獻(xiàn)23中，根據(jù)實(shí)時任務(wù)的周期進(jìn)行了分簇。他們的方法可以處理任務(wù)的

13、異構(gòu)性，擴(kuò)展性強(qiáng)。傳統(tǒng)的啟發(fā)式算法無法適應(yīng)所有的任務(wù)模型。在采用傳統(tǒng)啟發(fā)式算法之前往往需要對任務(wù)進(jìn)行假設(shè)，這使得一種啟發(fā)式算法只能應(yīng)用于特定的任務(wù)模型。于是許多人工智能算法被運(yùn)用到任務(wù)調(diào)度問題上來。 人工智能方法通過模擬各種自然活動，通過演化迭代的方式來求取問題的解，越來越多地被引入到啟發(fā)式算法當(dāng)中。目前，對于人工智能方法的研究已經(jīng)深入，許多方法形成自己的理論體系，為解決不同的復(fù)雜問題提供科學(xué)指導(dǎo)。這些方法有遺傳算法(Genetic Algorithm，GA)、模擬退火(Simulated Annealing，SA)算法、蟻群算法(Ant Colony Optimization，ACO)以及粒

14、子群優(yōu)化算法(Particle Swarm Optimization, PSO)等。這些算法都是模擬自然環(huán)境下的各種行為，從而求解過程具有隨機(jī)性，比傳統(tǒng)算法減少了人工干預(yù)。這些特點(diǎn)對于尋找全局最優(yōu)解方面具有獨(dú)特優(yōu)勢，為求解復(fù)雜問題提供了新的思路和解決方案，也廣泛應(yīng)用在任務(wù)調(diào)度這一復(fù)雜問題當(dāng)中。二、國內(nèi)研究現(xiàn)狀相對于國外的研究,國內(nèi)在多核處理器任務(wù)調(diào)度方面的研究起步比較晚,一直處于跟蹤研究階段,但隨著近年來國內(nèi)專家對任務(wù)調(diào)度研究的重視,仍取得了不少成果。中國科學(xué)院軟件研究所的戴國忠、王宏安等人發(fā)表了一系列研究成果32，采用集中式的調(diào)度方案, 考慮任務(wù)劃分策略及軟實(shí)時任務(wù)的服務(wù)質(zhì)量，以統(tǒng)一方式完成

15、對實(shí)時異構(gòu)系統(tǒng)中硬實(shí)時和軟實(shí)時任務(wù)的集成動態(tài)調(diào)度,提高了算法的調(diào)度成功率。此外，一些研究也對多處理器調(diào)度問題提出了新的算法和見解。針對fork-join圖結(jié)構(gòu)劉振英等人提出了一個新的算法TSA_FJ34(Task Schedule Algorithm Fork-Join)。TSA_FJ算法的原則是讓Fork-join任務(wù)圖中的最后一個任務(wù)節(jié)點(diǎn)盡早開始執(zhí)行。該算法著眼于解決任務(wù)調(diào)度中被忽略的一個問題，通信信道使用沖突。在大多數(shù)任務(wù)調(diào)度算法中都是允許通信重疊的，也就是可以并行執(zhí)行通信，在安排任務(wù)的起始執(zhí)行時間時，僅考慮該任務(wù)接受最長消息需要的時間，實(shí)際任務(wù)需要的消息并沒有全部獲取就開始執(zhí)行。但是現(xiàn)

16、實(shí)中的并行計(jì)算系統(tǒng)處理器在接受發(fā)送消息時是串行進(jìn)新的，所以傳統(tǒng)調(diào)度算法和實(shí)際計(jì)算環(huán)境并不相同。為了解決這個問題作者提出了TAS_FJ來解決實(shí)際通信信道占用問題，并且力圖使得處理器的消耗量最小。邱衛(wèi)東、陳燕等人以提高現(xiàn)有啟發(fā)式算法的性能為出發(fā)點(diǎn)，提出了一個異構(gòu)分布式系統(tǒng)的動態(tài)BLevel優(yōu)先算法36。該算法選擇就緒任務(wù)中動態(tài)BLevel值最大的任務(wù)，考慮任務(wù)之間的依賴關(guān)系，將其劃分到完成時間最早的處理器上。如果超過一個處理器具有相同的最早完成時間，則將任務(wù)分配到利用率最低的處理器上執(zhí)行，以降低任務(wù)調(diào)度長度。清華大學(xué)的石威、鄭緯民教授等對相關(guān)任務(wù)圖的表調(diào)度算法進(jìn)行了深入研究，分析了現(xiàn)有經(jīng)典表調(diào)度算

17、法中存在的不足。在此基礎(chǔ)上，提出了一種均衡動態(tài)關(guān)鍵路徑算法27。該算法綜合考慮了關(guān)鍵路徑節(jié)點(diǎn)和非關(guān)鍵路徑節(jié)點(diǎn)的優(yōu)先級，在調(diào)度過程中采用動態(tài)計(jì)算關(guān)鍵路徑長度的方法，優(yōu)先調(diào)度影響調(diào)度長度最大的任務(wù)，最終縮短了整個任務(wù)圖的總調(diào)度長度。華中科技大學(xué)何琨、趙勇對分布式并行系統(tǒng)中有向無回路圖的靜態(tài)任務(wù)調(diào)度問題，以使調(diào)度長度最短為主要目標(biāo)、減少資源數(shù)目為次要目標(biāo)，提出了一種基于任務(wù)復(fù)制的分簇與調(diào)度算法動態(tài)關(guān)鍵前驅(qū)算法DCP31。DCP算法將任務(wù)復(fù)制、分簇與優(yōu)先級列表方法結(jié)合起來，采用一種新的選擇策略來定義待復(fù)制的重要祖先集。哈爾賓工程大學(xué)的李靜梅、孫冬微、吳艷霞針對現(xiàn)有任務(wù)調(diào)度算法優(yōu)先級選取過于單一所產(chǎn)生局

18、部較優(yōu)調(diào)度結(jié)果的問題，從全局較優(yōu)出發(fā)，提出一種先分層后分支決定優(yōu)先級的靜態(tài)任務(wù)調(diào)度算法HGCOTS算法42。該算法考慮了任務(wù)間較大的通信開銷和冗余任務(wù)對異構(gòu)CMP任務(wù)調(diào)度效率的影響，通過綜合區(qū)間插入和任務(wù)復(fù)制技術(shù)最大限度地降低了任務(wù)間的通信開銷，對冗余任務(wù)進(jìn)行刪除，明顯提高了任務(wù)調(diào)度效率。湖南大學(xué)的徐雨明、李肯立通過結(jié)合傳統(tǒng)啟發(fā)式算法HEFT和遺傳算法（GA），提出了一種多優(yōu)先隊(duì)列遺傳算法（MPQGA）43，克服了各自算法的缺點(diǎn)。在建立初始種群時，利用多個優(yōu)先隊(duì)列使得初始種群能夠在解空間內(nèi)均勻分布。通過精心設(shè)計(jì)交叉、編譯、選擇等操作，使算法跳出局部最優(yōu)解。三、節(jié)能調(diào)度研究現(xiàn)狀由于功耗對于嵌入式

19、系統(tǒng)的重要性，嵌入式處理器發(fā)展的同時誕生了多種能耗優(yōu)化技術(shù)。如ARM處理器所具有的不同工作模式、硬件性能監(jiān)控器、動態(tài)電壓調(diào)節(jié)、動態(tài)時鐘控制等技術(shù)都跟節(jié)能相關(guān)。為了降低能耗，在嵌入式系統(tǒng)設(shè)計(jì)各個過程中，設(shè)計(jì)人員需要從在電路級、芯片級以及系統(tǒng)級對能耗進(jìn)行優(yōu)化。而能耗優(yōu)化的層面越高，則節(jié)能效果越明顯，因此許多學(xué)者開始對高層的任務(wù)調(diào)度問題進(jìn)行研究。為解決嵌入式系統(tǒng)設(shè)計(jì)中的能耗問題，近年來興起的動態(tài)功耗管理和動態(tài)電壓縮放技術(shù)引起了業(yè)界的廣泛關(guān)注。對于非實(shí)時應(yīng)用來說，DPM技術(shù)能夠有效實(shí)現(xiàn)節(jié)能，但由于DPM是將不使用的模塊掛起以實(shí)現(xiàn)節(jié)能，而實(shí)時系統(tǒng)在運(yùn)行過程中有許多不確定性，從而不能很好地發(fā)揮節(jié)能效果。因

20、而，對于實(shí)時性有較高需求的應(yīng)用多采用DVS技術(shù)，由于電壓調(diào)節(jié)過程通常也會影響到處理器頻率，所以也有人稱之為動態(tài)電壓/頻率縮放(Dynamic Voltage/Frequency Scaling, DVFS)技術(shù)，許多流行的低功耗處理器都支持該節(jié)能技術(shù)。如，IBM公司的PowerPC、Intel公司的Xscale以及Transmeta公司的Crusoe等。DVS技術(shù)通過實(shí)時改變處理器單元的電壓和頻率來降低系統(tǒng)功耗。然而系統(tǒng)頻率降低導(dǎo)致任務(wù)執(zhí)行時間變長，可能錯過任務(wù)的截止期。因而，在電壓縮放過程中，需要設(shè)計(jì)適當(dāng)?shù)恼{(diào)度算法，在不影響系統(tǒng)性能的情況下對能耗進(jìn)行優(yōu)化。DVS技術(shù)的本身是通過犧牲系統(tǒng)性能用

21、來換取功耗的降低，本質(zhì)上算作一種硬件節(jié)能技術(shù)，需要在軟件層面上通過配置處理器的電壓級別，使用在保證系統(tǒng)實(shí)時性的同時最大限度地實(shí)現(xiàn)功耗優(yōu)化。通常情況下，處理器電壓并不能聯(lián)系變化，只具有幾個離散的電壓值。在具有離散電壓級別的異構(gòu)多處理器系統(tǒng)下對關(guān)聯(lián)任務(wù)進(jìn)行節(jié)能調(diào)度已被證明屬于NP難問題，通常采用啟發(fā)式算法進(jìn)行求解44?，F(xiàn)今，在異構(gòu)多處理器系統(tǒng)上進(jìn)行節(jié)能調(diào)度算法研究得到了國內(nèi)外研究者的廣泛關(guān)注。目前，針對多處理器系統(tǒng)的實(shí)時低功耗調(diào)度算法的研究越來越受到人們的重視。針對同構(gòu)多處理器系統(tǒng)的節(jié)能問題，許多研究者對其展開了研究。在文獻(xiàn)45中，作者提出了一種面向軟實(shí)時任務(wù)的節(jié)能調(diào)度算法。該算法首先計(jì)算每個任務(wù)

22、的松弛時間，然后采用全局DVS技術(shù)，在松弛時間內(nèi)對片上多處理器的電壓進(jìn)行動態(tài)調(diào)節(jié)，從而在滿足任務(wù)的截止期前提下降低內(nèi)核計(jì)算速度，以實(shí)現(xiàn)系統(tǒng)節(jié)能的目的。文獻(xiàn)46通過采用性能計(jì)數(shù)器獲取多處理器的功耗參數(shù)，再根據(jù)這些參數(shù)來決定是執(zhí)行還是掛起任務(wù)，使系統(tǒng)的功耗始終處于閾值范圍內(nèi)，也是一種實(shí)時任務(wù)節(jié)能調(diào)度方法。然而，這些算法都是針對軟實(shí)時任務(wù)而設(shè)計(jì)，無法保證硬實(shí)時任務(wù)的完成時間，從而難以在硬實(shí)時系統(tǒng)上應(yīng)用。文獻(xiàn)47假定同構(gòu)多處理器片上系統(tǒng)中各個核的運(yùn)行電壓相同，采用全局DVS技術(shù)和EDF算法對各個核的電壓進(jìn)行同時調(diào)節(jié)，給出了一種靜態(tài)DVS啟發(fā)式節(jié)能調(diào)度算法。但是該算法忽略了各處理器核之間的電壓差異，從而

23、難以取得最佳的節(jié)能效果。文獻(xiàn)48對節(jié)能調(diào)度算法進(jìn)行了總結(jié)分析，文中認(rèn)為，對于多處理器系統(tǒng)，沒有通用的節(jié)能算法可以針對各種情形，不同算法有其特定的適用范圍和應(yīng)用環(huán)境。在某些情況下能取得很好節(jié)能效果的算法，在其它情況下可能比不考慮節(jié)能的調(diào)度算法需要的能耗更大。對于異構(gòu)多處理器系統(tǒng)來說，各個核之間的指令集不同，存在性能和結(jié)構(gòu)上的差異性。異構(gòu)多處理器系統(tǒng)的各個處理器核是異構(gòu)的，所以需要先對任務(wù)進(jìn)行劃分，將任務(wù)分配到各個處理器核上，然后再對分配到各處理器核上的任務(wù)隊(duì)列進(jìn)行調(diào)度。在任務(wù)劃分之后，任務(wù)的調(diào)度策略跟單處理器上存在一定的類似，可以借鑒對單處理器的一些研究成果進(jìn)行多處理器進(jìn)行任務(wù)調(diào)度，但任務(wù)之間的

24、關(guān)聯(lián)性使得多處理器上的任務(wù)調(diào)度難度大大增加。在異構(gòu)多處理器系統(tǒng)環(huán)境下，利用DVS技術(shù)對具有依賴任務(wù)集進(jìn)行節(jié)能調(diào)度是NP難問題，難以在多項(xiàng)式時間內(nèi)求取最優(yōu)解。文獻(xiàn)49將電壓縮放問題表述為一個整數(shù)規(guī)劃問題，通過求解該問題實(shí)現(xiàn)處理器能耗最優(yōu)。Leung等人在文獻(xiàn)50中將節(jié)能調(diào)度中的任務(wù)劃分、調(diào)度以及電壓縮放問題抽象成一個混合的整數(shù)非線性規(guī)劃問題(Mixed Integer Nonlinear Programming , MINLP)加以解決，首先給出一個目標(biāo)函數(shù)，然后在各種限制條件下下求解目標(biāo)函數(shù)的最小值，從而獲得系統(tǒng)最低能耗。Luo等人提出了一種同時調(diào)度多速率周期任務(wù)及非周期任務(wù)的能量感知算法51

25、。美國加州大學(xué)歐文分校的Gorjiara.B等人提出了一種快速啟發(fā)式算法52；作者隨后在文獻(xiàn)53中結(jié)合隨機(jī)算法及能量梯度技術(shù)來同時解決松弛時間片的分配及任務(wù)調(diào)度問題；其最新相關(guān)工作在文獻(xiàn)54中給出，根據(jù)任務(wù)的能量梯度和執(zhí)行時間計(jì)算優(yōu)先級，然后在優(yōu)先級指導(dǎo)下進(jìn)行隨機(jī)調(diào)度。Gruian等提出了一種基于優(yōu)先級的列表調(diào)度算法55。Yanhong Liu提出了一種基于關(guān)鍵路徑分析的任務(wù)調(diào)度和壓縮放策略56。英國南安普頓大學(xué)的Marcus.T等人持續(xù)在多處理器節(jié)能調(diào)度方面進(jìn)行研究，其在文獻(xiàn)57中將傳統(tǒng)遺傳算法和列表調(diào)度策略相結(jié)合，提出遺傳列表調(diào)度算法來確定任務(wù)的執(zhí)行順序，結(jié)合作者在文獻(xiàn)58中提出的動態(tài)電壓

26、縮放算法完成異構(gòu)多處理順環(huán)境下的節(jié)能調(diào)度。V. Kianzad等在文獻(xiàn)59中提出了一種融合任務(wù)分配、調(diào)度和能量管理(Combined Assignment, Scheduling, and PowER management，CASPER)的調(diào)度框架，CASPER調(diào)度框架采用遺傳算法，將任務(wù)劃分、調(diào)度和電壓縮放三個步驟整合到一個單循環(huán)優(yōu)化迭代當(dāng)中。 在文獻(xiàn)60中，作者首先進(jìn)行優(yōu)先級初始分配，然后采用模擬退火算法對任務(wù)執(zhí)行順序進(jìn)一步優(yōu)化，最后基于任務(wù)時效性和能量的變化率，采用時間片分配算法對處理器進(jìn)行動態(tài)電壓縮放。文獻(xiàn)61認(rèn)為漏極功耗是異構(gòu)多處理器系統(tǒng)中主要能耗來源，采用DVS技術(shù)和處理器休眠技術(shù)

27、提出一系列針對軟實(shí)時任務(wù)的啟發(fā)式節(jié)能調(diào)度算法。但是算法沒有考慮硬實(shí)時任務(wù)，具有一定局限性。參考文獻(xiàn)：1 Liu C, Layland J. Scheduling algorithms for multiprogramming in a hard real-time environmentJ.Journal of the ACM, 1973,20 (1): 46-61.2 Sanjoy Baruah. Feasibility analysis of preemptive real-time systems upon heterogeneous multiprocessor platformsC.

28、 In: Proc of the 25th IEEE International Real-Time Systems Symposium. Lisbon, Portugal: Computer Society Press, 2004, 37-46.3 Giuseppe Lipari, Sanjoy K Baruah. Efficient scheduling of Real- Time Multi-Task Applications in Dynamic systemsC. In: Proceedings of the 6th IEEE Real Time Technology and App

29、lications Symposium, 2000, 166-175.4 Haluk Topcuoglu, Salim Hariri , Min-You Wu. Performance-Effective and Low- Complexity Task Scheduling for Heterogeneous ComputingJ. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274.5 Sanjoy Baruah. Task partitioning upon heterogeneous m

30、ultiprocessor platformC. In Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium, 2004.6 Sanjoy Baruah. Feasibility analysis of preemptive real-time systems upon heterogeneous multiprocessor platformsC. In Proceedings of the 25th IEEE International Real-Time Syst

31、ems Symposium, Dec. 2004: 37-46.7 Sanjoy Baruah, Nathan Fisher. The Partitioned Multiprocessor Scheduling of Deadline-Constrained Sporadic Task SystemsJ. IEEE Transactions on Computers, July 2006, 55(7): 918-923.8 Haluk Topcuoglu, Salim Hariri, Min-You Wu. Task Scheduling Algorithms for Heterogeneou

32、s ProcessorsJ. Proceedings of the Heterogeneous Computing Workshop,HCW,1999:3-14P.9 TaoYang, APostolos Gerasoulis. DSC: Scheduling Parallel Tasks on an Unbounded Number of ProeessorsJ. IEEE Transactions on Parallel and Distributed Systems, 1994,5(9):951-967P.10 Luiz F.Bittencourt, Rizos Sakellariou,

33、 Edmundo R.M.Madeira. DAG Scheduling Using a Lookahead Variant of the Heterogeneous Earliest Finish Time AlgorithmC.2010 18th Euromicro Conferenee on Parallel, Distributed and Network based Proeessing,2010:27-34.11 Y.Kwok and I. Ahmad, Benchmarking the Task Graph Scheduling AlgorithmsC, Proceedings

34、of International Parallel Processing Symposium, Florida,U.S.A. April 1998, pp. 531-537.12 Tracy D. Braunt, Howard Jay Siegel, Noah Beck, Ladislau L. Boloni, Muthucumaru Maheswarans. A Comparison Study of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed

35、 Computing SystemsJ. Purdue University School of Electrical and Computer Engineering Technical Report. 2000:TR- ECE 00-4.13 Chi Xing, Xudong Chai, Qi Wang, Yang Chen, Li Tan. Simulation Job Scheduling on Clusters with Heterogeneous Scheduling SystemsJ. AsiaSim 2013. 2013, pp 403-408.14 Jinghui Zhang

36、, Junzhou Luo, Fang Dong. Scheduling Parallel Task Graphs on non-dedicated heterogeneous multicluster platform with Moldable Task DuplicationC. Computer Supported Cooperative Work in Design (CSCWD), 2013 IEEE 17th International Conference on. June 2013, 313-318.15 Humphrey, John, Spagnoli, Kyle. Sch

37、eduling Operations for Massive Heterogeneous ClustersJ. NASA Tech Briefs, July 2013:33-34.16 David Koufaty, Dheeraj Reddy, Scott Hahn, Bias scheduling in heterogeneous multi-core architecturesC. EuroSys '10 Proceedings of the 5th European conference on Computer systems table of contents. 2010:12

38、5-138.17 Starke, R.A, de Oliveira, R.S. A Heterogeneous Preemptive and Non-preemptive Scheduling Approach for Real-Time Systems on MultiprocessorsC. Critical Embedded Systems (CBSEC), 2012 Second Brazilian Conference on. 20-25 May 2012:70-75.18 Li Wang, Jing Liu, Jingtong Hu, Qingfeng Zhuge, Duo Liu

39、, Edwin H. -M. Sha. Efficient Task Assignment on Heterogeneous Multicore Systems Considering Communication OverheadC. 12th International Conference, ICA3PP 2012, Fukuoka, Japan, September 4-7, 2012, Proceedings, Part I.19 Lina Sawalha, Ronald D. Barnes. Phase-based scheduling and thread migration fo

40、r heterogeneous multicore processorsC. PACT '12 Proceedings of the 21st international conference on Parallel architectures and compilation techniques. 2012:493-494.20 Ahmad I, Kwok Y K. On exploiting task duplication in parallel program schedulingJ. IEEE Trans. Parallel and Distributed Systems,

41、1998, 9(9): 872-892. 21 Bansal S, Kumar P, Singh K. Dealing with heterogeneity through limited duplication for scheduling precedence constrained task graphsJ. Parallel and Distributed Computing , 2005, 65(6): 479-491.22 Shin K, Cha M, Jang M, et al. Task scheduling algorithm using minimized duplicat

42、ions in homogeneous systemsJ. Parallel and Distributed Computing, 2008, 68(8): 1146-1156. 23 Tarek F, Abdelzaher, Kang G Shin. Period-Based partitioning and assignment for large Real-Time ApplicationsJ. IEEE Transactions on Computers, Jan. 2000, 49(1): 81-87.24 Dutot P.Complexity of master-slave tas

43、king on heterogeneoustreesJ.EuropeanJournal on Operational Research, 2005, 164(3): 690-695.25 鄭凱.對數(shù)據(jù)在異構(gòu)多核處理器模擬器中進(jìn)行任務(wù)劃分的研究D.上海交通大學(xué)碩士學(xué)位論文.2008:1-1226 吳佳駿.多核多線程處理器上任務(wù)調(diào)度技術(shù)研究D.中國科學(xué)院計(jì)算技術(shù)研究所博士學(xué)位論文.2006:4-1727 石威,鄭緯民.相關(guān)任務(wù)圖的均衡動態(tài)關(guān)鍵路徑調(diào)度算法J.計(jì)算機(jī)學(xué)報(bào).2001,24(9):l-828 鐘求喜,謝濤,陳火旺.基于遺傳算法的任務(wù)分配與調(diào)度J.計(jì)算機(jī)研究與發(fā)展.2000,37(10):

44、1198-120329 李慶華,韓建軍,AbbasA.Essa.同構(gòu)計(jì)算環(huán)境中一種快速有效的靜態(tài)任務(wù)調(diào)度算法J.計(jì)算機(jī)研究與發(fā)展.2005,42(1):118-12530 劉軼,張聽,李鶴,錢德沛一種面向多核處理器并行系統(tǒng)的啟發(fā)式任務(wù)分配算法J.計(jì)算機(jī)研究與發(fā)展.2009,46(6):1058-106431 何琨,趙勇,黃文奇.基于任務(wù)復(fù)制的分簇與調(diào)度算法J.計(jì)算機(jī)學(xué)報(bào).2008,31(5):734-73932 王永炎,王強(qiáng),王宏安,金宏,戴國忠.基于優(yōu)先級表的實(shí)時調(diào)度算法及其實(shí)現(xiàn)J.軟件學(xué)報(bào).2004,15(3):361-36933 梁洪濤,袁由光,方明一種基于任務(wù)全局遷移的靜態(tài)調(diào)度算法J.

45、計(jì)算機(jī)研究與發(fā)展.2006,43(5):797-80434 劉振英,方濱興,姜譽(yù),張毅,趙宏. 一個調(diào)度 Fork-Join 任務(wù)圖的新算法J. 軟件學(xué)報(bào), 2002, 13(4):693-69735 章軍,馮秀山,韓冀中,韓承德. 總線互連機(jī)群系統(tǒng)上的靜態(tài)任務(wù)調(diào)度J. 計(jì)算機(jī)研究與發(fā)展. 1999,36(7):805-81236 邱衛(wèi)東,陳燕,李潔萍,彭澄廉. 一種實(shí)時異構(gòu)嵌入式系統(tǒng)的任務(wù)調(diào)度算法J. 軟件學(xué)報(bào) Vol.15,No.4,200437 李仁發(fā), 劉彥, 徐成. 多處理器片上系統(tǒng)任務(wù)調(diào)度研究進(jìn)展評述J. 計(jì)算機(jī)研究與發(fā)展. 2008, 45(9)：1620-1629.38 江維,

46、 常政威, 桑楠等. 安全和能量關(guān)鍵的分布式協(xié)作任務(wù)調(diào)度J.電子學(xué)報(bào), 2011, 39(4): 757-762.39 肖鵬,胡志剛. 截止時間約束下獨(dú)立網(wǎng)格任務(wù)的協(xié)同調(diào)度模型J.電子學(xué)報(bào), 2011, 39(8): 1852-1857.40 劉衛(wèi)寧,高龍. 異構(gòu)云中面向集群負(fù)載均衡的任務(wù)調(diào)度策略J. 計(jì)算機(jī)應(yīng)用, 2013, 33(8).41 童小念, 舒萬能, 李子茂. 異構(gòu)多處理機(jī)系統(tǒng)的負(fù)載均衡與任務(wù)調(diào)度J. 光學(xué)精密工程. 2007, 15(12).42 李靜梅，孫冬微，吳艷霞. 一種全局較優(yōu)的靜態(tài)任務(wù)調(diào)度算法J. 計(jì)算機(jī)應(yīng)用研究. 2014, 31(4)：1027-1030.43 Y

47、uming Xu, Kenli Li, Jingtong Hu, Keqin Li. A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queuesJ. Information Sciences, 2014, Volume 270(20): 255287.44 ANDREI A, SCHMITZ M, ELES P, et al. Overhead-conscious voltage selection for dynamic and leakag

48、e energy reduction of time-constrained systemsC. In Proc. Design, Automation and Test in Europe Conference and Exposition, 2005: 518-523.45 Bautista D,Sahuquillo J,Hassan H,et al.A Simple Power-Aware Schecluling for Multicore Systems When Running Real-Time ApplieationsC. In Proceedings of the 22nd I

49、EEE /ACM Int1 Parallel and Distributed Processing Symp, 2008: 1-7.46 Singh K, Bhadauria M, McKee S A. Real Time Power Estimation and Thread Scheduling via Performance CountersJ. ACM SIGARCH Computer Architecture News,2009, 37(2):46-55.47 Huang Xin,Li KenLi,Li RenFa.A Energy Efficient Scheduling Base

50、 on Dynamic Voltage and Frequency Scaling for Multi-Core Embedded Real-Time SystemC. In Proceedings of ICA3PP09, 2009: 137-145.48 Rotem E, Mendelson A,Ginosar R,et al.Multiple Clock and Voltage Domains for Chip Multi ProcessorsC. In Proceedings of ACM MICRO09, 2009: 459-468.49 Zhang Y, Hu X, Chen D

51、Z. Task Scheduling and Voltage Selection for Energy MinimizationC. In Proceedings of the 39th Design Automation Conference, June 2002: 183-188.50 Leung L F, Tsui C Y, Ki WH. Minimizing Energy Consumption of Multiple Processors-Core Systems with Simultaneous Task Allocation, Scheduling and Voltage As

52、signmentC. In Proceedings of Asia and South Pacific Design Automation Conf., Jan. 2004: 647-652.51 Luo J, Jha N K. Power-Conscious Joint Scheduling of Periodic Task Graphs and Aperiodic Tasks in Distributed Real- time Embedded SystemsC. In Proceedings of Intl Conf. Computer-Aided Design, Nov. 2000: 357-364.52 Gorjiara B, Chou P, Bagherzadeh N, et al. Fast and efficient voltage scheduling by evolutionary slack distributionC. In Proceedings of Asia and South Pacific Design Automation Conference, Jan. 2004: 659-662.53 Gorjiara B, Bagherzadeh N, Chou P. An efficient vol