面向異構信號處理平臺的量子調度算法

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

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

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

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

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

1 系統模型

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

圖1 平臺結構Figure 1. Platform structure

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

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

圖2 典型DAG任務Figure 2. Typical DAG task

2 QSA算法

2.1 優先級排序

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

(1)

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

(2)

(3)

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

2.2 量子比特編碼

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

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

(4)

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

|A|2+|B|2=1

(5)

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

(6)

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

(7)

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

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

(8)

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

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

(9)

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

(10)

2.3 處理器分配

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

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

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

2.4 適度函數

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

makespan=EFT(vexit)

(11)

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

2.5 量子比特更新

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

(12)

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

圖3 量子旋轉Figure 3. Quantum rotation

在量子比特同最優解的二進制編碼比較時,將二進制的0和1等效于量子比特的|0>態和|1>態。

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

表2 量子旋轉角取值Table 2. The value of the quantum ration angle

表3 QSA算法參數設置Table 3. QSA algorithm parameter settings

(13)

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

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

3 仿真實驗及性能分析

3.1 參數設置

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

3.2 QSA有效性分析

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

實驗1計算得到QSA算法的調度長度如圖5所示。

圖5 實驗1QSA調度長度結果Figure 5. QSA scheduling length result in experiment one

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

表4 實驗1中4種算法調度長度結果Table 4. The four algorithms scheduling length result in experimont one

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

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

圖6 實驗2QSA調度長度結果Figure 6. QSA scheduling length result experiment two

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

表5 實驗2中4種算法調度長度結果Table 5.The four algorithms scheduling length result experiment two

從調度結果看出,QSA算法的調度長度均優于對比算法。

從以上實驗看出,QSA算法對調度長度的優化效果有效、明顯。

3.3 QSA可靠性分析

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

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

圖7 實驗3調度長度對比Figure 7. Comparison of scheduling length in experiment three

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

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

圖8 實驗4調度長度對比Figure 8. Comparison of scheduling length in experiment four

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

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

4 結束語

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