基于DTPS算法的異構集群優化策略

李薛劍, 陳 豪, 朱 凱

(安徽大學 計算機科學與技術學院，安徽 合肥 230601)

?

基于DTPS算法的異構集群優化策略

李薛劍, 陳 豪, 朱 凱

(安徽大學 計算機科學與技術學院，安徽 合肥 230601)

隨著高性能計算機的發展，一種基于CPU-GPU的異構集群逐漸被人們所關注。相比于傳統集群，它更經濟環保，且擁有更高的運算速度。但異構模式下效率較低的短板也限制著異構集群的發展。本文提出的DTPS算法，通過動態調整異構集群下CPU與GPU任務劃分的比例，整合集群計算資源，使集群的計算效率達到相對較高的水平，并通過實驗證明了算法的有效性。

異構集群； 任務劃分； 任務調度； 動態調整

0 引 言

隨著計算需求的增大，超級計算機得到迅速發展。因技術上的瓶頸，傳統的通過提高CPU性能來提高超級計算機性能的方法受到了巨大的挑戰。而GPU在圖形加速領域的出色表現及其強大的并行處理能力，使其逐漸轉向通用計算領域，同時超級計算機也在向異構體系發展。

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

1 DTPS算法

DTPS算法是一種基于CPU-GPU異構集群的動態任務劃分與調度[9-10]算法。將整個計算任務劃分為若干子任務，并將各子任務調度到CPU或GPU執行。根據反饋的CPU與GPU的執行時間[11]，通過動態調整方式，迭代修正CPU與GPU任務劃分的比例，直到劃分比例達到合理的范圍。并用該比例指導其它同類任務的劃分與調度。

1.1 任務劃分模型

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

(1)

子任務Taski的描述定義如下：

(2)

式中：IA表示子任務內部的計算規模，即子任務內部所執行的基本指令條數，這里用子任務內部所有操作所需的時間換算成的標準操作條數來衡量，定義如下：

(3)

mi表示任務內部第i個操作的條數；ni表示第i個操作換算成標準操作的條數；DA表示子任務間的通信量，即子任務間的數據交換，用該子任務與相鄰子任務的數據交換量來衡量，定義如下：

(4)

式中：DAin表示相鄰子任務對當前任務的數據輸入量；DAout表示當前任務對相鄰子任務的數據輸出量。在此基礎上，對任務Taski的排序權重函數的定義如下：

(5)

1.2 任務調度模型

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

(6)

式中:C_Excution()為將計算任務調度到CPU執行的函數;G_Excution()為將子任務調度到GPU執行的函數。常數p，q取值：當一個計算任務到達時，整個計算任務計算量大小為P，通信量大小Q，假如一個計算任務被分成N個子任務，則p取P/2N，q取Q/2n。

1.3 動態比例調整模型

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

(7)

根據式(7)計算延遲系數m。以m為基礎，給出動態比例調整模型中CPU與GPU每次比例調整的量θ的初始值定義如下：

(8)

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

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

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

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

1.4 基于DTPS算法的任務執行

在上述模型的基礎上，可實現一批計算任務的高效率計算。具體而言，首先，對于第一個計算任務進行任務劃分；然后，利用子任務調度函數執行該計算任務，得到合理的任務劃分比例；最后用該比例指導后續計算任務劃分，若劃分不合理則進行相應調整，直至完成一批計算任務的計算。具體流程如圖1所示。

2 實驗結果與分析

為驗證算法的有效性，本文在CPU和CUDA上設計了3組實驗。通過對比，驗證本文算法在可以有效地提高集群計算效率，加速任務的的計算。實驗將本文算法與傳統調用CUBLAS的方法進行比較。

2.1 軟硬件環境

實驗硬件環境為：1個計算節點，CPU和GPU各1個，CPU與GPU通過PCI-E總線相連。CPU為雙核Intel Core i5-3337U，主頻是1.8 GHz；GPU為NVIDIA GeForce 820M，擁有96個流處理器，頻率是775 MHz。實驗軟件環境為：Intel MKL版本為11.1.1，Cuda ToolKit版本為7.0。

2.2 實驗的實現

