面向異構(gòu)信號處理平臺的量子調(diào)度算法

沈小龍,馬金全,胡澤明,李 娜,李宇東

(1.戰(zhàn)略支援部隊信息工程大學(xué) 信息系統(tǒng)工程學(xué)院,河南 鄭州 450000;2.交通銀行 河南省分行,河南 鄭州 450000)

隨著科學(xué)技術(shù)的發(fā)展,現(xiàn)代信號處理應(yīng)用對硬件資源的處理速度要求越來越快,精度要求越來越高,內(nèi)存要求越來越大,且不同類型應(yīng)用所需的硬件資源類型不相同。傳統(tǒng)信號處理平臺硬件資源類型單一、搭載的信號處理應(yīng)用類型少、處理能力有限以及面對上述硬件資源要求無解決方法,而異構(gòu)信號處理平臺憑借自身豐富處理資源[1-4]成為現(xiàn)代信號處理應(yīng)用的首選搭載平臺。將信號處理應(yīng)用部署在異構(gòu)信號處理平臺時,首先利用有向無環(huán)圖(Directed Acyclic Graph,DAG)將應(yīng)用抽象建模為有依賴關(guān)系的任務(wù)集合[5-7],然后通過調(diào)度算法將任務(wù)部署到平臺的處理器上,不同的部署方案應(yīng)用執(zhí)行完成時間差別較大。調(diào)度算法的優(yōu)劣決定應(yīng)用實時性高低和平臺工作性能好壞。因此設(shè)計一種使應(yīng)用完成時間盡可能短、實時性盡可能高的調(diào)度算法是該領(lǐng)域的研究熱點。

調(diào)度算法在運行時主要分為任務(wù)優(yōu)先級排序和處理器分配兩個階段。根據(jù)DAG平均通信開銷和平均計算開銷的比值(Communication to Computation Ratio,CCR)將應(yīng)用分為計算密集型和通信密集型[8]。文獻[9]提出HEFT(Heterogeneous Earliest Finish Time)算法,該算法是較為經(jīng)典的調(diào)度算法,通過任務(wù)平均計算開銷計算得到任務(wù)序值并進行排序,忽略不同處理器處理性能差異,對通信密集型任務(wù)調(diào)度效果較好,但對計算密集型任務(wù)調(diào)度效果不佳,且其任務(wù)處理器分配策略單一。文獻[10]提出HSIP(Heterogeneous Scheduling Algorithm with Improved Task Priority)算法,該算法在HEFT基礎(chǔ)上進行改進,在計算任務(wù)優(yōu)先級時,利用計算開銷標準差代替平均值,充分反映任務(wù)在不同處理器運行時的計算開銷差異,對計算密集型應(yīng)用調(diào)度效果較好,但對通信密集型應(yīng)用調(diào)度效果一般。文獻[11]提出任務(wù)優(yōu)先級分流排序策略,根據(jù)應(yīng)用類型特點制定不同排序方法,但該算法處理器分配方案較為復(fù)雜且算法復(fù)雜度高。文獻[12]提出的算法對初始信息素矩陣較為依賴。量子算法具有較好的性能,在密碼和神經(jīng)網(wǎng)絡(luò)優(yōu)化領(lǐng)域得到廣泛應(yīng)用。文獻[13]利用量子比特進行傳輸協(xié)議制定,并通過量子旋轉(zhuǎn)門設(shè)計傳輸機制。文獻[14]和文獻[15]均是用量子算法優(yōu)化BP(Back Propagation)神經(jīng)網(wǎng)絡(luò)的閾值和權(quán)值參數(shù),提升網(wǎng)絡(luò)準確率。文獻[16]將量子算法與生成對抗網(wǎng)絡(luò)結(jié)合,提升網(wǎng)絡(luò)訓(xùn)練速度。

當前量子算法在異構(gòu)信號處理平臺任務(wù)調(diào)度領(lǐng)域研究較少。結(jié)合上述調(diào)度算法的研究現(xiàn)狀,本文提出一種面向異構(gòu)信號處理平臺的量子調(diào)度算法(Quantum Scheduling Algorithm,QSA)。該算法利用量子比特對任務(wù)分配方案進行編碼,并通過量子旋轉(zhuǎn)門更新分配方案。在任務(wù)優(yōu)先級排序階段,采用任務(wù)優(yōu)先級分流排序策略確定任務(wù)調(diào)度順序。在處理器分配階段,采用任務(wù)復(fù)制思想和最早完成時間原則進行處理器分配。

