基于負(fù)載均衡的CPU- GPU異構(gòu)計(jì)算平臺(tái)任務(wù)調(diào)度策略

方 娟，章佳興

(1.北京工業(yè)大學(xué)信息學(xué)部，北京 100124; 2.北京工業(yè)大學(xué)北京智慧城市研究院，北京 100124)

隨著制造工藝的升級(jí)，計(jì)算機(jī)體系結(jié)構(gòu)發(fā)生了巨大的變革. 單核處理器結(jié)構(gòu)被物理設(shè)計(jì)極限和能耗等因素制約，必然導(dǎo)致摩爾定律[1]的重點(diǎn)由單純的晶體管數(shù)量轉(zhuǎn)移到可以被集成在芯片上的核心數(shù)量[2].

在中央處理單元- 圖形處理單元(central processing unit-graphics processing unit，CPU- GPU)結(jié)構(gòu)中，CPU具有較大的緩存和大量邏輯運(yùn)算單元，被設(shè)計(jì)用于處理復(fù)雜的任務(wù). 大緩存和邏輯運(yùn)算單元可以保證數(shù)據(jù)運(yùn)算的低延遲，在較少時(shí)鐘周期內(nèi)完成計(jì)算任務(wù). CPU還有很多的加速分支判斷和復(fù)雜的邏輯判斷硬件用來(lái)提高分支預(yù)測(cè)能力，降低延遲. GPU是基于大吞吐量的設(shè)計(jì)，具有大量的算術(shù)邏輯單元和很少的緩存，擅長(zhǎng)大規(guī)模并行計(jì)算. 在2003年以后，數(shù)學(xué)家和經(jīng)濟(jì)學(xué)家注意到多核心的GPU非常適合并行任務(wù)的處理，逐步將GPU用于通用計(jì)算領(lǐng)域. 英偉達(dá)(NVIDIA)、超威半導(dǎo)體(AMD)和蘋(píng)果(Apple)等公司分別提出了GPU通用并行計(jì)算技術(shù)Cuda、ATI Stream和OpenCL，GPU開(kāi)始被廣泛應(yīng)用在數(shù)學(xué)、金融等各類(lèi)通用計(jì)算領(lǐng)域.

異構(gòu)計(jì)算系統(tǒng)指使用不同類(lèi)型指令集和體系架構(gòu)的計(jì)算單元組成的計(jì)算系統(tǒng). 目前，異構(gòu)計(jì)算系統(tǒng)已經(jīng)延伸到CPU、GPU、數(shù)字信號(hào)處理(digital signal processing，DSP)、現(xiàn)場(chǎng)可編程門(mén)陣列(field programmable gate array，F(xiàn)PGA)、專用集成電路(application specific integrated circuit，ASIC)和其他固定加速器等，不同的計(jì)算單元相互協(xié)作共同完成計(jì)算任務(wù). 其中CPU- GPU是目前最為主流、應(yīng)用最廣的異構(gòu)系統(tǒng)架構(gòu).

1 CPU- GPU處理器調(diào)度

傳統(tǒng)的CPU- GPU異構(gòu)計(jì)算平臺(tái)的任務(wù)調(diào)度策略中CPU負(fù)責(zé)串行計(jì)算部分，GPU管理并提供GPU運(yùn)算所需數(shù)據(jù)以及接收GPU計(jì)算完成的結(jié)果[3-5]. Iturriaga等[6]在CPU- GPU異構(gòu)平臺(tái)上使用改進(jìn)的隨機(jī)搜索方法gPALS來(lái)實(shí)現(xiàn)異構(gòu)計(jì)算系統(tǒng)中的調(diào)度問(wèn)題. 王彥華等[7]使用支持向量機(jī)(support vector machine，SVM)的分類(lèi)方法將計(jì)算任務(wù)區(qū)分為CPU型和GPU型，然后按照任務(wù)類(lèi)型派發(fā)給適合的處理器.

此類(lèi)調(diào)度策略容易實(shí)施，但CPU等待GPU計(jì)算結(jié)果的時(shí)間對(duì)于高效的計(jì)算單元來(lái)說(shuō)無(wú)疑是一種嚴(yán)重的性能浪費(fèi).

