異構(gòu)多平臺(tái)信號(hào)處理任務(wù)調(diào)度研究

李宇東,馬金全,謝宗甫,沈小龍

(戰(zhàn)略支援部隊(duì)信息工程大學(xué) 信息系統(tǒng)工程學(xué)院,河南 鄭州 450000)

近年來(lái),無(wú)線通信和互聯(lián)網(wǎng)技術(shù)發(fā)展迅速,數(shù)據(jù)信息交換和任務(wù)處理計(jì)算的體量出現(xiàn)爆炸式增長(zhǎng),對(duì)信號(hào)處理平臺(tái)的時(shí)效性、高效性以及穩(wěn)定性等提出了更高要求,因此研發(fā)一種具有多層級(jí)、可重構(gòu)和可擴(kuò)展的多異構(gòu)處理平臺(tái)成為未來(lái)信號(hào)處理任務(wù)調(diào)度研究的重點(diǎn)。異構(gòu)多平臺(tái)信號(hào)處理(Heterogeneous Platform Signal Processing,HPSP)任務(wù)調(diào)度是一個(gè)集成了多平臺(tái)、多處理器和支持多種總線類型及數(shù)據(jù)傳輸協(xié)議的處理系統(tǒng),便于解決不同規(guī)模、型號(hào)的平臺(tái)間數(shù)據(jù)通信問(wèn)題和分布式處理規(guī)模龐大復(fù)雜的信號(hào)任務(wù)調(diào)度問(wèn)題。不同類別的信號(hào)處理平臺(tái)之間使用的處理器性能有所差異,且存在軟硬件資源耦合度大、任務(wù)移植性差等問(wèn)題,導(dǎo)致研發(fā)處理平臺(tái)周期長(zhǎng)、移植性差。

隨著認(rèn)知無(wú)線電等概念的出現(xiàn)和軟件通信架構(gòu)技術(shù)的成熟,在開(kāi)放性通用平臺(tái)上開(kāi)發(fā)可重構(gòu)、可復(fù)用、可定義的軟硬件架構(gòu)成為關(guān)注熱點(diǎn)。隨著人工智能技術(shù)的快速發(fā)展,神經(jīng)網(wǎng)絡(luò)、深度學(xué)習(xí)等人工智能調(diào)度算法在異構(gòu)系統(tǒng)中也得到了廣泛應(yīng)用。例如針對(duì)云計(jì)算場(chǎng)景中數(shù)據(jù)量大、情況復(fù)雜的調(diào)度問(wèn)題,利用深度強(qiáng)化學(xué)習(xí)方法有效降低了作業(yè)的整體完工時(shí)間[1]。針對(duì)算法適應(yīng)度低、解集大的情況,可利用梯度策略方法來(lái)解決該問(wèn)題[2]。隨著任務(wù)智能感知和加卸載技術(shù)的發(fā)展,多平臺(tái)協(xié)同處理任務(wù)調(diào)度問(wèn)題更高效、智能。例如為解決用戶需求、調(diào)度速度等因素進(jìn)行差異化處理任務(wù)調(diào)度,可將資源感知和任務(wù)調(diào)度相結(jié)合[3]。針對(duì)調(diào)度方法中難以準(zhǔn)確預(yù)測(cè)執(zhí)行時(shí)間、難以同時(shí)滿足任務(wù)關(guān)聯(lián)和全局優(yōu)先級(jí)的情況,可利用在云計(jì)算調(diào)度中加入任務(wù)感知的方法來(lái)解決[4]。單一的任務(wù)調(diào)度算法雖然能滿足一般的調(diào)度需求,但無(wú)法滿足任務(wù)數(shù)多、計(jì)算量大、復(fù)雜度高等情況的需求,而混合調(diào)度算法可較好地滿足上述情況需求,因此基于任務(wù)感知的混合算法-感知全局任務(wù)動(dòng)態(tài)分配處理任務(wù)是未來(lái)研究發(fā)展的重點(diǎn),本文主要對(duì)異構(gòu)多平臺(tái)信號(hào)處理調(diào)度進(jìn)行研究和討論。

1 HPSP調(diào)度策略

1.1 HPSP平臺(tái)