1 系統(tǒng)模型

異構(gòu)處理平臺總體可分為4層[17],如圖1所示。底層為硬件層,包含平臺所有處理器資源。底層之上為中間層,由操作系統(tǒng)層、板級支持包以及平臺抽象層等組成。中間層之上為組件層,包含項目組研發(fā)的所有組件。頂層為應(yīng)用層,包含當前平臺部署的信號處理應(yīng)用程序。在異構(gòu)信號處理平臺增加新應(yīng)用時,首先進行功能分析從組件庫中挑選組件搭建應(yīng)用程序,之后利用調(diào)度算法為應(yīng)用程序中組件分配處理器,最后通過中間層將組件部署到相應(yīng)處理器,完成新應(yīng)用程序在異構(gòu)處理平臺的開發(fā)。

圖1 平臺結(jié)構(gòu)Figure 1. Platform structure

在調(diào)度算法研究中,將信號處理應(yīng)用抽象建模為DAG圖,定義為G=(V,C,P,W)。其中,V是任務(wù)集合,C是通信開銷矩陣,P是處理器集合,W是計算開銷矩陣。經(jīng)典DAG如圖2所示。其中,vi為任務(wù),與圖中節(jié)點對應(yīng),cij為任務(wù)間平均通信開銷,與圖中有向邊對應(yīng),pi為處理器,wij為任務(wù)在處理器上計算開銷,與表1對應(yīng)。

表1 典型DAG計算成本Table 1．Typical DAG calculation cost

圖2 典型DAG任務(wù)Figure 2. Typical DAG task

2 QSA算法

2.1 優(yōu)先級排序

為能夠得到更加符合任務(wù)類型特點的調(diào)度順序,本文采用任務(wù)優(yōu)先級分流排序策略,針對不同任務(wù)類型,優(yōu)先級計算方法不同。得到任務(wù)圖后首先計算該圖CCR,計算式如下

(1)

其中,cij為vi與vj間通信開銷;wik為vi在pk上計算開銷;son(vi)為vi子任務(wù)集合;n為任務(wù)數(shù);l為有向邊數(shù)目;m為處理器數(shù)。CCR值≥1的是通信密集型任務(wù),其余為計算密集型任務(wù)。通信密集型任務(wù)優(yōu)先級計算式如下

(2)

(3)

其中,σi為vi在所有處理器上計算開銷的標準差,能更好地反映出任務(wù)在不同處理器上計算開銷差異。得到任務(wù)優(yōu)先級序值后,按照降序排序作為任務(wù)最終調(diào)度順序。

2.2 量子比特編碼

量子算法尋優(yōu)能力較強,且不需要初始信息素。因此本文采用量子比特對任務(wù)處理器分配方案進行編碼,編碼中通過量子位來存儲信息。量子位是由2個量子基態(tài)組成,其中一個是|0>態(tài)表示自旋向下態(tài);另一個是|1>態(tài)表示自旋向上態(tài),此二者是一對標準正交基。量子空間中的量子比特是這兩個基態(tài)的疊加態(tài)|φ>

|φ>=A×|0>+B×|1>

(4)

其中,A和B分別表示處于各基態(tài)的概率幅,且滿足如下計算式

|A|2+|B|2=1

(5)

量子比特可用基態(tài)矩陣和概率幅矩陣相乘的形式表示,計算式如下

(6)

本文實驗的處理器數(shù)量取值范圍是3～6,所以利用3個量子比特對任務(wù)分配的處理器進行編碼,任務(wù)vi的編碼方案如下

(7)

其中每對概率幅都滿足式(5)。在具體情形中可根據(jù)處理器上限數(shù)量對量子比特編碼位數(shù)進行調(diào)整。

在初始化任務(wù)分配方案的量子編碼時,首先生成兩個服從標準正太分布的隨機數(shù)a和b,然后按照如下計算式

(8)

計算得到量子比特概率幅均滿足式(5),通過產(chǎn)生的隨機數(shù)增加種群多樣性。

在得到編碼方案后,生成一個0～1的隨機數(shù)rand,并在每個量子比特中隨機選取一個概率幅例如Ai1,將rand同Ai12進行對比,根據(jù)結(jié)果將該量子比特編碼為二進制1或0,結(jié)果如下

(9)