鑒于上述情況，研究者將并行任務(wù)分割成不同的部分，CPU和GPU同時(shí)處理并行任務(wù)的不同部分，平衡CPU與GPU的負(fù)載[8-12]. 這能夠避免計(jì)算單元空閑，縮短任務(wù)計(jì)算時(shí)間，提升系統(tǒng)性能. 雖然CPU和GPU對(duì)于任務(wù)的處理具有偏好性，但使用2種處理器共同處理計(jì)算任務(wù)，仍然能夠提升性能.

CPU- GPU異構(gòu)計(jì)算系統(tǒng)靜態(tài)調(diào)度策略指在系統(tǒng)運(yùn)行之前就已經(jīng)確定好調(diào)度方案. Alsubaihi等[8]提出了一種面向高性能和能耗的多目標(biāo)資源分配方案，使用粒子群算法(partical swarm optimization,PSO)求解高效的負(fù)載分配比例，但是該方案在計(jì)算小規(guī)模任務(wù)時(shí)，PSO求解調(diào)度方案的時(shí)間相比任務(wù)處理的時(shí)間過(guò)長(zhǎng). Shulga等[9]使用機(jī)器學(xué)習(xí)(machine-learning,ML)的方法處理調(diào)度問(wèn)題. 文中指出在一定場(chǎng)景中，某類(lèi)型的處理器負(fù)載過(guò)高，限制了系統(tǒng)性能，將一些任務(wù)加載到另一類(lèi)型的處理器上能提升系統(tǒng)性能.

靜態(tài)調(diào)度策略[10]調(diào)度開(kāi)銷(xiāo)較小，容易實(shí)施，但是易造成負(fù)載不均. 對(duì)于一些CPU與GPU計(jì)算速度相差較大的應(yīng)用，負(fù)載不均帶來(lái)的性能浪費(fèi)尤為明顯. 靜態(tài)調(diào)度只能針對(duì)特定的CPU- GPU結(jié)構(gòu)，當(dāng)計(jì)算單元型號(hào)(計(jì)算能力)改變后，靜態(tài)調(diào)度確定的劃分比例不再適用. 對(duì)于CPU與GPU區(qū)分明顯的應(yīng)用，可能會(huì)降低系統(tǒng)性能表現(xiàn).

CPU- GPU異構(gòu)計(jì)算系統(tǒng)動(dòng)態(tài)調(diào)度策略[10]是指在操作環(huán)境與計(jì)算任務(wù)不確定情況下進(jìn)行的調(diào)度. 調(diào)度過(guò)程中根據(jù)CPU和GPU的負(fù)載情況調(diào)節(jié)分配的數(shù)據(jù)量，確保不同類(lèi)型計(jì)算單元負(fù)載均衡. 動(dòng)態(tài)調(diào)度基本解決了靜態(tài)調(diào)度只針對(duì)固定CPU- GPU結(jié)構(gòu)和負(fù)載不均較大的問(wèn)題，但是動(dòng)態(tài)調(diào)度帶來(lái)的內(nèi)存和時(shí)間開(kāi)銷(xiāo)較大，對(duì)整體系統(tǒng)性能的影響較明顯.

Ma等[11]設(shè)計(jì)了一個(gè)分步調(diào)度方案，根據(jù)上一周期處理器計(jì)算能力動(dòng)態(tài)調(diào)整下一周期計(jì)算量的分配，使CPU和GPU計(jì)算任務(wù)的完成時(shí)間差較小，保證不同類(lèi)型處理器負(fù)載均衡. Shen等[12]通過(guò)負(fù)載預(yù)測(cè)調(diào)度(load-prediction scheduling,LPS)技術(shù)平衡不同類(lèi)型處理器的工作負(fù)載. Vilches等[13]提出了一種新的自適應(yīng)分區(qū)(adaptive partitioning)調(diào)度策略，特別是針對(duì)運(yùn)行在CPU- GPU異構(gòu)芯片上的不規(guī)則應(yīng)用而設(shè)計(jì)的. 這項(xiàng)工作的創(chuàng)新在于，分配給CPU和GPU的工作負(fù)載的大小可以動(dòng)態(tài)地進(jìn)行調(diào)整，以最大限度地平衡設(shè)備之間的工作負(fù)載，提高異構(gòu)計(jì)算單元利用率.

