面向CPUs-GPUs系統的OpenCL任務調度框架

王 浩，王浩楓

(中國航天科工集團第二研究院 七〇六所，北京 100854)

0 引 言

隨著處理器的發展，異構計算機系統已經成為計算機架構的一大研究熱點，異構編程也得到了飛速發展，其中OpenCL[1]憑借良好的可移植性得到廣泛應用。OpenCL標準規定設備與命令隊列高度耦合，程序需在編碼階段靜態指定任務調度方案，這不僅對開發人員是一大難題，也對多任務下的資源分配帶來了極大的苦難。

目前，面向OpenCL多任務的研究主要包括靜態方法和動態方法。靜態方法是通過預先執行的方式，獲取任務在不同設備上的執行信息，進一步通過元啟發式算法確定調度方案并進行程序編碼。動態方法主要包括任務在線分析和任務調度兩部分，采用任務在線分析的方法替代靜態方法中的程序預執行，再根據任務分析結果，結合異構調度算法對任務進行動態調度。傳統動態調度一方面任務分析不考慮任務間資源競爭導致多任務場景下任務分析不準確，另一方面傳統研究忽視OpenCL數據傳輸導致的時間開銷，使得任務分析偏差較大，進一步影響調度效果。

本文提出了一個新穎的調度框架，它能夠在資源競爭環境下確定最佳任務分配。一方面，該框架考慮了OpenCL內核行為對設備硬件特性的適應性。另一方面，也考慮了動態設備和內核特性(如設備負載、內核數據大小等)對系統中任務調度的影響，該調度算法考慮系統總體負載均衡的同時保證了單個任務的執行效率。

1 研究現狀

本節展示了當前異構調度方法的研究現狀和存在的問題。

目前已經提出了幾種OpenCL任務調度方法。Fang J等[2]提出了一種基于異構多處理器的匹配度調度算法，該算法通過將任務靜態特征和處理器核心特征映射到相同的歐氏空間來計算任務與處理器的距離值，使用加權歐氏距離作為調度的依據。Al-Zoubi A等[3]提出了一個基于模糊邏輯分類器的CPU-GPU-FPGA異構平臺的調度框架。該框架使用OpenCL即時編譯器從OpenCL內核的抽象語法樹中提取靜態代碼特征，并與運行時特征相結合，將OpenCL內核調度到高并行度內核(GPU和FPGA)或低并行度內核(CPU)。Aji A M等[4]提出了建立在SnuCL基礎上的MultiCL調度框架，通過將內核啟動與高級命令隊列而不是實際的物理設備相關聯，使調度器能夠在內核啟動時動態地選擇合適的設備。MultiCL使用機器學習算法來預測內核在不同設備上的執行時間，作為內核剖析時調度的基礎。雖然上述方法取得了一些成果，但在多任務資源競爭的情況下，但是他們不考慮設備的負載情況，將任務大量映射到高速設備上，使系統負載極不均衡。在高競爭場景下，部分任務出現了2倍～3倍的執行效率下降。

部分研究[5-8]假定GPU是任務獨占性的，即一旦一個任務獲得了對GPU的訪問權，在當前任務完成之前，其它任務不能使用GPU。隨著GPU和OpenCL技術的發展，MPI+OpenCL已經被廣泛使用。GPU已經可以并行地執行不同的OpenCL內核。上述研究給出的調度方案極大偏離實際情況，單任務獨占設備的方案浪費了大量計算資源。

因此，鑒于當前研究的不足，本文考慮資源競爭對OpenCL內核執行的影響，提出了面向CPUs-GPUs系統的OpenCL任務調度框架，緩解異構調度算法在資源競爭環境下的性能下降現象，保障CPU-GPU異構系統的高效性。

為了驗證設備負載對任務執行時間的影響，選取宇宙學中最常用的N體運動模擬程序N-Body作為測試程序，實驗設備為Nvidia Titan RTX，軟件環境為CUDA 10.0 SDK，操作系統為Ubuntu 16.04，模擬輸入為1000個天體，記錄N-Body程序在設備Nvidia Titan RTX預先設置不同負載情況下的執行時間。

圖1顯示了N-Body基準測試在不同的GPU爭用情況下的運行時間(單位ms)。從圖中可以看出，在低負載時，即使有其它OpenCL內核在GPU中執行，對N-Body的執行時間幾乎沒有影響。隨著負載的增加，負載程序和N-Body之間存在著明顯的資源競爭，N-Body的執行時間明顯增加，大約是低負載時的2.7倍。

圖1 N-Body在不同負載下的GPU爭用 情況下的運行時間

