李薛劍, 陳 豪, 朱 凱

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601)

?

基于DTPS算法的異構(gòu)集群優(yōu)化策略

李薛劍, 陳 豪, 朱 凱

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601)

隨著高性能計(jì)算機(jī)的發(fā)展，一種基于CPU-GPU的異構(gòu)集群逐漸被人們所關(guān)注。相比于傳統(tǒng)集群，它更經(jīng)濟(jì)環(huán)保，且擁有更高的運(yùn)算速度。但異構(gòu)模式下效率較低的短板也限制著異構(gòu)集群的發(fā)展。本文提出的DTPS算法，通過動(dòng)態(tài)調(diào)整異構(gòu)集群下CPU與GPU任務(wù)劃分的比例，整合集群計(jì)算資源，使集群的計(jì)算效率達(dá)到相對較高的水平，并通過實(shí)驗(yàn)證明了算法的有效性。

異構(gòu)集群； 任務(wù)劃分； 任務(wù)調(diào)度； 動(dòng)態(tài)調(diào)整

0 引 言

隨著計(jì)算需求的增大，超級計(jì)算機(jī)得到迅速發(fā)展。因技術(shù)上的瓶頸，傳統(tǒng)的通過提高CPU性能來提高超級計(jì)算機(jī)性能的方法受到了巨大的挑戰(zhàn)。而GPU在圖形加速領(lǐng)域的出色表現(xiàn)及其強(qiáng)大的并行處理能力，使其逐漸轉(zhuǎn)向通用計(jì)算領(lǐng)域，同時(shí)超級計(jì)算機(jī)也在向異構(gòu)體系發(fā)展。

實(shí)踐證明，異構(gòu)集群比傳統(tǒng)CPU集群具有更強(qiáng)的計(jì)算能力，但異構(gòu)集群下計(jì)算效率較低[1]也是一個(gè)既定事實(shí)，所以如何有效地整合中央處理器(Central Processing Unit,CPU)與圖形處理器(Graphics Processing Unit,GPU)計(jì)算資源顯得格外重要。為了提高集群的計(jì)算效率，許多學(xué)者在異構(gòu)集群基礎(chǔ)上提出了相應(yīng)優(yōu)化方案，主要方向有數(shù)據(jù)通信優(yōu)化、訪存優(yōu)化、任務(wù)劃分與調(diào)度優(yōu)化等。在數(shù)據(jù)通信優(yōu)化方面，呂兆峰等提出一種基于子流劃分的CPU-GPU通信優(yōu)化方法[2-3]，將提交給GPU計(jì)算的數(shù)據(jù)流分成多個(gè)子流，使子流之間的計(jì)算與通信能夠同時(shí)進(jìn)行，從而隱藏了CPU與GPU之間數(shù)據(jù)傳輸?shù)耐ㄐ砰_銷；在訪存優(yōu)化方面，方旭東等提出通過使用共享存儲(chǔ)器及合并訪存等方式[4]來提高訪存帶寬利用率；在任務(wù)劃分方面，成思遠(yuǎn)等提出將任務(wù)劃分為多個(gè)子任務(wù)分別調(diào)度的CPU與GPU上運(yùn)行以整合計(jì)算資源[5]。以上的優(yōu)化方案在一定程度上提高了集群的計(jì)算效率，但也都存在一定的局限性。為此本文提出了基于異構(gòu)集群(Heterogeneous Cluster,HC)的動(dòng)態(tài)任務(wù)劃分與調(diào)度(Dynamic Task Partitioning and Scheduling,DTPS)算法，通過動(dòng)態(tài)調(diào)整CPU與GPU任務(wù)劃分的比例[6]，使CPU與GPU負(fù)載均衡[7]，提高集群的計(jì)算效率。實(shí)驗(yàn)表明，該算法能有效地整合集群計(jì)算資源[8]，大幅度提高計(jì)算集群性能。

1 DTPS算法

DTPS算法是一種基于CPU-GPU異構(gòu)集群的動(dòng)態(tài)任務(wù)劃分與調(diào)度[9-10]算法。將整個(gè)計(jì)算任務(wù)劃分為若干子任務(wù)，并將各子任務(wù)調(diào)度到CPU或GPU執(zhí)行。根據(jù)反饋的CPU與GPU的執(zhí)行時(shí)間[11]，通過動(dòng)態(tài)調(diào)整方式，迭代修正CPU與GPU任務(wù)劃分的比例，直到劃分比例達(dá)到合理的范圍。并用該比例指導(dǎo)其它同類任務(wù)的劃分與調(diào)度。