2 調(diào)度策略

2.1 負(fù)載均衡

CPU- GPU異構(gòu)計(jì)算平臺(tái)負(fù)載均衡指加載到CPU與GPU的計(jì)算任務(wù)在同一時(shí)間完成.

定義：T表示當(dāng)計(jì)算量為X時(shí)的計(jì)算時(shí)間，則處理器計(jì)算該任務(wù)的計(jì)算速度為

(1)

設(shè)計(jì)算任務(wù)的數(shù)據(jù)量總和為S，CPU與GPU計(jì)算該任務(wù)的速度分別為VCPU和VGPU，CPU與GPU共同參與計(jì)算所用的時(shí)間分別為T(mén)CPU和TGPU，則S可表示為

S=VCPUTCPU+VGPUTGPU

(2)

設(shè)δ(δ>0)為系統(tǒng)的負(fù)載不均程度，δ越小表明系統(tǒng)負(fù)載不均越小.δ可表示為

(3)

理想狀態(tài)下δ=0，即當(dāng)TCPU=TGPU時(shí)負(fù)載均衡，設(shè)此時(shí)CPU和GPU分配的數(shù)據(jù)量比值為P，可推出

(4)

由式(4)可得，負(fù)載均衡狀態(tài)CPU與GPU所分配的數(shù)據(jù)量為

(5)

2.2 基于隊(duì)列的混合調(diào)度策略

影響系統(tǒng)性能穩(wěn)定性的因素眾多且動(dòng)態(tài)調(diào)度過(guò)程的資源分配和時(shí)間消耗開(kāi)銷(xiāo)過(guò)大[14]，因此，本文提出基于隊(duì)列的混合調(diào)度策略，在并行任務(wù)處理前將計(jì)算任務(wù)存入雙向隊(duì)列，在派發(fā)計(jì)算任務(wù)給不同類(lèi)型處理器時(shí)，CPU從隊(duì)首派發(fā)，GPU從隊(duì)尾派發(fā). 該策略核心是預(yù)測(cè)和分配，由式(4)(5)可知，SCPU和SGPU由VCPU和VGPU求解.VCPU和VGPU是策略的預(yù)測(cè)的關(guān)鍵.該策略按照以下4個(gè)步驟完成.

第1步 首先檢測(cè)該系統(tǒng)是否第一次運(yùn)行該程序，若是，則將CPU與GPU的計(jì)算量按照

sCPU=sGPU=0.05S

(6)

分別派發(fā)給CPU與GPU,探測(cè)異構(gòu)計(jì)算系統(tǒng)對(duì)該類(lèi)任務(wù)的計(jì)算能力；否則讀取系統(tǒng)存儲(chǔ)的分配比值P，按照

(7)

計(jì)算量派發(fā)，驗(yàn)證當(dāng)前分配比例是否適合此時(shí)系統(tǒng)狀態(tài).

第2步 根據(jù)系統(tǒng)第一階段的CPU計(jì)算時(shí)間tCPU和GPU計(jì)算時(shí)間tGPU推導(dǎo)系統(tǒng)當(dāng)前狀態(tài)，計(jì)算該任務(wù)的性能比值p，當(dāng)系統(tǒng)第一次運(yùn)行該程序時(shí)，比值p由

(8)

求解，否則由

(9)

求解.

探測(cè)階段的負(fù)載不均程度δ′公式為

(10)

當(dāng)δ′>μ時(shí)，更新計(jì)算量分配比例P=p；當(dāng)δ′≤μ時(shí)，計(jì)算量分配比例P不需改變. 其中μ為系統(tǒng)設(shè)置閾值.

第3步 混合調(diào)度階段，將全部數(shù)據(jù)量的80%按照上一步確定的比例派發(fā)給CPU和GPU. 剩余的10%進(jìn)行動(dòng)態(tài)調(diào)度，先完成計(jì)算任務(wù)的處理器不需等待后完成的處理器，直接進(jìn)入隊(duì)列動(dòng)態(tài)調(diào)度階段，后完成的處理器在完成分配的數(shù)據(jù)量之后也進(jìn)入隊(duì)列動(dòng)態(tài)調(diào)度階段，直至隊(duì)列首尾相遇，計(jì)算任務(wù)全部完成.