上述實驗結果表明，資源競爭對OpenCL內核執行效率存在較大影響，從實驗角度進一步驗證了上述調度算法研究忽略資源競爭的不合理性。

2 調度框架介紹

OpenCL多任務調度系統包括3層：硬件、系統軟件、OpenCL任務調度層。OpenCL多任務調度系統如圖2所示。硬件層是最底層，由基于CPU和GPU構成的異構多核計算機構成，包含多個CPU和GPU，其中OpenCL主機程序運行在CPU上，OpenCL內核既可以運行在CPU上也可以運行在GPU上，主機程序通過直接訪問或者PCIe總線訪問設備。硬件層的頂部是系統軟件層，由操作系統和OpenCL運行時組成，為OpenCL程序運行提供軟件支持的同時，為上層調度系統提供相關的設備信息，操作系統提供設備負載等信息查詢接口，OpenCL運行時提供OpenCL設備性能等相關信息。OpenCL多任務調度程序位于異構系統的最頂層。系統中的用戶提交了不同的OpenCL程序，調度系統利用任務估計模塊對任務隊列中的任務進行評估，量化每一個OpenCL內核調度到不同設備上的開銷，由OpenCL內核調度器將內核調度到不同設備關聯的命令隊列中，由OpenCL運行時完成命令隊列中的相關命令分配，直到命令完成。

圖2 調度框架構成

本文提出的調度框架主要包括任務估計模塊，數據傳輸分析模塊和調度模塊。任務估計模塊又包括內核特征提取，設備特征提取和任務估計部分，特征提取模塊作為任務估計模塊的輸入，由任務估計模塊評估內核在設備上的運行時間。數據傳輸分析則是量化OpenCL內核所帶來的數據傳輸開銷。任務調度模塊則是根據上述模塊的輸出，為OpenCL內核選擇合適的設備進行調度。

3 任務估計

3.1 內核特征提取

圖3 內核特征提取流程

通過LLVM中間層語言來分析kernel，能夠盡可能多獲取kernel的靜態特征，規避了直接分析kernel代碼而導致的特征提取不充分的問題。LLVM匯編代碼比抽象語法樹更清楚地反映了OpenCL內核的行為。

除了靜態代碼特征外，還利用運行時參數來描述內核的動態特征和并行性質。內核的動態特性主要與數據的大小和線程的數量有關。根據OpenCL API所提供的函數獲取OpenCL運行時的內核動態特征，包括創建對象、數據傳輸、kernel啟動函數。創建內存對象功能參數主要包括內存大小、內存種類標簽、主機地址。數據傳輸功能參數主要包括傳輸模式、傳輸數據量大小。OpenCL內核啟動功能參數主要包括工作組數目，工作項數目和內核對象。

提取的內核特征見表1。

表1 內核特征

上述特征不僅包括內核行為，還包括內核結構，以及函數、內存等使用情況。

3.2 設備特征提取

現有研究中的設備靜態特征僅包括OpenCL設備的硬件固有屬性，包括核心數、L1 Cache大小、L2 Cache大小、內存大小等。然而，單純通過系統自帶的設備管理器所獲得的硬件屬性很難準確表征OpenCL設備的性能。該方案的設備特征提取器除了硬件本身的結構特征外，創新性地將基準分數作為設備特征的一部分。設備特征提取模塊集成了Geekbench 5基準測試程序來獲得設備在不同方面的性能分數[10]。設備特征提流程如圖4所示。

圖4 設備特征提取流程

設備特征提取器維護一個設備信息的數據庫。當OpenCL程序在讀取平臺下設備的時候，該框架根據OpenCL平臺所獲取的設備基本信息去設備信息表中查找對應的條目，如果存在該條目的完整信息，則從數據庫中讀取相應的設備信息，如果沒有，則通過運行對應的Geekbench 5基準測試程序，獲取其相關信息，并填入設備信息表中。該方法使得該框架能夠在運行過程中不斷擴充硬件信息，保證了該框架可以在各種硬件環境中廣泛使用。

設備動態特征主要用于描述設備的運行狀態，包括設備負載、內存使用和溫度。特征提取模塊通過操作系統層和OpenCL運行時接口獲取上述信息。設備靜態特征與動態特征相結合能很好表示該設備剩余計算資源的數目，有效反映對后續調度的影響，是該框架可以適用于任務資源競爭環境的重要保證。

表2展示了設備特征提取器所涉及的設備特征。

上述設備特征不僅包含基本硬件特征，還包括性能得分，與OpenCL內核行為相對應，有利于調度模塊學習設備與OpenCL內核的映射關系，其次設備的動態特征能夠很好表示系統中資源爭用情況，對后續調度具有重要意義。