異構(gòu)多平臺(tái)信號(hào)處理系統(tǒng)對(duì)軟硬件體系架構(gòu)要求較高,通常通過(guò)構(gòu)建硬件體系和軟件體系對(duì)處理系統(tǒng)資源進(jìn)行全局管理,方便定義和擴(kuò)展。硬件體系架構(gòu)如圖1所示,VPX (VITA 46)、ATCA(Advanced Telecom Computing Architecture)和CPCI(Compact PCI)等不同的總線標(biāo)準(zhǔn)和通信協(xié)議定義的平臺(tái)構(gòu)成硬件資源架構(gòu),平臺(tái)集成高密度的標(biāo)準(zhǔn)板卡和機(jī)箱,在板卡上搭載FPGA(Field Programmable Gate Array)、CPU(Central Processing Unit)、DSP(Digital Signal Processing)和GPU(Graphics Processing Unit)等各類高性能處理器,通過(guò)互聯(lián)網(wǎng)絡(luò)和制定的通信協(xié)議實(shí)現(xiàn)不同平臺(tái)間的交互操作?；谟布亩鄠€(gè)不同域互聯(lián)形成系統(tǒng)域,每個(gè)平臺(tái)內(nèi)包含了多個(gè)板卡,板卡內(nèi)嵌入不同處理速度、結(jié)構(gòu)和功能的高性能處理器,按照其異構(gòu)性、差異性、多樣性以及層級(jí)性的特點(diǎn),異構(gòu)處理平臺(tái)可劃分為系統(tǒng)域、域、平臺(tái)、板卡和處理器[5]。

軟件架構(gòu)如圖2所示,由硬件資源、操作系統(tǒng)、驅(qū)動(dòng)平臺(tái)、核心架構(gòu)、管理資源和應(yīng)用層構(gòu)成。在硬件平臺(tái)層采用了兼容性強(qiáng)、可擴(kuò)展的硬件架構(gòu)ATCA(包括CPU、GPU、DSP和FPGA等處理器)和VPX等高速串行總線[6]。操作系統(tǒng)層和驅(qū)動(dòng)抽象層為上層提供統(tǒng)一接口,達(dá)到屏蔽底層硬件之間差異的目的,體現(xiàn)層級(jí)劃分的思想。在核心框架層利用容器技術(shù)形成了統(tǒng)一、標(biāo)準(zhǔn)的任務(wù)調(diào)度模式,屏蔽不同處理器間的差異。應(yīng)用層包含雷達(dá)、短波、衛(wèi)星等多種應(yīng)用,以組件的形式進(jìn)行調(diào)度。平臺(tái)軟硬件架構(gòu)的層次型設(shè)計(jì)實(shí)現(xiàn)了平臺(tái)軟硬件解耦合,滿足組件的可移植、跨平臺(tái)操作等需求[7]。

圖2 異構(gòu)信號(hào)處理平臺(tái)軟件體系架構(gòu)Figure 2. Software architecture of heterogeneous platform signal processing

1.2 任務(wù)調(diào)度模型

任務(wù)調(diào)度模型和目標(biāo)處理環(huán)境模型在其相應(yīng)的應(yīng)用任務(wù)調(diào)度、調(diào)度算法以及調(diào)度目標(biāo)中具有重要作用[8],所以構(gòu)建合理規(guī)范的任務(wù)調(diào)度模型是設(shè)計(jì)、分析任務(wù)調(diào)度算法的基礎(chǔ),同時(shí)也為設(shè)計(jì)算法提供了一個(gè)描述準(zhǔn)確、架構(gòu)簡(jiǎn)單的任務(wù)調(diào)度模型。目前采用有向無(wú)環(huán)圖描述任務(wù)調(diào)度模型。如圖3(a)所示,每個(gè)節(jié)點(diǎn)表示一個(gè)任務(wù),每條有向邊表示任務(wù)間的通信鏈路。構(gòu)建系統(tǒng)任務(wù)調(diào)度模型[9]為G={V,E,C,L},其中,V={v1,v2,v3,…,vn}是調(diào)度處理系統(tǒng)中所有任務(wù)的集合,E={e12,e23,…,eij}表示有關(guān)聯(lián)的任務(wù)間的通信鏈路集合,eij=(vi,vj)代表任務(wù)vi和vj之間的通信邊,且vi是vj的父任務(wù),C={c1,c2,…,cn}表示任意被執(zhí)行任務(wù)計(jì)算代價(jià)集合,L(vi,vj)表示任務(wù)間通信延遲。硬件架構(gòu)用無(wú)向圖抽象為P={N,H,W,T},是一個(gè)具有4個(gè)異構(gòu)處理器的處理系統(tǒng)模型,如圖3(b)所示。其中,N是處理器集合,H為處理器特征,W為計(jì)算量,T是處理器間的通信量,如式(1)所示。任意兩個(gè)任務(wù)vi及vj被分配至同一節(jié)點(diǎn)上(即在同一處理上),通信開(kāi)銷(xiāo)Tij為0。