在量子比特編碼轉(zhuǎn)換為二進制編碼方案過程中,通過隨機數(shù)進行比較,有助于跳出局部最優(yōu)解。然后將該任務(wù)的二進制編碼映射成為具體處理器編號。以將任務(wù)集合分配到3個處理器為例,對具體映射方案進行如下講解。首先將式(9)中二進制轉(zhuǎn)換為十進制數(shù),因為每個任務(wù)的分配方案是用3個量子比特進行編碼,所以轉(zhuǎn)換為十進制后的取值范圍是0～7,而處理器取值范圍是1～3,因此按照如下計算式對十進制數(shù)進行映射

(10)

2.3 處理器分配

在進行處理器分配時,將任務(wù)分為入口任務(wù)、各處理器首任務(wù)和其余任務(wù)3類。

入口任務(wù)優(yōu)先級最高,是第1個分配任務(wù),其分配結(jié)果直接影響最終調(diào)度結(jié)果。本文采取最小計算開銷原則對入口任務(wù)進行分配,將其分配到具有最小計算開銷的處理器上,可以有效減少調(diào)度長度。

各處理器首任務(wù)是指分配到處理器上的第1個任務(wù),對于該類任務(wù)利用任務(wù)復(fù)制思想優(yōu)化任務(wù)完成時間。若首任務(wù)是入口任務(wù)則按照入口任務(wù)分配原則處理,若不是入口任務(wù)其執(zhí)行開始時間前存在時間空隙,此時可以利用任務(wù)復(fù)制思想將其父任務(wù)復(fù)制到該處理器,同一處理器上任務(wù)間的通信開銷可以忽略不計。通過任務(wù)復(fù)制能夠有效減少任務(wù)間通信開銷,進而優(yōu)化任務(wù)完成時間。其余任務(wù)按照量子編碼方案進行分配。

2.4 適度函數(shù)

本文將任務(wù)調(diào)度長度作為適度函數(shù)衡量每種分配方案優(yōu)劣。同時每次迭代中適度函數(shù)的最優(yōu)值是量子種群更新迭代得參考標準。調(diào)度長度計算式如下

makespan=EFT(vexit)

(11)

其中,vexit表示出口任務(wù);EFT(vexit)表示出口任務(wù)的完成時間。調(diào)度長度即為DAG圖的整體執(zhí)行完成時間,該值越小越好。

2.5 量子比特更新

通過量子旋轉(zhuǎn)門對量子比特進行更新,使更新后量子比特的概率幅仍然滿足式(5),量子旋轉(zhuǎn)門quantum_gate計算式如下

(12)

式中,θ為旋轉(zhuǎn)角,其大小一般是π/25[18],通過將每種分配方案同最優(yōu)適度函數(shù)方案進行對比后確定方向。圖3為量子旋轉(zhuǎn),該圖中橫坐標是|0>態(tài),縱坐標是|1>態(tài),A和B分別表示處于各基態(tài)的概率幅,逆時針旋轉(zhuǎn)為正方向,順時針旋轉(zhuǎn)量子比特的二進制編碼同最優(yōu)解的二進制編碼進行比較,決定量子旋轉(zhuǎn)角。

圖3 量子旋轉(zhuǎn)Figure 3. Quantum rotation

在量子比特同最優(yōu)解的二進制編碼比較時,將二進制的0和1等效于量子比特的|0>態(tài)和|1>態(tài)。

表2為具體情況下旋轉(zhuǎn)角取值。得到旋轉(zhuǎn)角后,按照如下計算式進行量子比特旋轉(zhuǎn)

表2 量子旋轉(zhuǎn)角取值Table 2. The value of the quantum ration angle

表3 QSA算法參數(shù)設(shè)置Table 3. QSA algorithm parameter settings

(13)

其中,Ai1和Bi1是旋轉(zhuǎn)前的概率幅;Ai1′和Bi1′是旋轉(zhuǎn)后的概率幅。圖4為QSA算法流程。

圖4 QSA運行流程Figure 4.QSA operation flow

3 仿真實驗及性能分析

3.1 參數(shù)設(shè)置

算法中的參數(shù)設(shè)置如3所示,量子種群為30,迭代次數(shù)為1 000,量子比特編碼長度為3。

3.2 QSA有效性分析

通過經(jīng)典DAG和隨機DAG進行仿真實驗,將QSA同HEFT算法、HSIP算法和文獻[11]所提算法進行對比,驗證QSA的有效性。

實驗1計算得到QSA算法的調(diào)度長度如圖5所示。

圖5 實驗1QSA調(diào)度長度結(jié)果Figure 5. QSA scheduling length result in experiment one

從該仿真結(jié)果看出迭代到62次時,QSA算法的調(diào)度長度值收斂于69。表4為4種算法的調(diào)度長度。