第4步 統(tǒng)計(jì)混合調(diào)度階段中靜態(tài)調(diào)度計(jì)算任務(wù)的CPU與GPU的計(jì)算時(shí)間t′CPU和t′GPU. 通過(guò)計(jì)算時(shí)間求得系統(tǒng)當(dāng)前計(jì)算任務(wù)的最優(yōu)分配比例

(11)

設(shè)P與P′離散程度為Δ，Δ用

(12)

表示.

當(dāng)Δ>ν時(shí)，更新異構(gòu)計(jì)算系統(tǒng)CPU與GPU負(fù)載比為P′，其中ν為系統(tǒng)設(shè)置閾值.

基于隊(duì)列的混合調(diào)度策略流程圖如圖1所示.

3 性能測(cè)試

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)采用的計(jì)算平臺(tái)為曙光W580- G20，運(yùn)行Linux系統(tǒng)，CPU為Intel Xeon(R) CPU E5- 2620；GPU為NVIDIA Tesla P100；內(nèi)存128GB、硬盤(pán)2TB. CPU和GPU擁有各自獨(dú)立的內(nèi)存空間，通過(guò)PCIE總線互聯(lián).

本文選用4組基準(zhǔn)測(cè)試程序，其中MatMul是并行計(jì)算領(lǐng)域經(jīng)典的測(cè)試程序；Pathfinder和Kmeans來(lái)自最新版本的Rodinia測(cè)試集；Nbody為NVIDIA官方測(cè)試用例.

3.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)選取的4組基準(zhǔn)測(cè)試程序均在CPU- GPU異構(gòu)計(jì)算平臺(tái)調(diào)試通過(guò)，根據(jù)數(shù)據(jù)計(jì)算時(shí)間衡量系統(tǒng)性能.

本文對(duì)所提出的調(diào)度策略進(jìn)行了廣泛的評(píng)估，將其與傳統(tǒng)調(diào)度算法、靜態(tài)調(diào)度算法和動(dòng)態(tài)與靜態(tài)相結(jié)合的調(diào)度算法進(jìn)行對(duì)比測(cè)試.

3.2.1 基準(zhǔn)測(cè)試程序MatMul

MatMul屬于微矩陣測(cè)試程序，是并行計(jì)算領(lǐng)域經(jīng)典測(cè)試用例. 實(shí)驗(yàn)在并行數(shù)據(jù)計(jì)算部分設(shè)有大量微矩陣. 微矩陣選用長(zhǎng)寬均為100的方陣. 本實(shí)驗(yàn)異構(gòu)計(jì)算平臺(tái)中的Intel Xeon(R) CPU E5- 2620和Tesla P100計(jì)算單個(gè)微矩陣的時(shí)間分別為6～7 ms和3～4 ms，在當(dāng)前CPU- GPU異構(gòu)計(jì)算平臺(tái)上GPU處理MatMul測(cè)試程序能力強(qiáng)于CPU.

經(jīng)過(guò)優(yōu)化后的調(diào)度算法與傳統(tǒng)調(diào)度算法的具體性能數(shù)據(jù)對(duì)比如表1所示. 靜態(tài)調(diào)度策略對(duì)4組不同數(shù)據(jù)量的性能提升分別為12.87%、9.92%、6.54%和12.87%；靜態(tài)與動(dòng)態(tài)相結(jié)合的調(diào)度策略對(duì)4組不同數(shù)據(jù)量的性能提升分別為18.37%、15.92%、14.79%和18.14%. 雖然2種調(diào)度策略對(duì)系統(tǒng)性能有明顯提升，但波動(dòng)較明顯. 基于隊(duì)列的混合調(diào)度策略對(duì)4組數(shù)據(jù)量的性能提升分別為31.74%、29.79%、28.20%和30.14%.

表1 MatMul性能