1.1 任務(wù)劃分模型

任務(wù)劃分是指將一個(gè)計(jì)算任務(wù)的算法分解為若干個(gè)子任務(wù)，各子任務(wù)具有合理的數(shù)據(jù)規(guī)模和計(jì)算規(guī)模，互相之間不存在公共操作部分。所以，問題S的劃分方案如下：

(1)

子任務(wù)Taski的描述定義如下：

(2)

式中：IA表示子任務(wù)內(nèi)部的計(jì)算規(guī)模，即子任務(wù)內(nèi)部所執(zhí)行的基本指令條數(shù)，這里用子任務(wù)內(nèi)部所有操作所需的時(shí)間換算成的標(biāo)準(zhǔn)操作條數(shù)來衡量，定義如下：

(3)

mi表示任務(wù)內(nèi)部第i個(gè)操作的條數(shù)；ni表示第i個(gè)操作換算成標(biāo)準(zhǔn)操作的條數(shù)；DA表示子任務(wù)間的通信量，即子任務(wù)間的數(shù)據(jù)交換，用該子任務(wù)與相鄰子任務(wù)的數(shù)據(jù)交換量來衡量，定義如下：

(4)

式中：DAin表示相鄰子任務(wù)對當(dāng)前任務(wù)的數(shù)據(jù)輸入量；DAout表示當(dāng)前任務(wù)對相鄰子任務(wù)的數(shù)據(jù)輸出量。在此基礎(chǔ)上，對任務(wù)Taski的排序權(quán)重函數(shù)的定義如下：

(5)

1.2 任務(wù)調(diào)度模型

CPU支持超線程、多流水線、復(fù)雜的分支預(yù)測等工作，但在指令級上的并行偏低，邏輯控制較強(qiáng)，比較適合做普通的串行計(jì)算任務(wù)。而GPU本身就是為并行服務(wù)的，大部分芯片面積用在執(zhí)行單元上，使其具有強(qiáng)大的并行計(jì)算能力，比較適合做密集型的計(jì)算任務(wù)[12]。為此，本文在考慮任務(wù)調(diào)度時(shí)，計(jì)算量大而通信量小的子任務(wù)調(diào)度到GPU上運(yùn)行，計(jì)算量小而通信量大的子任務(wù)調(diào)度到GPU運(yùn)行[13]。當(dāng)兩者產(chǎn)生沖突時(shí)，優(yōu)先考慮通信量的影響。比如一個(gè)計(jì)算量和通信量同時(shí)較大的子任務(wù)，將其調(diào)度到CPU執(zhí)行。任務(wù)調(diào)度函數(shù)的定義如下：

(6)

式中:C_Excution()為將計(jì)算任務(wù)調(diào)度到CPU執(zhí)行的函數(shù);G_Excution()為將子任務(wù)調(diào)度到GPU執(zhí)行的函數(shù)。常數(shù)p，q取值：當(dāng)一個(gè)計(jì)算任務(wù)到達(dá)時(shí)，整個(gè)計(jì)算任務(wù)計(jì)算量大小為P，通信量大小Q，假如一個(gè)計(jì)算任務(wù)被分成N個(gè)子任務(wù)，則p取P/2N，q取Q/2n。

1.3 動(dòng)態(tài)比例調(diào)整模型

對于一批計(jì)算任務(wù)，第一個(gè)計(jì)算任務(wù)S0到達(dá)，根據(jù)式(1)將任務(wù)劃分為若干個(gè)子任務(wù)，根據(jù)式(5)可得到CPU核心計(jì)算時(shí)間Tc與GPU核心計(jì)算時(shí)間Tc，及CPU執(zhí)行比例α0、GPU執(zhí)行比例β0。下式給出延遲系數(shù)m的定義：

(7)

根據(jù)式(7)計(jì)算延遲系數(shù)m。以m為基礎(chǔ)，給出動(dòng)態(tài)比例調(diào)整模型中CPU與GPU每次比例調(diào)整的量θ的初始值定義如下：

(8)

式(8)中Turn表示調(diào)整的輪次，Turn=0表示計(jì)算任務(wù)首次進(jìn)行比例劃分調(diào)整。調(diào)整分以下三種情況。