3.3 模型構建

任務估計模塊通過構造一個基于機器學習的模型來預測內核的執行時間。建立一個基于機器學習的模型需要收集訓練數據。為了使訓練的模型獲得良好的泛化效果，從AMD APP Code Samples、Nvidia OpenCL Code Samples，Intel OpenCL SDK sample programs中選擇了85個基準測試程序。在不同負載的不同設備上運行它們，記錄OpenCL內核和設備的靜態與運行時特征，并記錄應用的計算時間，得到訓練數據約5000條，上述基準程序涵蓋了數值計算、圖像處理、加密算法、機器學習，幾乎包含了大多數應用類型，使得訓練數據能夠覆蓋常見的OpenCL應用程序。為接下來的模型訓練提供良好的數據基礎。

表2 設備特征

本文采用K最鄰近算法(K-nearest neighbor，KNN)、支持向量機(support vector machine，SVM)、隨機森林(random forest，RF)、樸素貝葉斯(Naive Bayes，NB)和貝葉斯網絡(bayesian network，BN)這5種預測模型進行訓練，得到模型在測試集上的預測的可決系數。

圖5展示了，上述5類常見算法在測試集上的預測模型可決系數的變化。

圖5 特征篩選后各算法預測準確率

選擇KNN、SVM、RF、NB和BN作為對比算法的主要原因是該框架作為運行時調度框架，具有強實時性。較為復雜的算法，受限于計算時間難以滿足實時性需求，因此選取這些常見且簡單模型。文獻[11]驗證了復雜算法在實時調度領域應用的難點，僅能支持上述幾種簡單模型和三層的神經網絡。針對XGboost和復雜神經網絡等較為復雜的模型算法，實時性方面表現較差。隨機森林算法具有很好的預測準確性的同時，還具有很好的抗噪聲能力。根據上述分析選取隨機森林算法構建任務估計模型。

4 數據傳輸

OpenCL平臺模型由主機和多個OpenCL設備構成，除了內核部分外，OpenCL程序中均在主機上運行，而內核則在OpenCL設備上運行。該平臺模型的結構導致主機和OpenCL設備間存在不可避免的數據交互。隨著應用數據規模的增加，以及數據傳輸速率發展遠遠跟不上處理器運算速率的發展速度，數據傳輸已經成為OpenCL高性能計算的一大瓶頸[12]。

本文框架借鑒現有的研究[13,14]等對于數據傳輸采用了簡化處理，假設在OpenCL平臺中，內核調度到CPU中時，內核可以直接訪問內存，數據傳輸時間為0；內核調度到GPU時數據傳輸時間僅和數據傳輸規模和PCIe總線帶寬有關，用公式表示如下

其中，tGPU表示數據傳輸到GPU所需要的時間，tCPU表示數據傳輸到CPU所需要的時間，Sdata表示數據的大小，BdPCIe表示總線帶寬。

該公式有一定的借鑒意義，但是也有一定的不合理性。數據傳輸命令的生命周期包括命令入隊、命令調度、命令載入、命令啟動、命令執行和命令結束部分，其中命令入隊到命令啟動是數據傳輸啟動的固有開銷；命令執行則是數據傳輸過程，OpenCL包含多種緩沖區和數據傳輸模式，傳輸速度有明顯差異，通過理論和實驗分析提出了新的數據傳輸量化公式

5 調度模型

本文提出的異構調度算法包含兩個目標：負載均衡和單任務執行時間。負載均衡定義為將負載(工作任務)進行平衡、分攤到多個處理單元上進行執行，是衡量系統中不同處理單元任務分配的均衡程度。單任務執行時間是衡量單個任務執行效率的最常用指標。

為了衡量一個OpenCL調度到某個設備上的負載變化情況，提出通過OpenCL內核的并行度，即工作組和工作組中工作項數目的乘積來表示OpenCL內核所需要的計算資源，該理念符合OpenCL執行模型和CPU-GPU的體系結構。OpenCL內核在OpenCL啟動時，根據OpenCL API的相關指令，將設備上的OpenCL內核按照指定維度進行劃分，內核依據偏移量平鋪到設備對應的內核。OpenCL內核工作項映射到內核由硬件實現保證，映射方式比較靈活，現在設備并不按照偏移量進行映射。當設備計算資源充足時，即當前剩余核心數目大于等于OpenCL內核啟動命令設置的工作項數目時，該內核的所有工作組可同時執行；當設備計算資源不足時，即當前剩余核心數目小于OpenCL內核啟動命令設置的工作項數目時，一部分工作組中的工作項先行執行，其它工作項阻塞，直到有工作項執行結束，再將工作項調度到空閑核心上。工作項映射到OpenCL核心的方式驗證了本文提出的設備負載量化機制，能夠準確預測OpenCL內核調度到設備上所造成的負載影響。