如圖2所示，經(jīng)過(guò)優(yōu)化的3種調(diào)度策略相對(duì)于傳統(tǒng)調(diào)度算法都有明顯的性能提升，靜態(tài)調(diào)度策略平均有10.55%的提升；靜態(tài)與動(dòng)態(tài)相結(jié)合的調(diào)度策略平均有16.80%的提升；基于隊(duì)列的混合調(diào)度策略平均有29.98%的提升，基于隊(duì)列的混合調(diào)度策略在性能提升效果上明顯優(yōu)于其他2種策略.

3.2.2 基準(zhǔn)測(cè)試程序PathFinder

PathFinder是路徑尋找測(cè)試程序，按照金字塔路徑尋找從矩陣頂部到底部的最短距離. 實(shí)驗(yàn)選用長(zhǎng)10 000、寬100的矩陣作為PathFinder數(shù)據(jù)實(shí)例. 使用本系統(tǒng)CPU與GPU計(jì)算單個(gè)矩陣金字塔距離的時(shí)間分別為0.60～0.67 ms和1.11～1.12 ms. 該測(cè)試用例的CPU計(jì)算性能優(yōu)于GPU，這也是選取本實(shí)例的主要原因.

當(dāng)數(shù)據(jù)量分別為5 000、10 000、40 000和50 000時(shí)，傳統(tǒng)任務(wù)調(diào)度算法與其他3種調(diào)度算法的性能差距如表2所示. 與傳統(tǒng)調(diào)度算法相比，靜態(tài)調(diào)度策略在4組測(cè)試實(shí)例中性能分別提升了15.02%、13.70%、11.11%和7.37%；靜態(tài)與動(dòng)態(tài)相結(jié)合的調(diào)度策略性能分別提升了18.44%、20.01%、13.65%和22.03%；基于隊(duì)列的混合調(diào)度策略性能分別提升28.64%、27.13%、26.94%和27.77%.

表2 PathFinder性能

如圖3所示，靜態(tài)調(diào)度策略、靜態(tài)與動(dòng)態(tài)相結(jié)合的調(diào)度策略和基于隊(duì)列的混合調(diào)度策略與傳統(tǒng)調(diào)度算法相比在性能上平均有11.80%、18.53%和27.62%的提升.

3.2.3 基準(zhǔn)測(cè)試程序Kmeans

Kmeans算法是基于迭代求解的聚類(lèi)算法，單次迭代過(guò)程需計(jì)算每個(gè)點(diǎn)到K個(gè)聚類(lèi)中心點(diǎn)的距離. 使用本系統(tǒng)計(jì)算單個(gè)Kmeans實(shí)例的CPU和GPU耗時(shí)范圍分別約為0.27～0.32 ms和0.15～0.20 ms. 該程序的GPU計(jì)算速度優(yōu)于CPU計(jì)算速度.

當(dāng)樣本數(shù)據(jù)量為2 000、4 000、10 000和20 000時(shí)，不同調(diào)度算法耗時(shí)如表3所示. 計(jì)算易得，與傳統(tǒng)調(diào)度方案性能相比，靜態(tài)調(diào)度策略和靜態(tài)與動(dòng)態(tài)相結(jié)合的調(diào)度策略對(duì)4組數(shù)據(jù)量分別有21.17%、14.79%、18.17%、12.05%、16.76%、16.97%、18.95%和13.57%的性能提升；基于隊(duì)列的混合調(diào)度策略對(duì)4組數(shù)據(jù)量分別有25.38%、28.27%、27.18%和25.72%的性能提升.

表3 Kmeans性能展示

3種調(diào)度算法的優(yōu)化效果如圖4所示. 靜態(tài)調(diào)度策略、靜態(tài)與動(dòng)態(tài)相結(jié)合的調(diào)度策略和基于隊(duì)列的混合調(diào)度策略的平均性能提升為16.54%、16.56%和26.64%.

3.2.4 基準(zhǔn)測(cè)試程序Nbody