(1) 若-0.1≤m≤0.1，說明延遲在合理范圍內(nèi)，CPU與GPU負(fù)載均衡。下一個(gè)計(jì)算任務(wù)S到達(dá)，根據(jù)式(1)將任務(wù)劃分為若干個(gè)子任務(wù)，根據(jù)式(5)得到各子任務(wù)的排序權(quán)重。對子任務(wù)進(jìn)行排序，權(quán)重越大的子任務(wù)排序越靠前。并直接用α0、β0指導(dǎo)排序后的計(jì)算任務(wù)的劃分，任務(wù)的前一部分調(diào)度到CPU執(zhí)行，任務(wù)的后一部分調(diào)度到GPU執(zhí)行。

(2) 若m<-0.1，說明GPU負(fù)載過多，則需要對CPU與GPU的任務(wù)劃分比例作相應(yīng)調(diào)整,迭代令α0+=θ、β0-=θ、θ=θ/2，根據(jù)新的比例重新計(jì)算延遲系數(shù)m，直到m≥-0.1。若-0.1≤m≤0.1，說明延遲在可接受范圍之內(nèi)，則用此時(shí)的劃分比例來指導(dǎo)下一個(gè)計(jì)算任務(wù)的劃分；若m>0.1，則迭代令α0-=θ、β0+=θ、θ=θ/2，直到m調(diào)整至合適比例。

(3) 若m>0.1，說明CPU負(fù)載過多，則首先令α0-=θ、β0+=θ、θ=θ/2，做類似于(2)的迭代動(dòng)態(tài)調(diào)整。

1.4 基于DTPS算法的任務(wù)執(zhí)行

在上述模型的基礎(chǔ)上，可實(shí)現(xiàn)一批計(jì)算任務(wù)的高效率計(jì)算。具體而言，首先，對于第一個(gè)計(jì)算任務(wù)進(jìn)行任務(wù)劃分；然后，利用子任務(wù)調(diào)度函數(shù)執(zhí)行該計(jì)算任務(wù)，得到合理的任務(wù)劃分比例；最后用該比例指導(dǎo)后續(xù)計(jì)算任務(wù)劃分，若劃分不合理則進(jìn)行相應(yīng)調(diào)整，直至完成一批計(jì)算任務(wù)的計(jì)算。具體流程如圖1所示。

2 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證算法的有效性，本文在CPU和CUDA上設(shè)計(jì)了3組實(shí)驗(yàn)。通過對比，驗(yàn)證本文算法在可以有效地提高集群計(jì)算效率，加速任務(wù)的的計(jì)算。實(shí)驗(yàn)將本文算法與傳統(tǒng)調(diào)用CUBLAS的方法進(jìn)行比較。

2.1 軟硬件環(huán)境

實(shí)驗(yàn)硬件環(huán)境為：1個(gè)計(jì)算節(jié)點(diǎn)，CPU和GPU各1個(gè)，CPU與GPU通過PCI-E總線相連。CPU為雙核Intel Core i5-3337U，主頻是1.8 GHz；GPU為NVIDIA GeForce 820M，擁有96個(gè)流處理器，頻率是775 MHz。實(shí)驗(yàn)軟件環(huán)境為：Intel MKL版本為11.1.1，Cuda ToolKit版本為7.0。

2.2 實(shí)驗(yàn)的實(shí)現(xiàn)

實(shí)驗(yàn)分為3組：第1組為不同維度矩陣通過調(diào)用CPU函數(shù)在CPU上的執(zhí)行情況；第2組為在CUDA架構(gòu)[14]下，不做任何優(yōu)化，不同維度的矩陣在GPU上的執(zhí)行情況；第3組為在CUDA架構(gòu)下，利用DTPS算法思想，對矩陣進(jìn)行劃分與調(diào)度，不同維度矩陣的執(zhí)行情況。通過比較3組實(shí)驗(yàn)結(jié)果，可以體現(xiàn)出DTPS算法的優(yōu)勢。

2.2.1 基于CPU函數(shù)的矩陣乘法

本組實(shí)驗(yàn)通過調(diào)用CPU函數(shù)來實(shí)現(xiàn)不同維度矩陣在CPU上的運(yùn)行，未做相關(guān)優(yōu)化，不同維度矩陣在CPU上完成計(jì)算的執(zhí)行時(shí)間以及執(zhí)行速度如表1所示。

表1 基于CPU函數(shù)矩陣乘法的執(zhí)行情況