(a)

(1)

2 任務(wù)調(diào)度算法分類及對(duì)比分析

目前,多數(shù)任務(wù)調(diào)度算法基于異構(gòu)計(jì)算系統(tǒng)被提出,其以低成本和高效率完成大型科學(xué)應(yīng)用計(jì)算以及海量信息數(shù)據(jù)處理和服務(wù)等特點(diǎn)得到了學(xué)術(shù)界廣泛關(guān)注。無(wú)論從調(diào)度任務(wù)過(guò)程、目標(biāo)類型,還是從使用的數(shù)學(xué)模型和研究方法來(lái)看,調(diào)度方法都有諸多劃分方法,例如隨機(jī)和非隨機(jī)調(diào)度、靜態(tài)和動(dòng)態(tài)調(diào)度、無(wú)期限約束和有期限約束調(diào)度等。本文主要按調(diào)度策略對(duì)現(xiàn)有調(diào)度算法進(jìn)行分類,系統(tǒng)總結(jié)分析了各類調(diào)度算法之間的差異性、優(yōu)缺點(diǎn)等性能指標(biāo),為實(shí)際應(yīng)用和學(xué)術(shù)科研提供理論基礎(chǔ)。

2.1 調(diào)度算法分類

任務(wù)調(diào)度的難點(diǎn)主要在將待處理任務(wù)合理分配到處理平臺(tái)中的各個(gè)處理器上,即在滿足平臺(tái)資源約束條件下選擇合適的算法將到達(dá)的任務(wù)隊(duì)列進(jìn)行合理有效的映射,使平臺(tái)中的處理器均擁有高效的計(jì)算處理性能,最終完成預(yù)期的調(diào)度任務(wù)。文獻(xiàn)[10]對(duì)靜態(tài)和動(dòng)態(tài)調(diào)度間的區(qū)別做了說(shuō)明,靜態(tài)調(diào)度主要包括啟發(fā)式和引導(dǎo)隨機(jī)搜索調(diào)度,而啟發(fā)式調(diào)度方法又分為表調(diào)度、聚類調(diào)度和任務(wù)復(fù)制調(diào)度[11]。動(dòng)態(tài)任務(wù)調(diào)度方法分為傳統(tǒng)調(diào)度和智能調(diào)度,傳統(tǒng)調(diào)度方法又分為仿真方法、啟發(fā)式方法和最優(yōu)化方法。智能調(diào)度方法分為神經(jīng)網(wǎng)絡(luò)方法、智能搜索方法、專家系統(tǒng)和Multi-agent方法[12]。圖4為調(diào)度方法分類拓?fù)?體現(xiàn)了各類任務(wù)調(diào)度方法間的邏輯關(guān)系。

圖4 調(diào)度方法分類拓?fù)銯igure 4. Classification topology of scheduling methods

2.1.1 表調(diào)度方法

