基于多核處理器的關聯任務并行感知調度算法

梁秋玲，張向利，張紅梅，閆 坤

（1.桂林電子科技大學信息與通信學院，廣西桂林541004；2.桂林電子科技大學信息與通信學院認知無線電與信息處理省部共建教育部重點實驗室，廣西桂林541004）

0 概述

多核處理器的應用為實時系統高性能集成設計提供了有效途徑［1］。多核處理器通常分為同構多核處理器和異構多核處理器。其中，異構多核處理器更有利于靈活配置系統資源，提高系統性能，降低系統功耗［2］。核間通信一直是多核系統設計過程中的重點問題，而基于共享總線的通信機制具有結構簡單、易于實現的優點，能夠有效實現核間的互聯和通信［3］。但是，共享總線的通信方式效率較低，可擴展性較差，核間通信開銷爭用問題直接影響多核結構的性能［4-5］。因此，在多核系統應用中降低通信開銷尤為重要。

多樣化的數據流應用組成了結構各異的任務模型。在多核處理器系統研究中，常見的任務模型有fork/join 模型［6］、同步并行模型［7］和DAG（Directed Acyclic Graph）模型［8］。隨著智能設備的快速發展，關聯任務隨之產生，例如，一輛自動駕駛汽車具有并發的多種任務（速度監測、制動控制等），一個任務需要使用另一個任務的輸出參數，從而導致任務間存在數據關聯［9］。關聯任務之間具有相互約束的特點，基于此，研究人員通常采用DAG 模型對關聯任務進行建模。與傳統DAG 任務不同，關聯任務在多核處理器中執行時需要考慮通信時延。據統計，任務在多核系統中執行時，核間通信造成的通信時延是核內通信的3 倍～5 倍［10-11］。因此，如何設計任務的映射以充分利用多核處理器強大的計算能力，是關聯任務調度算法設計過程中的關鍵問題。

近年來，有較多學者對關聯任務調度算法進行了研究。文獻［12］分析最壞情況下關聯任務的關聯數據流在總線上的執行時間以及系統調度方法，其優化了總線的調度策略。文獻［13］通過模型檢查器SPIN 優化了靜態任務和總線訪問時間表，并提出一種有效的啟發式算法。文獻［14］提出一種基于動態規劃的偽多項式時間算法求解任務的映射和執行順序，通過提高任務的并行性來縮短任務調度時間，但其忽略了核間通信開銷。文獻［15］針對任務的周期特性，通過本地緩存區保存上一周期的關聯數據使通信型任務和計算型任務能夠重疊調度，從而最大程度地減少通信時延，同時，提出一種整數線性規劃（ILP）方法對任務進行調度，但該方法比較復雜且僅適用于周期任務。文獻［16］建立一種基于簡單樹（Simple-tree）的周期任務調度模型，其通過可延遲時間越短、任務越優先的調度方法改善資源利用率并提高任務的死限丟失率。文獻［17］提出一種針對周期與非周期關聯性任務的調度算法（DTSV），并根據任務相關性給出任務關聯性評價函數，將強關聯性任務分配到同一內核中，有效減少了核間通信，此外，該文結合輪詢算法改善了負載均衡問題。

目前，針對基于總線的多核處理器上關聯任務調度算法的研究取得了一定成果，但也存在一些問題，如算法多數是在同構多核處理器背景下展開分析，且所研究的任務結構簡單，算法可擴展性較低。為此，本文提出一種異構多核處理器下的結構多樣化關聯任務調度算法。以計算所得任務的最長路徑值為參照，合理分配任務調度的優先級。在處理器內核選擇階段，兼顧內核的可最早完成時間和任務分配到該內核的可減少通信延遲，設計任務與內核的最佳匹配評價函數。在任務調度期間，在內核和總線的空閑間隙插入合適的任務，以充分利用系統資源。

1 關聯任務模型

關聯任務模型結構如圖1所示，研究人員通常將關聯任務分為計算型任務和通信型任務兩類，用符號＜T，E＞表示，T代表計算型任務集合，E代表通信型任務集合。圖1 中的節點即為一個計算型任務，記為Ti，表示第i個計算型任務，對應權值ti表示任務計算時間。與當前節點直接相連的前一個節點稱作前驅計算型任務，記為Tk，對應的連邊稱作前驅通信型任務，記為，權值表示通信時間；與當前節點直接相連的后一個節點稱作后繼計算型任務，記為Tj。為方便下文表述，將第一個計算型任務定義為源點任務，最后一個計算型任務定義為終點任務。每個計算型任務需要分配到處理器內核中執行，通信型任務則需在總線上執行。當具有數據關聯性的計算型任務被分配在不同的內核時，任務間通信為核間通信，不為零；計算型任務被分配到同一個內核時，任務間通信為核內通信，很小，本文假定為0。

圖1 關聯任務模型結構Fig.1 Related task model structure

2 算法設計及相關公式

異構多核處理器各個內核的功能、運算能力不同，導致同一個計算型任務分配到不同內核中執行所需的計算時間也不同。本文在分配計算型任務的調度優先級前，先計算任務在各個內核中執行所需的時間平均值，計算公式如下：