顯然，CPU上通過調(diào)用CPU函數(shù)來實(shí)現(xiàn)矩陣乘法的方式，運(yùn)算速度受矩陣維度的影響很大。隨著矩陣維度的增大，CPU執(zhí)行速度逐漸減小，這也驗(yàn)證了CPU比較適合做普通的串行任務(wù)。

2.2.2 基于CUBLAS庫的矩陣乘法

本組實(shí)驗(yàn)在CUDA架構(gòu)下，調(diào)用CUBLAS庫直接進(jìn)行矩陣乘法運(yùn)算，未做優(yōu)化，不同維度矩陣完成計(jì)算的執(zhí)行時(shí)間以及執(zhí)行速度如表2所示。

表2 基于CUBLAS庫矩陣乘法的執(zhí)行情況

實(shí)驗(yàn)結(jié)果表明，在CUDA下，隨著矩陣維度的增大，矩陣執(zhí)行速度逐漸增大，與GPU適合做密集型計(jì)算這一特性相符。與表1相比，對相同維度矩陣，GPU的執(zhí)行速度要比CPU的執(zhí)行速度快，且隨著矩陣維度的增大，優(yōu)勢越來越明顯。

2.2.3 基于DTPS算法的矩陣乘法

本組實(shí)驗(yàn)將待計(jì)算矩陣劃分為若干個(gè)子矩陣，子矩陣大小的不同體現(xiàn)算法中子任務(wù)計(jì)算量IA的不同。根據(jù)式(6)將各個(gè)子任務(wù)分配給CPU，GPU計(jì)算。根據(jù)運(yùn)行結(jié)果CPU執(zhí)行時(shí)間Tc、GPU執(zhí)行時(shí)間Tg和動(dòng)態(tài)比例調(diào)整模型做任務(wù)劃分比例的調(diào)整。不同維度矩陣在CUDA下運(yùn)用動(dòng)態(tài)任務(wù)劃分與調(diào)度算法的執(zhí)行情況如表3所示。

表3 基于DTPS算法的矩陣乘法執(zhí)行情況計(jì)算任務(wù)

由表3可知，DTPS算法能在較少的次數(shù)下得到一個(gè)合適的任務(wù)劃分比例，并且該比例可用于指導(dǎo)余下同類任務(wù)的運(yùn)行。矩陣乘法在不同模式下的性能對比如下圖2所示，通過對比可知，在DTPS算法下，相同維度矩陣的執(zhí)行速度較CPU函數(shù)和Cublas調(diào)用有了很大提高。且隨著矩陣維度的增大，優(yōu)勢逐漸明顯。因此，DTPS算法在整合計(jì)算資源，提高計(jì)算性能上是有效的，通過計(jì)算可得，性能的提升在19%左右。當(dāng)矩陣維度較小時(shí)，由于DTPS算法的優(yōu)勢并不明顯，所以圖2中維度小于1 024的矩陣基于DTPS算法的執(zhí)行情況未予體現(xiàn)。但集群本身就是為大規(guī)模數(shù)據(jù)計(jì)算服務(wù)的，因此DTPS算法仍是有意義的。

圖2 矩陣乘法在不同模式下的性能對比

3 結(jié) 語

隨著高性能計(jì)算領(lǐng)域計(jì)算需求的增大，超級計(jì)算機(jī)逐漸向異構(gòu)體系發(fā)展。本文提出了一種異構(gòu)模式下的任務(wù)劃分與調(diào)度算法，通過動(dòng)態(tài)調(diào)整任務(wù)劃分比例，用前一個(gè)作業(yè)的結(jié)果來指導(dǎo)下一個(gè)作業(yè)的任務(wù)劃分。通過實(shí)驗(yàn)可以看出，該劃分模式下，當(dāng)同類作業(yè)相繼到達(dá)時(shí)，只要做較少的調(diào)整就能得到一個(gè)合理的劃分比例。所以，該算法在異構(gòu)體系優(yōu)化中具有一定的指導(dǎo)意義。此外，為了增強(qiáng)集群的計(jì)算能力，除了引入GPU外，近年來也有在集群體系中加入MIC卡的結(jié)構(gòu)[15-16]。在后期工作中，筆者會(huì)對加入MIC卡做相關(guān)研究，實(shí)現(xiàn)對CPU-MIC卡異構(gòu)集群的優(yōu)化。