因此通過如下公式估計內核調度到指定設備后，該設備的計算資源使用情況表示為

其中，Li表示設備i的計算資源使用情況，CRJi表示內核調度到設備i后(實際未調度)，設備i上執行內核工作項數組之和，Corei表示設備i所具有的OpenCL(CUDA)核心數目。

因此，得到系統的負載均衡程度Comload， 定義如下

其中，μ表示系統中設備的平均負載，μ按照如下公式計算

如果僅采用負載均衡程度作為調度依據，會導致大量內核被調度到低速設備上，使得任務執行效率下降，因此結合負載均衡度和任務執行效率，提出調度評價函數f(Ji,Pi)， 計算公式如下

其中，α表示獨立參數，用來調整內核執行時間和系統整體負載均衡度之間的占比，可根據實際應用場景需求，調整參數盡可能對單任務執行時間和系統負載進行折衷處理。Tji表示按照OpenCL調度開銷模型估計內核Jj調度到設備Pi的時間開銷，Tmin和Tmax表示按照OpenCL調度開銷模型估計內核Jj調度到系統中設備的最短時間和最長時間開銷。Tji包括任務估計模塊對內核執行時間估計以及數據傳輸開銷，由如下公式計算

因此整個調度框架流程如圖6所示。

圖6 調度算法流程

上述步驟展示了OpenCL任務的一個內核調度的完整過程，當前內核處理結束后，該程序按照任務提交的順序，逐個處理直到所有任務執行結束。

6 實 驗

在這一節中，將描述本文的實驗設置和所使用的評估指標及方法。

6.1 實驗設置

在兩個CPU-GPU異構系統上評估本文提出的方法。其中一個系統包含兩塊Intel(R) Xeon(R) Gold 6151@3.00GHz CPU和8塊NVIDIA Titan RTX，第二個系統包含一塊Intel Core i7-10870H CPU和兩塊AMD Radeon RX 6900 XT。實驗使用OpenCL SDK包括NVIDIA CUDA Toolkit 10.1，Intel SDK for OpenCLTMApplications和AMD APP SDK 3.0。系統一的操作系統為Ubuntu 16.04，系統二的操作系統為Windows 10。硬件平臺的詳情見表3。

表3 硬件平臺信息

系統一包含兩個OpenCL平臺，分別為Intel和Nvidia平臺，Intel平臺下有兩個設備，Nvidia平臺下有8個設備，OpenCL版本為2.0。系統二也包含兩個OpenCL平臺，分別為Intel和AMD平臺，Intel平臺下有一個設備，Nvidia平臺下有兩個設備，OpenCL版本為分別為1.2和3.0。上述OpenCL運行時和操作系統共同構成了測試的軟件層。

實驗選擇了兩個主流基準套件(Parboil OpenCL基準套件和Ploybench基準套件)來驗證該框架的性能。主要包括Parboil基準套件BFS、Cutup、Sgemm和Spmv等程序以及Ploybench基準套件中的ATAX、BICG、CORR、GESUMMV和SYRK等程序，輸入規模為4 M-1 G。上述兩個基準測試在OpenCL調度系統性能測試中具有很好的代表性，在諸多論文實驗中廣泛應用。

為了能夠驗證該框架能夠適應不同程度的資源競爭場景，實驗調整任務提交的時間間隔，使得測試環境分別處于低資源競爭(平均負載小于40%)、中資源競爭(平均負載大于40%小于70%)和高資源負載(平均負載大于70%)，用戶按照一定的時間間隔向上述異構系統提交任務。用戶在3種場景下提交任務間隔為5 min，1 min和10 s。

對比方法選擇主流的兩個OpenCL調度框架：最佳匹配度調度框架；MultiCL框架。

(1)最佳匹配度調度框架(MDS)：根據OpenCL內核代碼特征和設備匹配程度進行任務調度。

(2)MultiCL框架：基于OpenCL運行時特征實現自動化命令隊列調度。

上述兩個調度框架是除開發人員手動調度外，較為常見且高效的調度框架，其中以最佳匹配調度框架作為基準，對比實驗結果。

6.2 評價指標

為了評估本文所提出的框架，實驗使用了兩個性能指標：系統中任務執行總時間和負載平衡度。這兩個指標已被廣泛用于評估多任務環境中調度方法的性能。該框架的目標是優化任務執行總時間，這通常會導致系統的負載均衡。這兩個指標的定義如下。