多體問(wèn)題(Nbody)是一個(gè)非常著名的物理問(wèn)題. 該問(wèn)題研究N個(gè)星體間作用力問(wèn)題，這類(lèi)程序?qū)儆贑PU與GPU計(jì)算能力相差懸殊的應(yīng)用類(lèi)型. 當(dāng)將星體數(shù)量設(shè)為8 192時(shí)，GPU處理時(shí)間為6.99 ms，CPU處理時(shí)間為17.330 97 s. CPU和GPU在處理該實(shí)例的計(jì)算速度差距非常懸殊，理論的性能提升可以忽略不計(jì). 系統(tǒng)內(nèi)部計(jì)算時(shí)間的誤差大于基于負(fù)載均衡的性能提升空間. 實(shí)際調(diào)度在執(zhí)行過(guò)程中因?yàn)樘砑铀惴ǖ拈_(kāi)銷(xiāo)導(dǎo)致結(jié)果更差.

通過(guò)對(duì)比發(fā)現(xiàn)，本文設(shè)計(jì)的任務(wù)調(diào)度策略對(duì)于CPU與GPU計(jì)算差距在同數(shù)量級(jí)類(lèi)型的程序有明顯的性能提升. 其中基于隊(duì)列的混合調(diào)度策略在性能表現(xiàn)上明顯優(yōu)于其他2種，對(duì)本文選用的MatMul、Pathfinder和Kmeans三個(gè)基準(zhǔn)測(cè)試程序系統(tǒng)性能分別提升了29.97%、27.62%和26.63%，平均提升了28.08%. 其他2種調(diào)度方案相比于傳統(tǒng)調(diào)度方案平均分別提升了12.96%和17.30%. 具體性能提升對(duì)比見(jiàn)圖5.

對(duì)于CPU與GPU計(jì)算差距懸殊的應(yīng)用，理論上負(fù)載均衡不再是此類(lèi)應(yīng)用提升性能的方法，應(yīng)該更多地考慮單CPU/GPU的優(yōu)化方案.

4 結(jié)論

1) 文中設(shè)計(jì)的任務(wù)調(diào)度策略對(duì)于大部分應(yīng)用性能提升明顯，該策略在任務(wù)處理前將計(jì)算任務(wù)存入雙向隊(duì)列，并結(jié)合了動(dòng)態(tài)調(diào)度策略，平衡負(fù)載能力更強(qiáng). 從不同數(shù)據(jù)量的同組實(shí)例可得出結(jié)論，系統(tǒng)運(yùn)行的實(shí)時(shí)性能并不穩(wěn)定，導(dǎo)致靜態(tài)調(diào)度策略和靜態(tài)與動(dòng)態(tài)相結(jié)合的調(diào)度策略對(duì)于性能提升實(shí)際值與理論值差距較大且性能波動(dòng)較為明顯，2種策略在相同實(shí)驗(yàn)環(huán)境下最大分別有9%和8%的波動(dòng)，而基于隊(duì)列的混合調(diào)度策略只有不到4%.

2) 本文設(shè)計(jì)的任務(wù)調(diào)度策略能夠有效平衡異構(gòu)計(jì)算平臺(tái)CPU與GPU負(fù)載，同時(shí)構(gòu)建任務(wù)隊(duì)列和10%動(dòng)態(tài)調(diào)度所造成的時(shí)間開(kāi)銷(xiāo)不會(huì)對(duì)系統(tǒng)性能產(chǎn)生明顯影響.

3) 文中設(shè)計(jì)的任務(wù)調(diào)度策略均適合CPU與GPU計(jì)算性能處于同一數(shù)量級(jí)應(yīng)用. 對(duì)于CPU與GPU性能相差巨大的應(yīng)用，提升效果不明顯. 例如文中采用的Nbody實(shí)例，該實(shí)例GPU計(jì)算速度是CPU的近2 500倍，理論的性能提升可以忽略不計(jì). 此類(lèi)型實(shí)例的局限性決定了優(yōu)化方法，與算法無(wú)關(guān).

4) 本文設(shè)計(jì)的任務(wù)調(diào)度策略對(duì)系統(tǒng)性能提升明顯，不需修改即可適應(yīng)不同計(jì)算單元型號(hào)(計(jì)算能力)的CPU與GPU. 值得指出的是，異構(gòu)平臺(tái)的負(fù)載受CPU和GPU計(jì)算能力影響較大，對(duì)于不同型號(hào)CPU與GPU，實(shí)際劃分比例可能區(qū)別較大，產(chǎn)生的性能提升效果會(huì)有明顯差異.