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

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

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

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

1 HPSP調(diào)度策略

1.1 HPSP平臺

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

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

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

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

任務(wù)調(diào)度模型和目標處理環(huán)境模型在其相應(yīng)的應(yīng)用任務(wù)調(diào)度、調(diào)度算法以及調(diào)度目標中具有重要作用[8],所以構(gòu)建合理規(guī)范的任務(wù)調(diào)度模型是設(shè)計、分析任務(wù)調(diào)度算法的基礎(chǔ),同時也為設(shè)計算法提供了一個描述準確、架構(gòu)簡單的任務(wù)調(diào)度模型。目前采用有向無環(huán)圖描述任務(wù)調(diào)度模型。如圖3(a)所示,每個節(jié)點表示一個任務(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ù)計算代價集合,L(vi,vj)表示任務(wù)間通信延遲。硬件架構(gòu)用無向圖抽象為P={N,H,W,T},是一個具有4個異構(gòu)處理器的處理系統(tǒng)模型,如圖3(b)所示。其中,N是處理器集合,H為處理器特征,W為計算量,T是處理器間的通信量,如式(1)所示。任意兩個任務(wù)vi及vj被分配至同一節(jié)點上(即在同一處理上),通信開銷Tij為0。

(a)

(1)

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

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

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

任務(wù)調(diào)度的難點主要在將待處理任務(wù)合理分配到處理平臺中的各個處理器上,即在滿足平臺資源約束條件下選擇合適的算法將到達的任務(wù)隊列進行合理有效的映射,使平臺中的處理器均擁有高效的計算處理性能,最終完成預(yù)期的調(diào)度任務(wù)。文獻[10]對靜態(tài)和動態(tài)調(diào)度間的區(qū)別做了說明,靜態(tài)調(diào)度主要包括啟發(fā)式和引導(dǎo)隨機搜索調(diào)度,而啟發(fā)式調(diào)度方法又分為表調(diào)度、聚類調(diào)度和任務(wù)復(fù)制調(diào)度[11]。動態(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)度方法分類拓撲,體現(xiàn)了各類任務(wù)調(diào)度方法間的邏輯關(guān)系。

圖4 調(diào)度方法分類拓撲Figure 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)先級的調(diào)度列表并逐一將任務(wù)分配至處理器,在該過程中任務(wù)的執(zhí)行順序不變。主要步驟是從調(diào)度列表中依次取出待執(zhí)行任務(wù),再將取出的任務(wù)依次分配到能夠使其執(zhí)行時間最短的處理器上。動態(tài)表調(diào)度方法與靜態(tài)表調(diào)度方法最大的區(qū)別在于動態(tài)表調(diào)度在每次取出調(diào)度列表中的一個任務(wù)后會重新計算各任務(wù)優(yōu)先級并形成新的調(diào)度列表。

表調(diào)度方法因步驟簡單和模型復(fù)雜度低而被廣泛應(yīng)用于任務(wù)調(diào)度問題中,但表調(diào)度方法通過優(yōu)先級調(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ù)間的通信開銷。其過程主要包括兩個步驟:1)初始化調(diào)度任務(wù),將任務(wù)劃分為不同的聚類,并將聚類映射到虛擬處理器上以減少任務(wù)間的通信開銷;2)將每個聚類任務(wù)映射到一個處理器上。

由于聚類調(diào)度方法中是全局聚類的,所以執(zhí)行效果較好,但當可用處理器數(shù)量小于聚類數(shù)目時,方法的有效性會降低[21]。通常利用不同的合并任務(wù)簇方法來區(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)度方法

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

不同任務(wù)復(fù)制算法在選擇復(fù)制的策略上有所差異,一種算法只復(fù)制直接前繼節(jié)點任務(wù),另一種算法復(fù)制所有可能的前繼節(jié)點任務(wù)。相對于其它啟發(fā)式調(diào)度方法,基于任務(wù)復(fù)制的調(diào)度算法的性能更好,但這類算法適用于處理器數(shù)量無限制的系統(tǒng),且時間復(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)隨機搜索調(diào)度方法

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

引導(dǎo)隨機搜索調(diào)度方法主要在調(diào)度任務(wù)集合中通過大量迭代來尋找最優(yōu)解。相對于啟發(fā)式方法,該方法的調(diào)度質(zhì)量更高,但是解空間求解時間相對較高。為更好得到最優(yōu)解,算法中的循環(huán)架構(gòu)和適應(yīng)度函數(shù)需要合理設(shè)計,且參數(shù)設(shè)置通常與任務(wù)需求相關(guān),故存在擴展性差、解空間求解時間高等缺點。經(jīng)典的引導(dǎo)隨機搜索調(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é)方法,其在既定約束下尋求某一指標得到最優(yōu),主要由函數(shù)優(yōu)化和組合優(yōu)化構(gòu)成。函數(shù)優(yōu)化對象是有限區(qū)間內(nèi)的連續(xù)變量,組合優(yōu)化對象是解空間中的離散狀態(tài)。通過最優(yōu)化算法解決問題的主要思路是建立數(shù)學(xué)模型和制定最優(yōu)解搜索策略,本質(zhì)是一種搜索規(guī)則或方法。引導(dǎo)隨機搜索調(diào)度方法是一種最優(yōu)化方法,在某些機制基礎(chǔ)上通過一定策略或方法使最終的解符合任務(wù)需求。最優(yōu)化算法包括精確算法、個體尋優(yōu)算法、啟發(fā)式算法以及群體智能尋優(yōu)算法等。

2.1.6 仿真方法

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

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

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

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

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

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

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

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

異構(gòu)多平臺信號處理系統(tǒng)的難點是動態(tài)分配任務(wù)和提高系統(tǒng)的實時性。已提出的各類算法在任務(wù)調(diào)度中雖然都能起到一定作用,但是單一的調(diào)度算法本身存在的缺點不能滿足平臺對調(diào)度任務(wù)高效性和動態(tài)性的要求。本文根據(jù)異構(gòu)平臺任務(wù)調(diào)度的最新研究提出了基于任務(wù)感知的混合調(diào)度算法,即在任務(wù)資源感知的狀態(tài)下(任務(wù)智能加卸載),首先通過靜態(tài)調(diào)度形成任務(wù)劃分的初始方案,然后根據(jù)異構(gòu)平臺接收處理任務(wù)的變化進行動態(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),對比分析了它們的優(yōu)化目標、調(diào)度類型和應(yīng)用場景等指標參數(shù)。

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

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

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

表2 HA、MHA、AIA和THA算法對比分析

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

3 未來發(fā)展方向

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

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

4 結(jié)束語

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