任務執行總時間由系統中最后的任務完成時間減去任務開始時間表示，這是調度方法性能的最直接表示，體現了此調度方案下的執行效率。

負載平衡度[17]是用來量化系統中設備的負載平衡程度。它可以定義如下

其中，Vlb代表系統的平均負載。m代表設備的數量。loadk代表設備k的負載不同，該部分負載不是調度前的估計值，而是調度后通過設備管理器獲取的實際負載值。Vlb數值越小，說明系統負載就越均衡。該指標通過數學的方式，將系統負載均衡程度量化。

7 結果及分析

在這一節中，詳細介紹了上述實驗結果，并對實驗結果進行了分析，說明本文所提出調度框架在不同資源競爭環境下的表現。

實驗將不同數據規模的Parboil OpenCL基準套件和Ploybench基準套件程序作為任務按照不同的時間間隔提交到在第6節所敘述的兩個異構系統上，統計上述兩個系統的任務執行總時間和系統負載均衡程度，為了直觀對比3個調度框架的性能，將得到的上述指標均比上基準框架(即最佳匹配度調度框架)，得到數據如圖7和圖8所示。

圖7 不同資源競爭程度下任務執行總時間

圖8 不同資源競爭程度下系統負載均衡度

實驗結果顯示在圖7和圖8中。圖7顯示了3種程度的資源競爭場景下3種調度方案的總任務完成時間，圖8顯示了3種負載情況下3種調度方案的系統負載平衡度。本文提出的框架在低資源競爭情況下，相比于MDS算法，任務執行時間幾乎持平，僅延遲了1%，系統負載均衡度方面較好，約4%提升；相比于MultiCL任務執行時間有明顯優勢，縮短了約13%，負載均衡度提升約2%。中資源競爭場景下，相比于MDS算法，任務執行時間縮短19%，負載均衡度指標提升20%；相比于MultiCL任務執行時間提升約10%，負載均衡度指標提升約9%。高資源競爭場景下，本文提出的框架表現出良好性能，相比于MDS算法，任務執行時間縮短了約27%，系統負載均衡度指標提升約29%；相比于MultiCL框架，任務執行效率提升約16%，系統負載均衡度指標提升約12%。本文提出的框架在低資源競爭情況下與MDS算法性能幾乎持平，略高于MultiCL框架，在中高資源競爭下，性能明顯高于MDS算法和MultiCL，符合預期。

除此之外為了驗證該調度框架滿足OpenCL多任務調度的實時性要求，針對上述實驗在兩個系統中所執行的Parboil OpenCL基準套件和Ploybench基準套件程序，統計各基準程序在兩個CPU-GPU系統中數據傳輸，OpenCL內核計算以及調度所產生的時間占比，如圖9所示。

圖9 數據傳輸、調度系統和任務執行時間時間占比

從圖9可以看出，針對Parboil OpenCL基準套件中的BFS、Cutup、Sgemm和Spmv程序以及Ploybench基準套件中的ATAX、BICG、CORR、GESUMMV和SYRK程序，本文提出的調度框架在調度階段耗時僅占有計算的0.4%～2.1%，該時間僅為調度模塊的計算時間加上動態特征提取帶來的時間開銷，靜態特征提取可在程序初始化階段完成，從圖中可以看出，該調度框架調度耗時與計算時間相比幾乎可以忽略，滿足OpenCL運行時的實時性要求。

其次對比圖7和圖8，本文所提出的調度框架所引入的額外開銷遠小于本文框架所帶來的性能提升，也充分驗證了該框架具有良好的實際運用價值。

結合上述，在現在主流的兩類CPU+GPU的異構系統中，本文所提出的基于資源爭用的調度框架在不同程度的資源競爭場景下均表現出良好性能，在任務總執行時間和系統負載均衡度兩個指標持平或優于MDS和MultiCL，尤其是在中高資源競爭場景下，該框架表現出良好的性能優勢，同時也滿足了OpenCL運行時的實時性要求。

8 結束語

本文提出了一個基于CPU-GPU異構平臺上資源爭用的自適應、智能化OpenCL多任務調度框架。該框架使用OpenCL內核和設備的靜態和動態特性來分析任務，為任務調度提供良好的數據支持。并提出了適用于CPU-GPU異構系統的OpenCL數據傳輸開銷量化公式。最后通過內核并行度估計內核調度后的設備負載變化，結合內核執行時間，在盡可能滿足系統負載均衡的同時，保障單個任務的執行效率。實驗驗證在存在中高程度的任務間競爭環境下，與其它常見的方法相比，它展現出明顯的性能改進。