表調(diào)度方法是常用的啟發(fā)式調(diào)度方法之一,靜態(tài)任務(wù)調(diào)度方法是傳統(tǒng)的表調(diào)度方法,主要方法是確定具有優(yōu)先級(jí)的調(diào)度列表并逐一將任務(wù)分配至處理器,在該過(guò)程中任務(wù)的執(zhí)行順序不變。主要步驟是從調(diào)度列表中依次取出待執(zhí)行任務(wù),再將取出的任務(wù)依次分配到能夠使其執(zhí)行時(shí)間最短的處理器上。動(dòng)態(tài)表調(diào)度方法與靜態(tài)表調(diào)度方法最大的區(qū)別在于動(dòng)態(tài)表調(diào)度在每次取出調(diào)度列表中的一個(gè)任務(wù)后會(huì)重新計(jì)算各任務(wù)優(yōu)先級(jí)并形成新的調(diào)度列表。

表調(diào)度方法因步驟簡(jiǎn)單和模型復(fù)雜度低而被廣泛應(yīng)用于任務(wù)調(diào)度問(wèn)題中,但表調(diào)度方法通過(guò)優(yōu)先級(jí)調(diào)度列表遍歷所有任務(wù),因此解空間不是全局最優(yōu),且適用在處理器數(shù)量有限、異構(gòu)、全連接的系統(tǒng)中?；趩l(fā)式的表調(diào)度有HEFT(Heterogeneous Earliest Finish Time)算法[13]、ILS(Iterative List Scheduling)算法[14]、HCPT(Heterogenous Critical Parent Trees)算法[15]、FCP(Fast Critical Path)算法[16]、CIPOP算法[17]、PEFT(Parameter Efficient Fine-Tuning)算法[18]、PETS(Performance Effective Task Scheduling)算法[19]和MOPT(Minimal Optimistic Processing Time)算法[20]等。

2.1.2 基于聚類的調(diào)度方法

基于聚類的任務(wù)調(diào)度主要把任務(wù)集合中相互通信的任務(wù)(任務(wù)簇)映射到同一處理器上,以此降低任務(wù)間的通信開(kāi)銷(xiāo)。其過(guò)程主要包括兩個(gè)步驟:1)初始化調(diào)度任務(wù),將任務(wù)劃分為不同的聚類,并將聚類映射到虛擬處理器上以減少任務(wù)間的通信開(kāi)銷(xiāo);2)將每個(gè)聚類任務(wù)映射到一個(gè)處理器上。

由于聚類調(diào)度方法中是全局聚類的,所以執(zhí)行效果較好,但當(dāng)可用處理器數(shù)量小于聚類數(shù)目時(shí),方法的有效性會(huì)降低[21]。通常利用不同的合并任務(wù)簇方法來(lái)區(qū)分不同的聚類調(diào)度算法。經(jīng)典算法有CHP算法[22]、LCM(Linear Clustering Method)算法[23]、RBCA(Runtime Balance Clustering Algorithm)算法[24]、MTA算法[25]、DSC(Dominant Sequence Clustering)算法[26]和Triplet算法[27]等。

2.1.3 基于任務(wù)復(fù)制的調(diào)度方法

當(dāng)任意兩個(gè)存在通信開(kāi)銷(xiāo)的任務(wù)被映射到相同處理器時(shí),其相互間的通信開(kāi)銷(xiāo)可近似為0。因此,基于任務(wù)復(fù)制調(diào)度的方法將待執(zhí)行任務(wù)分配到同一個(gè)處理器上來(lái)降低處理器間的通信量,即通過(guò)任務(wù)復(fù)制使處理器保持滿狀態(tài)運(yùn)行,以此達(dá)到提高任務(wù)調(diào)度效率的目的。

不同任務(wù)復(fù)制算法在選擇復(fù)制的策略上有所差異,一種算法只復(fù)制直接前繼節(jié)點(diǎn)任務(wù),另一種算法復(fù)制所有可能的前繼節(jié)點(diǎn)任務(wù)。相對(duì)于其它啟發(fā)式調(diào)度方法,基于任務(wù)復(fù)制的調(diào)度算法的性能更好,但這類算法適用于處理器數(shù)量無(wú)限制的系統(tǒng),且時(shí)間復(fù)雜度較高。典型算法有LDBS算法[28]、HCPFD(Heterogeneous Critical Parents with Fast Duplicator)算法[29]、DBUS算法[30]、LHCNF算法[31]、HNPD算法[32]和TDCA(Task Duplication based Clustering Algorithm)算法[33]等。