表4 實驗1中4種算法調(diào)度長度結(jié)果Table 4. The four algorithms scheduling length result in experimont one

從調(diào)度結(jié)果看出,QSA算法的調(diào)度長度優(yōu)于HEFT算法,但比HSIP算法和文獻[11]所提算法較差。這是因為經(jīng)典DAG任務(wù)少,體現(xiàn)不出QSA算法的計算性能。從圖5可以看出,迭代到一定次數(shù)時陷入局部最優(yōu),調(diào)度長度保持不變,能跳出局部最優(yōu)解在于將量子比特轉(zhuǎn)換為二進制比特過程中生成的隨機數(shù),該過程提供了跳出局部最優(yōu)的通道。

實驗2隨機生成一個任務(wù)數(shù)為20,處理器數(shù)為3的任務(wù)圖,計算得到QSA算法的調(diào)度長度如圖6所示。

圖6 實驗2QSA調(diào)度長度結(jié)果Figure 6. QSA scheduling length result experiment two

從該仿真結(jié)果看出,迭代到第210次時,QSA算法的調(diào)度長度值收斂于74。表5為4種算法的調(diào)度長度。

表5 實驗2中4種算法調(diào)度長度結(jié)果Table 5.The four algorithms scheduling length result experiment two

從調(diào)度結(jié)果看出,QSA算法的調(diào)度長度均優(yōu)于對比算法。

從以上實驗看出,QSA算法對調(diào)度長度的優(yōu)化效果有效、明顯。

3.3 QSA可靠性分析

設(shè)計兩組實驗對任務(wù)數(shù)量和處理器數(shù)量分別進行變化,以驗證QSA算法的可靠性。

實驗3隨機生成一組任務(wù)數(shù)為20,處理器數(shù)為3～6的任務(wù)圖。計算得到結(jié)果對比如圖7所示,并計算QSA算法相對于對比算法的優(yōu)化率。

圖7 實驗3調(diào)度長度對比Figure 7. Comparison of scheduling length in experiment three

從調(diào)度結(jié)果可以看出,QSA算法的調(diào)度長度均優(yōu)于HEFT、HSIP和文獻[11]所提算法,對調(diào)度結(jié)果進行計算可知,QSA對HEFT的平均優(yōu)化率為38.76%,對HSIP的平均優(yōu)化率為29.49%,對文獻[11]所提算法的平均優(yōu)化率為24.44%。

實驗4隨機生成一組處理器數(shù)為3,任務(wù)數(shù)為20、40、60的隨機DAG。計算得到結(jié)果對比如圖8所示,計算得到QSA算法相對于對比算法的優(yōu)化率。

圖8 實驗4調(diào)度長度對比Figure 8. Comparison of scheduling length in experiment four

從調(diào)度結(jié)果可以看出,QSA算法的調(diào)度長度均優(yōu)于HEFT和文獻[11]所提算法,對調(diào)度結(jié)果進行計算可知,QSA對HEFT的平均優(yōu)化率為29.52%,對HSIP的平均優(yōu)化率為19.82%,對文獻[11]所提算法的平均優(yōu)化率為16.22%。

從以上兩組實驗中看出,在任務(wù)數(shù)相同處理器數(shù)變化和處理器數(shù)相同任務(wù)數(shù)變化的兩種情況下,QSA算法的調(diào)度長度均達到了預(yù)期的優(yōu)化效果,證明了該算法的可靠性。

4 結(jié)束語

針對異構(gòu)信號處理平臺中已有調(diào)度算法對現(xiàn)代信號處理應(yīng)用的調(diào)度長度較大導(dǎo)致應(yīng)用的實時性下降問題,本文提出QSA算法。該算法采用任務(wù)優(yōu)先級分流排序策略,對通信密集型任務(wù)和計算密集型任務(wù)制定不同的優(yōu)先級計算方法。采用量子比特對任務(wù)分配方案進行編碼,通過將量子比特映射為二進制比特過程跳出局部最優(yōu)解。根據(jù)適度函數(shù)值大小,通過量子旋轉(zhuǎn)門更新量子比特,朝最小調(diào)度長度方向不斷迭代優(yōu)化?？紤]入口任務(wù)的關(guān)鍵性,將入口任務(wù)按照最小計算開銷原則分配,并利用任務(wù)復(fù)制思想降低任務(wù)間通信開銷,取得最小調(diào)度長度。通過仿真實驗可知,QSA算法能夠有效提高信號處理應(yīng)用的實時性。