其中，t（Ti，Px）表示Ti在第x個內核處理器中執行所需的時間，M為多核處理器系統的內核個數。

在異構多核系統中，只有芯片上集成的多核的功能配置與任務負載的并行特征匹配，才能有效提高計算效率［18］。根據任務圖的模型結構，具有數據關聯的各個任務存在嚴格的先后執行約束關系。因此，在任務調度優先級分配階段，本文對HEFT 算法進行改進，在計算每個計算型任務到終點任務的關鍵路徑值時，考慮與之相關的通信型任務并將其定義為最長路徑，按照最長路徑值的降序來排列任務的調度次序。相關定義及公式如下：

定義1（計算型任務Ti的最長路徑值L（Ti））L（Ti）表示在DAG 表示的關聯性任務圖中，從計算型任務Ti的最大前驅通信型任務到終點任務的路徑中權值之和的最大值。L（Ti）的計算公式如下：

其中，Mpred(Ti)、Msucc(Ti)表示計算型任務Ti的前驅計算型任務集合和后繼計算型任務集合。

高效的調度算法在進行任務調度時需要考慮應用程序的特點、行為和相關性能，然后將這些任務合理地分配到具有相應特性的不同類型的處理器核上［19］。因此，本文調度算法在內核選擇階段考慮任務在異構內核的最早執行時間和關聯度。

將關聯任務映射到多個內核中，定義tEST（Ti，Px）、tEFT（Ti，Px）分別為計算型任務Ti在內核Px的最早可執行時間和最早完成時間。其中，源點任務Tentry的tEST作為調度長度計算時的初始值，將其初始化為0，如下：

根據初始化值，每個待調度計算型任務的tEST與tEFT，可以通過迭代計算處理器中已分配的計算型任務和總線上相關通信型任務的tEFT獲得，相關計算過程如下：

1）計算型任務的所有前驅通信型任務的最晚完成時間計算公式如下：

其中，Aavail（Bbus）表示總線上最早可用空閑時隙的開始時間，其計算公式（式（7））需滿足式（8）的條件。

其中，Em和Em+1代表總線上任意相鄰的2 個通信型任務，m為數量標記，Sspace（m，Bbus）為總線上的空閑時隙。

2）內核的最早可執行時間，即滿足大于或等于任務在該內核的計算時間的最早空閑時隙，計算公式如式（9）、式（10）所示：

其中，Aavail（Px）表示處理器Px上最早可用空閑時隙的開始時間，式（9）需滿足式（10）的條件。Tm和Tm+1分別代表同一個內核上任意相鄰的2 個計算型任務，Sspace（m，Px）為內核的空閑時隙。

3）計算型任務可最早執行時間，為計算型任務所有前驅通信型任務的最晚完成時間和內核最早可執行時間的最大值，如式（11）所示，計算型任務最早可完成時間如式（12）所示。

內核與待調度任務的關聯度及其匹配評價函數的相關定義及公式如下：

定義2（任務關聯度評價函數R（Ti，Px））R（Ti，Px）為待分配任務Ti與分配到處理器Px的任務因存在數據關聯性而產生的通信時間總和。R（Ti，Px）的計算公式如下：

其中，n為處理器Px中的所有計算型任務數量，n=0時表示處理器還沒有分配計算型任務。

定義3（處理器匹配評價函數F）F為待分配任務Ti與處理器Px的關聯度與Ti在Px上的最早可執行時間差值，F值越大，匹配值越大。F的計算公式如下：

處理器匹配評價函數用于優化關聯任務以通信時間換取計算時間的并行調度效果，降低多核系統的通信量。例如，若一個待分配任務在一個處理器中的最早完成時間只比另外一個處理器早一點，但另外一個處理器與該任務有更強的關聯度，可減少更多的通信任務，本文算法則將任務分配到關聯度強的處理器中以降低系統整體能耗。

3 關聯任務調度算法實現

3.1 任務調度優先級分配

在關聯任務中，計算型任務可以執行的必要條件是其所有前驅通信型任務執行完畢，本文算法通過以下步驟計算任務的調度順序：

步驟1計算各個計算型任務的最長路徑值，按照最長路徑值的降序進行排列，記為集合T=｛T1，T2，…，Tx，…，Ty，…，TN｝。

步驟2按照排列順序遍歷集合T，若出現排列靠后的任務Ty是排列靠前任務Tx的前驅計算型任務，則將Tx取出并插入Ty之前，更新集合T；否則，集合T的元素順序即為調度順序。

3.2 處理器選擇

在關聯任務映射到對應的處理器內核時，為了降低通信量并充分利用多核系統強大的計算能力，本文算法通過內核的最佳匹配函數適當約束關聯任務調度的并行度，具體步驟如下：

步驟1計算待調度任務在每個內核的最早可完成時間tEFT（Ti，Px）。

步驟2計算待調度任務與每個處理器的關聯度R（Ti，Px）。

步驟3計算待調度任務與處理器的匹配值F（Ti，Px）。

步驟4選擇F（Ti，Px）最大值對應的處理器。