2.1.4 引導(dǎo)隨機(jī)搜索調(diào)度方法

引導(dǎo)隨機(jī)搜索調(diào)度方法通過(guò)有指導(dǎo)的搜索獲得解決策略,即在已有結(jié)果基礎(chǔ)上結(jié)合新隨機(jī)搜索來(lái)獲取最新結(jié)果,元啟發(fā)式算法屬于該方法。在已提出算法中,遺傳算法因其可以產(chǎn)生較好的調(diào)度值被廣泛使用,但因其調(diào)度時(shí)間比其它算法高,所以有研究者使用模擬退火、蟻群以及粒子群等算法來(lái)進(jìn)行算法優(yōu)化。

引導(dǎo)隨機(jī)搜索調(diào)度方法主要在調(diào)度任務(wù)集合中通過(guò)大量迭代來(lái)尋找最優(yōu)解。相對(duì)于啟發(fā)式方法,該方法的調(diào)度質(zhì)量更高,但是解空間求解時(shí)間相對(duì)較高。為更好得到最優(yōu)解,算法中的循環(huán)架構(gòu)和適應(yīng)度函數(shù)需要合理設(shè)計(jì),且參數(shù)設(shè)置通常與任務(wù)需求相關(guān),故存在擴(kuò)展性差、解空間求解時(shí)間高等缺點(diǎn)。經(jīng)典的引導(dǎo)隨機(jī)搜索調(diào)度算法有GA(Genetic Algorithm)算法[34]、EGA-TS(Enhanced Genetic Algorithm for Task Scheduling)算法[35]、MGGS算法[36]和Greedy-Ant算法[37]等。

2.1.5 最優(yōu)化調(diào)度方法

最優(yōu)化方法的本質(zhì)是一種數(shù)學(xué)方法,其在既定約束下尋求某一指標(biāo)得到最優(yōu),主要由函數(shù)優(yōu)化和組合優(yōu)化構(gòu)成。函數(shù)優(yōu)化對(duì)象是有限區(qū)間內(nèi)的連續(xù)變量,組合優(yōu)化對(duì)象是解空間中的離散狀態(tài)。通過(guò)最優(yōu)化算法解決問(wèn)題的主要思路是建立數(shù)學(xué)模型和制定最優(yōu)解搜索策略,本質(zhì)是一種搜索規(guī)則或方法。引導(dǎo)隨機(jī)搜索調(diào)度方法是一種最優(yōu)化方法,在某些機(jī)制基礎(chǔ)上通過(guò)一定策略或方法使最終的解符合任務(wù)需求。最優(yōu)化算法包括精確算法、個(gè)體尋優(yōu)算法、啟發(fā)式算法以及群體智能尋優(yōu)算法等。

2.1.6 仿真方法

仿真方法是在難以開(kāi)展理論分析情況下,通過(guò)對(duì)復(fù)雜多變的實(shí)際問(wèn)題構(gòu)建模型實(shí)現(xiàn)來(lái)簡(jiǎn)化調(diào)度問(wèn)題。目前采用仿真方法解決調(diào)度問(wèn)題主要有:1)設(shè)置不同參數(shù)進(jìn)行對(duì)比實(shí)驗(yàn),以便在調(diào)度問(wèn)題中做出最優(yōu)選擇,使結(jié)果具有更高的可信度。文獻(xiàn)[38]對(duì)仿真實(shí)驗(yàn)中各類參數(shù)的設(shè)置區(qū)間做了詳盡說(shuō)明;2)在仿真環(huán)境使用某類方法,通過(guò)評(píng)估同一環(huán)境不同方法得到各種方法的使用范圍等。文獻(xiàn)[39]利用仿真方法產(chǎn)生訓(xùn)練數(shù)據(jù)用于神經(jīng)網(wǎng)絡(luò)訓(xùn)練,并將模型用于動(dòng)態(tài)調(diào)度問(wèn)題。

由于仿真方法在構(gòu)建模型時(shí)做了較多假設(shè)和近似,因此仿真結(jié)果因模型選擇的不同而產(chǎn)生不同結(jié)果,較難得到一個(gè)一致的結(jié)論。但是對(duì)于缺乏有效理論分析的調(diào)度問(wèn)題,通過(guò)仿真方法可以得到較好的結(jié)果。