實驗分為3組：第1組為不同維度矩陣通過調用CPU函數在CPU上的執行情況；第2組為在CUDA架構[14]下，不做任何優化，不同維度的矩陣在GPU上的執行情況；第3組為在CUDA架構下，利用DTPS算法思想，對矩陣進行劃分與調度，不同維度矩陣的執行情況。通過比較3組實驗結果，可以體現出DTPS算法的優勢。

2.2.1 基于CPU函數的矩陣乘法

本組實驗通過調用CPU函數來實現不同維度矩陣在CPU上的運行，未做相關優化，不同維度矩陣在CPU上完成計算的執行時間以及執行速度如表1所示。

表1 基于CPU函數矩陣乘法的執行情況

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

2.2.2 基于CUBLAS庫的矩陣乘法

本組實驗在CUDA架構下，調用CUBLAS庫直接進行矩陣乘法運算，未做優化，不同維度矩陣完成計算的執行時間以及執行速度如表2所示。

表2 基于CUBLAS庫矩陣乘法的執行情況

實驗結果表明，在CUDA下，隨著矩陣維度的增大，矩陣執行速度逐漸增大，與GPU適合做密集型計算這一特性相符。與表1相比，對相同維度矩陣，GPU的執行速度要比CPU的執行速度快，且隨著矩陣維度的增大，優勢越來越明顯。

2.2.3 基于DTPS算法的矩陣乘法

本組實驗將待計算矩陣劃分為若干個子矩陣，子矩陣大小的不同體現算法中子任務計算量IA的不同。根據式(6)將各個子任務分配給CPU，GPU計算。根據運行結果CPU執行時間Tc、GPU執行時間Tg和動態比例調整模型做任務劃分比例的調整。不同維度矩陣在CUDA下運用動態任務劃分與調度算法的執行情況如表3所示。

表3 基于DTPS算法的矩陣乘法執行情況計算任務

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

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

3 結 語

隨著高性能計算領域計算需求的增大，超級計算機逐漸向異構體系發展。本文提出了一種異構模式下的任務劃分與調度算法，通過動態調整任務劃分比例，用前一個作業的結果來指導下一個作業的任務劃分。通過實驗可以看出，該劃分模式下，當同類作業相繼到達時，只要做較少的調整就能得到一個合理的劃分比例。所以，該算法在異構體系優化中具有一定的指導意義。此外，為了增強集群的計算能力，除了引入GPU外，近年來也有在集群體系中加入MIC卡的結構[15-16]。在后期工作中，筆者會對加入MIC卡做相關研究，實現對CPU-MIC卡異構集群的優化。

[1] 蔡鎮河, 張 旭, 欒江霞. CPU+GPU異構模式下并行計算效率研究[J]. 計算機與現代化, 2012(5):185-188.

[2] 呂兆峰. 基于CPU/GPU異構集群的矩量法研究[D]. 西安電子科技大學, 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] 方旭東. 面向大規模科學計算的CPU-GPU異構并行技術研究[D]. 長沙:國防科學技術大學, 2009.

[5] 成思遠. 異構(CPU-GPU)計算機系統性能評測與優化技術研究[D]. 長沙:國防科學技術大學, 2011.

[7] 彭江泉, 鐘 誠. CPU/GPU系統負載均衡的可分負載調度[J]. 計算機工程與設計, 2013, 34(11):3916-3923.

[8] 霍洪鵬, 胡新明, 盛沖沖,等. 面向節點異構GPU集群的能量有效調度方案[J]. 計算機應用與軟件, 2013, 30(3):283-286.

[9] 馮煥霞, 劉 莉, 李正淳. 異構集群下的動態任務調度策略[J]. 軟件導刊, 2014(6):23-26.

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

[11] 陳 偉, 張玉芳, 熊忠陽. 動態反饋的異構集群負載均衡算法的實現[J]. 重慶大學學報, 2010, 32(2):73-78.

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

[13] 李靜梅, 金勝男. 基于異構多核處理器的靜態任務調度研究[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-)，男，安徽合肥人，講師，主要研究方向為程序分析和驗證、高性能計算。E-mail:lxj@ahu.edu.cn

TP 338.6

A

1006-7167(2016)03-0126-04