4 實驗結果與分析

4.1 任務集及其參數

文獻［20］使用的DAG 任務集產生方法所產生的任務集更具隨機性、多樣性和復雜性，因此，本文采用該方法生成實驗任務集。文獻［20］方法生成的任務模型的主要控制參數包括任務的深度Ddepth、單個分支節點的最大并行數MmaxParBranches、并行因子Ppar、節點因子Pterm（Ppar+Pterm=1）和隨機因子PaddProb。其中，Ppar為從同一源點出發的并行任務個數的概率參數，Pterm為不同任務匯集同一節點任務個數的概率參數，PaddProb為任務與任務間隨機建立關聯的概率參數。本文實驗中關聯任務產生器的各個參數值設置為：Ddepth=4（4×2=8 層），Ppar=0.8，Pterm=0.2，PaddProb=0.2，MmaxParBranches=6，任務模型的節點權值和邊權值的取值范圍均為10～100。

4.2 對比實驗設計

本文從調度長度比（Scheduling Length Radio，SLR）［21］、處理器利用率和所產生的通信量3 個方面來評估算法性能。HEFT 是經典的DAG 任務調度算法，在現實多種網絡的任務調度中得到廣泛應用，本文在對HEFT 算法的處理過程中考慮通信任務的影響，使該算法適用于基于總線的多處理器環境下的關聯任務調度，本文將其重命名為busHEFT，該算法與本文算法（busCDEFT）、DTSV 算法［17］作為實驗對比算法。

在任務調度過程中，算法具有良好可擴展性表現為其適用于結構多樣化的任務集調度，且不會因為任務集或調度系統的一些參數變化而導致性能急劇下降。為證明本文算法具有良好的可擴展性，設計如下2 組實驗：第一組實驗在不同數量的處理器下比較算法的SLR、處理器利用率和通信量3 個指標結果，實驗設置處理器個數分別為2、3、4、5、6，CCR（Communication to Computation Ratio）為2；第二組實驗在不同CCR 下比較算法的上述3 個指標結果，其中，CCR 最小值為0.5，最大值為6.0，步長為0.5，處理器內核數目為3。為了使實驗更具代表性，在每次實驗參數變化后都使用重新隨機生成的任務集，2 組實驗使用的任務集數目均為500。

4.3 結果分析

第一組實驗結果如圖2～圖4所示，從中可以看出，在不同數目的處理器條件下，與另外2 種對比算法相比，本文算法具有更短的調度時延、更少的通信量和更高的資源利用率，這是因為DTSV 算法雖然根據任務關聯度評價函數將數據關聯性大的任務放在同一個處理器上，在一定程度上減少了通信量，但是結合輪詢算法分配其他關聯度比較弱的任務以實現負載均衡的方法，所產生的通信量會隨著處理器數量的增多而減少，同時任務調度時延也會增大，資源利用率降低，負載均衡的性能在異構處理器系統中較難保證，而本文算法和busHEFT 算法在任務調度階段考慮任務模型結構對調度次序的影響，從而能夠合理分配調度優先級。在任務映射階段，本文算法考慮了待調度任務在每個內核中的最早完成時間，使異構處理器核的運算能力與負載相互匹配，從而有效提高計算效率并縮短調度時延。此外，本文算法還兼顧了任務的關聯度對通信時延的影響，算法在這樣的前提條件下具有一定的并行感知調度性能，不會隨著處理器的增多而任意并行調度，從而有效減少了任務通信量并提高了處理器利用率。

圖2 不同處理器數目下3 種算法的SLR 性能比較Fig.2 Comparison of SLR performance of three algorithms with different numbers of processors

圖3 不同處理器數目下3 種算法所產生的通信量比較Fig.3 Comparison of communication traffic of three algorithms with different numbers of processors

圖4 不同處理器數目下3 種算法的處理器利用率比較Fig.4 Comparison of processor utilization of three algorithms with different numbers of processors

第二組實驗結果如圖5～圖7所示，從中可以看出，在其他參數設置相同、任務集CCR 值不同的條件下，本文算法同樣表現出較好的性能，其任務調度時延更短，通信量更少，處理器利用率更高。因此，本文算法的適用范圍較廣，可擴展性較高。

圖5 不同CCR 下3 種算法的SLR 性能比較Fig.5 Comparison of SLR performance of three algorithms under different CCR

圖6 不同CCR 下3 種算法所產生的通信量比較Fig.6 Comparison of communication traffic of three algorithms under different CCR

圖7 不同CCR 下3 種算法的處理器利用率比較Fig.7 Comparison of processor utilization of three algorithms under different CCR

5 結束語

本文提出一種關聯任務調度算法，根據關聯任務的結構特點計算各個計算型任務的最長路徑值，以合理分配任務的調度順序，同時考慮各個內核的運算性能，設計任務與處理器內核間的最佳匹配函數，從而提高系統的運行效率。實驗結果表明，該算法在處理結構復雜的多樣化關聯任務集時表現出良好的任務調度性能。下一步將研究關聯任務具有截止時間約束情況下調度算法的實時性和可靠性問題。