[1] 蔡鎮(zhèn)河, 張 旭, 欒江霞. CPU+GPU異構(gòu)模式下并行計(jì)算效率研究[J]. 計(jì)算機(jī)與現(xiàn)代化, 2012(5):185-188.

[2] 呂兆峰. 基于CPU/GPU異構(gòu)集群的矩量法研究[D]. 西安電子科技大學(xué), 2014:46-47.

[3] Dichev K, Lastovetsky A, Jeannot E,etal. 6. Optimization of Collective Communication for Heterogeneous HPC Platforms[J]. High-Performance Computing on Complex Environments, 2014(11):12-15.

[4] 方旭東. 面向大規(guī)模科學(xué)計(jì)算的CPU-GPU異構(gòu)并行技術(shù)研究[D]. 長沙:國防科學(xué)技術(shù)大學(xué), 2009.

[5] 成思遠(yuǎn). 異構(gòu)(CPU-GPU)計(jì)算機(jī)系統(tǒng)性能評測與優(yōu)化技術(shù)研究[D]. 長沙:國防科學(xué)技術(shù)大學(xué), 2011.

[7] 彭江泉, 鐘 誠. CPU/GPU系統(tǒng)負(fù)載均衡的可分負(fù)載調(diào)度[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2013, 34(11):3916-3923.

[8] 霍洪鵬, 胡新明, 盛沖沖,等. 面向節(jié)點(diǎn)異構(gòu)GPU集群的能量有效調(diào)度方案[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2013, 30(3):283-286.

[9] 馮煥霞, 劉 莉, 李正淳. 異構(gòu)集群下的動(dòng)態(tài)任務(wù)調(diào)度策略[J]. 軟件導(dǎo)刊, 2014(6):23-26.

[10] 王 超, 陳香蘭, 周學(xué)海,等. 異構(gòu)多核平臺上基于任務(wù)劃分和調(diào)度的性能評估方法[J]. 中國科技大學(xué)學(xué)報(bào), 2012, 29(2):257-263.

[11] 陳 偉, 張玉芳, 熊忠陽. 動(dòng)態(tài)反饋的異構(gòu)集群負(fù)載均衡算法的實(shí)現(xiàn)[J]. 重慶大學(xué)學(xué)報(bào), 2010, 32(2):73-78.

[12] 朱正東. 面向CPU-GPU架構(gòu)的源到源自動(dòng)映射方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015(11):41-47.

[13] 李靜梅, 金勝男. 基于異構(gòu)多核處理器的靜態(tài)任務(wù)調(diào)度研究[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2013, 34(1):178-184.

[14] Blattner T, Yang S. Performance study on CUDA GPUs for parallelizing the local ensemble transformed Kalman filter algorithm[J]. Concurrency & Computation Practice & Experience, 2012, 24(2):167-177.

[15] Tao G, Yutong L, Guang S. Using MIC to Accelerate a Typical Data-Intensive Application: The Breadth-first Search[C]// 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd ForumIEEE Computer Society, 2013:1117-1125.

[16] Potluri S, Bureddy D, Hamidouche K,etal. MVAPICH-PRISM: A proxy-based communication framework using InfiniBand and SCIF for Intel MIC clusters[C]// 2013 SC-International Conference for High Performance Computing, Networking, Storage and AnalysisIEEE Computer Society, 2013:1-11.

DTPS Algorithm Based Optimization Strategy of Heterogeneous Cluster

LIXue-jian,CHENHao,ZHUKai

(School of Computer Science and Technology, Anhui University, Hefei 230601, China)

With the development of high-performance computers, the heterogeneous cluster based on CPU and GPU gradually attract people’s attention. It is more cheaper and environment friendly compared to traditional supercomputing architectures. And it has faster computing speed in the mean time. However, limited by the low computing efficiency, it’s difficult for heterogeneous cluster to develop better. The DTPS algorithm proposed in the paper can adjust the proportion CPU-executed task and GPU-executed task dynamically. By the method, the computing of supercom-putting architecture is raised greately. Finally, the DTPS algorithm is verified by experiment.

heterogeneous cluster; task partitioning; task scheduling; dynamic adjustment

2015-08-26

李薛劍(1981-)，男，安徽合肥人，講師，主要研究方向?yàn)槌绦蚍治龊万?yàn)證、高性能計(jì)算。E-mail:lxj@ahu.edu.cn

TP 338.6

A

1006-7167(2016)03-0126-04