2.1.7 智能調(diào)度方法

隨著近年來(lái)人工智能的迅速發(fā)展,智能調(diào)度方法越來(lái)越受到開(kāi)發(fā)者的青睞,專家系統(tǒng)、人工神經(jīng)網(wǎng)絡(luò)、智能搜索等方法相繼被提出和使用。專家系統(tǒng)是把已有的領(lǐng)域知識(shí)和環(huán)境約束條件總結(jié)為知識(shí)庫(kù),再根據(jù)具體問(wèn)題從知識(shí)庫(kù)中生成調(diào)度方法,且能對(duì)突發(fā)情況采取對(duì)應(yīng)措施。比較成熟的專家系統(tǒng)有ISIS(Intermediate System to Intermediate System)[40]、OPIS(Orebody Position Indicating System in fault Simulation)[41]、SONIA[42]和OPAL[43]等。人工神經(jīng)網(wǎng)絡(luò)方法通過(guò)構(gòu)造訓(xùn)練模型、訓(xùn)練模型數(shù)據(jù)來(lái)解決調(diào)度問(wèn)題。例如文獻(xiàn)[44]在構(gòu)建分派功率和調(diào)度使用模型上結(jié)合圖神經(jīng)網(wǎng)絡(luò),解決了計(jì)算開(kāi)銷(xiāo)大和網(wǎng)絡(luò)歷史數(shù)據(jù)利率低的問(wèn)題。文獻(xiàn)[45]利用長(zhǎng)短期記憶性神經(jīng)網(wǎng)絡(luò)解決了任務(wù)調(diào)度中處理效率低、分配不合理和資源均衡差的問(wèn)題。智能搜索是基于人工智能的相關(guān)算法被提出。例如文獻(xiàn)[1]利用深度強(qiáng)化學(xué)習(xí)縮短調(diào)度整體完成時(shí)間,提出了智能的作業(yè)調(diào)度方法。文獻(xiàn)[46]為解決集群利用資源率和QoS保證率,利用深度學(xué)習(xí)實(shí)現(xiàn)了任務(wù)動(dòng)態(tài)調(diào)度。

2.1.8 混合調(diào)度方法

混合調(diào)度方法是通過(guò)兩種或多種調(diào)度算法相結(jié)合的方式,結(jié)合各自算法優(yōu)勢(shì)來(lái)解決任務(wù)調(diào)度問(wèn)題。其動(dòng)態(tài)資源分配、智能調(diào)度決策、廣泛的應(yīng)用場(chǎng)景等特性能夠較好地滿足異構(gòu)處理平臺(tái)對(duì)任務(wù)調(diào)度時(shí)效性、高效性和準(zhǔn)確性的要求,為解決調(diào)度問(wèn)題提供了新思路。文獻(xiàn)[4]通過(guò)預(yù)測(cè)任務(wù)結(jié)束時(shí)間實(shí)現(xiàn)資源感知,從而達(dá)到任務(wù)的動(dòng)態(tài)調(diào)度,提高了效率,縮短了調(diào)度時(shí)間。文獻(xiàn)[3]通過(guò)動(dòng)態(tài)任務(wù)插槽和區(qū)分?jǐn)?shù)據(jù)有效值實(shí)現(xiàn)處理調(diào)度差異化數(shù)據(jù)。文獻(xiàn)[47]通過(guò)將啟發(fā)式算法與強(qiáng)化學(xué)習(xí)相結(jié)合提出了異構(gòu)系統(tǒng)中基于Q-learning的智能蟻群調(diào)度算法,提高了異構(gòu)系統(tǒng)任務(wù)調(diào)度的效率且降低了時(shí)間成本。

本文雖然對(duì)調(diào)度方法進(jìn)行了明確分類,但有較多方法交叉重疊,例如一些智能搜索方法結(jié)合了引導(dǎo)隨機(jī)搜索方法,一些最優(yōu)化方法結(jié)合了智能搜索和元啟發(fā)式方法,一些基于任務(wù)復(fù)制方法結(jié)合了聚類方法等,所以在遇到具體調(diào)度問(wèn)題時(shí)需具體分析,切實(shí)構(gòu)建合適的問(wèn)題模型,選取最佳的調(diào)度方法。

2.2 調(diào)度算法對(duì)比分析

異構(gòu)多平臺(tái)信號(hào)處理系統(tǒng)的難點(diǎn)是動(dòng)態(tài)分配任務(wù)和提高系統(tǒng)的實(shí)時(shí)性。已提出的各類算法在任務(wù)調(diào)度中雖然都能起到一定作用,但是單一的調(diào)度算法本身存在的缺點(diǎn)不能滿足平臺(tái)對(duì)調(diào)度任務(wù)高效性和動(dòng)態(tài)性的要求。本文根據(jù)異構(gòu)平臺(tái)任務(wù)調(diào)度的最新研究提出了基于任務(wù)感知的混合調(diào)度算法,即在任務(wù)資源感知的狀態(tài)下(任務(wù)智能加卸載),首先通過(guò)靜態(tài)調(diào)度形成任務(wù)劃分的初始方案,然后根據(jù)異構(gòu)平臺(tái)接收處理任務(wù)的變化進(jìn)行動(dòng)態(tài)調(diào)整。表1總結(jié)了啟發(fā)式算法(Heuristic Algorithm,HA)、元啟發(fā)式算法(Meta Heuristic Algorithm,MHA)、人工智能算法(Artificial Intelligence Algorithm,AIA)和基于任務(wù)感知的混合調(diào)度算法(Task-aware Hybrid Algorithm,THA),對(duì)比分析了它們的優(yōu)化目標(biāo)、調(diào)度類型和應(yīng)用場(chǎng)景等指標(biāo)參數(shù)。

表1 典型任務(wù)調(diào)度算法總結(jié)

研究發(fā)現(xiàn),HA、MHA、AIA和THA等算法能夠應(yīng)用于異構(gòu)系統(tǒng)、分布式和云計(jì)算的調(diào)度問(wèn)題。

HA算法屬于離線算法,多用于靜態(tài)和周期任務(wù)調(diào)度,能夠預(yù)先制定好調(diào)度任務(wù)列表,減少了任務(wù)調(diào)度過(guò)程中的開(kāi)銷(xiāo)。相比于HA算法,MHA算法調(diào)度質(zhì)量更高,提高了調(diào)度效率,但HA算法的調(diào)度開(kāi)銷(xiāo)比MHA算法低。AIA算法基于人工智能算法所提出,可以簡(jiǎn)化復(fù)雜未知的任務(wù)模型,不易陷入局部最優(yōu)解,但數(shù)據(jù)模型訓(xùn)練耗時(shí)較長(zhǎng)且不同模型對(duì)調(diào)度結(jié)果影響較大。THA算法通過(guò)智能決策分配調(diào)度任務(wù)到合適的處理器上,實(shí)現(xiàn)了調(diào)度任務(wù)的動(dòng)態(tài)分配,提高了調(diào)度系統(tǒng)的效率。研究發(fā)現(xiàn),HA、MHA、AIA算法無(wú)論是在應(yīng)用場(chǎng)景還是性能功耗方面都存在不足,而THA算法使異構(gòu)處理平臺(tái)不再局限于單目標(biāo)、單性能的任務(wù)調(diào)度,可以通過(guò)智能感知資源并分配到合適的處理器上進(jìn)行調(diào)度,實(shí)現(xiàn)了資源的動(dòng)態(tài)分配。表2對(duì)以上4類調(diào)度算法的優(yōu)缺點(diǎn)做了總結(jié)歸納,給出了各自的適用場(chǎng)景。

表2 HA、MHA、AIA和THA算法對(duì)比分析

綜合以上對(duì)典型算法的研究以及表1和表2對(duì)各類算法的對(duì)比分析發(fā)現(xiàn),在近年來(lái)提出的各類調(diào)度算法中,基于任務(wù)感知的混合調(diào)度算法可以得到更好的優(yōu)化結(jié)果,具有更廣的應(yīng)用場(chǎng)景?；旌险{(diào)度算法通過(guò)對(duì)任務(wù)資源的動(dòng)態(tài)管理和智能策略,能夠滿足異構(gòu)處理平臺(tái)對(duì)任務(wù)調(diào)度靈活性、實(shí)時(shí)性、差異性以及準(zhǔn)確性要求。目前,此類算法的研究還不夠成熟,將此類算法應(yīng)用到異構(gòu)多平臺(tái)信號(hào)處理任務(wù)調(diào)度中是下一步的研究方向。

3 未來(lái)發(fā)展方向

異構(gòu)多平臺(tái)信號(hào)處理系統(tǒng)軟、硬件架構(gòu)復(fù)雜,其異構(gòu)性、層級(jí)性和多平臺(tái)的特點(diǎn)給任務(wù)調(diào)度增加了一定的復(fù)雜度。將待調(diào)度的任務(wù)合理映射、分配到合適的異構(gòu)處理單元上從而發(fā)揮異構(gòu)單元高效穩(wěn)定的特性已成為異構(gòu)處理平臺(tái)的研究重點(diǎn),而結(jié)合能耗感知、可靠性感知、動(dòng)態(tài)通信競(jìng)爭(zhēng)以及負(fù)載均衡等應(yīng)用場(chǎng)景的任務(wù)調(diào)度給研究帶來(lái)重大挑戰(zhàn)。將復(fù)雜的處理任務(wù)按照其特征合理分配到不同硬件架構(gòu)上,滿足處理平臺(tái)高效穩(wěn)定的要求需要有效合理的任務(wù)調(diào)度算法才能實(shí)現(xiàn)。圖5分析了啟發(fā)式算法、元啟發(fā)式算法、人工智能算法和基于任務(wù)感知的混合算法從19世紀(jì)60年代至今的使用比例。最初的列表調(diào)度、基于聚簇的調(diào)度等啟發(fā)式算法適用于靜態(tài)任務(wù)調(diào)度,能夠滿足簡(jiǎn)單的調(diào)度任務(wù),但其不能按照閑置處理器資源進(jìn)行及時(shí)任務(wù)調(diào)配,靈活性差,應(yīng)用比例逐年降低。隨著遺傳、蟻群和禁忌搜索算法的出現(xiàn),元啟發(fā)式算法使用比例逐漸提高。隨著計(jì)算量、模型復(fù)雜度的日益增加和人工智能、計(jì)算機(jī)技術(shù)的發(fā)展,研究者提出了智能調(diào)度算法并逐漸得到廣泛應(yīng)用,但因其訓(xùn)練模型的選擇對(duì)結(jié)果影響較大且訓(xùn)練時(shí)間較長(zhǎng)、結(jié)果不可預(yù)測(cè)等因素,不能滿足不同應(yīng)用場(chǎng)景對(duì)異構(gòu)信號(hào)處理平臺(tái)實(shí)時(shí)性、高效性、穩(wěn)定性的要求。

圖5 HA、MHA、AIA和THA算法應(yīng)用比例Figure 5.Application proportion of HA、MHA、AIA and THA

4 結(jié)束語(yǔ)

目前,異構(gòu)多平臺(tái)信號(hào)處理系統(tǒng)的軟硬件部署、任務(wù)規(guī)劃決策等方面仍然面臨重大挑戰(zhàn),本文對(duì)異構(gòu)多平臺(tái)信號(hào)處理任務(wù)調(diào)度系統(tǒng)進(jìn)行了研究,并將調(diào)度算法按照任務(wù)類型、調(diào)度目標(biāo)、調(diào)度過(guò)程和研究方法進(jìn)行了分類,總結(jié)了異構(gòu)處理系統(tǒng)的任務(wù)調(diào)度算法研究現(xiàn)狀,結(jié)合任務(wù)智能感知的研究提出了基于任務(wù)感知的混合調(diào)度算法。最后根據(jù)異構(gòu)多平臺(tái)信號(hào)處理系統(tǒng)對(duì)實(shí)時(shí)性、穩(wěn)定性以及準(zhǔn)確定的要求和目前調(diào)度任務(wù)存在的重難點(diǎn)問(wèn)題,闡述了下一步的研究方向是基于任務(wù)感知的混合調(diào)度算法。