姜春雷，張樹清(.中國(guó)科學(xué)院東北地理與農(nóng)業(yè)生態(tài)研究所，吉林長(zhǎng)春3002；2.中國(guó)科學(xué)院大學(xué)，北京00049)

CPU-GPU協(xié)同加速K riging插值的負(fù)載均衡方法*

姜春雷1，2，張樹清1
(1.中國(guó)科學(xué)院東北地理與農(nóng)業(yè)生態(tài)研究所，吉林長(zhǎng)春130102；2.中國(guó)科學(xué)院大學(xué)，北京100049)

Kriging插值算法被廣泛應(yīng)用于地學(xué)各領(lǐng)域，有著極其重要的現(xiàn)實(shí)意義，但在面對(duì)大規(guī)模輸出網(wǎng)格及大量輸入采樣點(diǎn)時(shí)，不可避免地遇到了性能瓶頸。利用OpenCL和OpenMP在異構(gòu)平臺(tái)上實(shí)現(xiàn)了CPU與GPU協(xié)同加速普通Kriging插值。針對(duì)Kriging插值中采樣點(diǎn)的不規(guī)則分布及CPU和GPU由于體系結(jié)構(gòu)差異對(duì)其的不同適應(yīng)性，提出一種基于不同設(shè)備間計(jì)算性能的差異和數(shù)據(jù)分布特點(diǎn)的負(fù)載均衡方法。試驗(yàn)結(jié)果表明，該方法能有效提高普通Kriging插值速度，同時(shí)還能節(jié)約存儲(chǔ)空間和提高訪存效率。

通用計(jì)算圖形處理器；開放運(yùn)算語言；Kriging插值；負(fù)載均衡

Kriging插值算法是一種考慮區(qū)域變量空間變異結(jié)構(gòu)(自相關(guān)結(jié)構(gòu))特點(diǎn)的線性無偏最優(yōu)估計(jì)插值方法［1］，它在地學(xué)的很多領(lǐng)域都有著重要的應(yīng)用。但是，當(dāng)Kriging插值的輸出網(wǎng)格增大及輸入采樣點(diǎn)增多時(shí)，其計(jì)算時(shí)間急劇增加［2］。當(dāng)前，集成Kriging插值算法的主流地理資訊系統(tǒng)(Geographic Information System，GIS)仍以串行計(jì)算為基礎(chǔ)框架，不能充分利用多核處理器的優(yōu)勢(shì)［3］。隨著各種并行技術(shù)的不斷成熟，地理空間柵格數(shù)據(jù)算法的并行化研究成為新的熱點(diǎn)［4］。很多研究者試圖通過不同的并行技術(shù)來加速Kriging插值。目前，針對(duì)Kriging插值的加速方法主要基于的編程模型有消息傳遞接口(Message Passing Interface，MPI)［5］，OpenMP［6］和通用計(jì)算圖形處理器(General Purpose Graphics Processing Units，GPGPU)［7-8］?；谶@些不同編程模型的Kriging插值算法都取得了很好的加速效果，尤其是GPGPU編程模型的加速比更高。然而，GPGPU加速算法僅將CPU作為一個(gè)流程控制端，造成了GPU計(jì)算時(shí)CPU空閑等待，顯然，CPU與GPU共同承擔(dān)計(jì)算任務(wù)的方式是未來協(xié)同并行計(jì)算的發(fā)展方向［9］。

多設(shè)備協(xié)同加速需要解決的核心問題之一是設(shè)備間的負(fù)載均衡問題。目前關(guān)于計(jì)算設(shè)備間負(fù)載均衡的研究主要集中在根據(jù)不同設(shè)備的性能差異分配計(jì)算的靜態(tài)負(fù)載均衡［10-11］以及在計(jì)算過程中根據(jù)不同計(jì)算設(shè)備進(jìn)度分配計(jì)算的動(dòng)態(tài)負(fù)載均衡［12］。夏飛等［13］對(duì)于異構(gòu)設(shè)備(例如CPU與GPU)間的負(fù)載均衡給出了根據(jù)計(jì)算能力分發(fā)計(jì)算任務(wù)的靜態(tài)負(fù)載均衡方法；趙斯思和周成虎［14］對(duì)于單個(gè)GPU上多個(gè)kernel同時(shí)執(zhí)行，提出一種基于動(dòng)態(tài)規(guī)劃的動(dòng)態(tài)負(fù)載均衡方法，有效地加速了算法的執(zhí)行。對(duì)于Kriging插值而言，由于受限于自然環(huán)境、經(jīng)濟(jì)和人力等條件的限制，采樣點(diǎn)通常不規(guī)則，表現(xiàn)為分布不均勻。由于體系結(jié)構(gòu)的差異，對(duì)于數(shù)據(jù)量相同但分布密度不同的數(shù)據(jù)，不同體系結(jié)構(gòu)的硬件通常表現(xiàn)出不同的計(jì)算速度。這表明負(fù)載均衡時(shí)不僅要考慮不同設(shè)備間性能的差異，還應(yīng)考慮數(shù)據(jù)的特征。

本文提出了一種新的綜合考慮設(shè)備計(jì)算性能和數(shù)據(jù)特征的負(fù)載均衡方法(Load Balancing based on Computation Performance and Data Distribution，LBCPDD)，來實(shí)現(xiàn)設(shè)備間高效合理的負(fù)載均衡，以達(dá)到更快加速Kriging插值的目的。

1 背景知識(shí)

1.1 普通K riging

普通Kriging插值公式可以表示為:

a.無偏性條件。

其中，E表示數(shù)學(xué)期望，m是中間變量。

b.最優(yōu)性條件(即估計(jì)值誤差的方差最小)。

依據(jù)拉格朗日乘數(shù)法原理，建立拉格朗日函數(shù):

r是變異函數(shù)，上述方程組可用矩陣表示如下:解上述方程組，求得λi代入普通Kriging插值公式可計(jì)算出待估未知點(diǎn)的值。

1.2 通用計(jì)算圖形處理器

GPGPU將原本只用于圖形處理的硬件用于通用計(jì)算領(lǐng)域，OpenCL和統(tǒng)一計(jì)算設(shè)備架構(gòu)(Compute Unified Device Architecture，CUDA)是實(shí)現(xiàn)這個(gè)理念的兩種主要軟件開發(fā)平臺(tái)，OpenCL由于能夠在不同的硬件平臺(tái)上運(yùn)行，更具應(yīng)用前景。目前，GPGPU已經(jīng)被廣泛地應(yīng)用于各領(lǐng)域的科學(xué)研究，其相關(guān)知識(shí)已經(jīng)被相關(guān)文獻(xiàn)大量描述，本文僅介紹在其他文獻(xiàn)中被較少描述且被應(yīng)用于本研究的相關(guān)內(nèi)容。AMD公司和NVIDIA公司對(duì)同一硬件概念有不同的稱謂，由于本研究基于AMD公司的GPU實(shí)現(xiàn)，因此在以后的描述中以AMD公司的概念為準(zhǔn)。在AMD公司的GPU中，一個(gè)計(jì)算單元(Compute Unit，CU)可以同時(shí)運(yùn)行多個(gè)workgroup，具體硬件運(yùn)行的workgroup數(shù)及workgroup內(nèi)的線程數(shù)由GPU的硬件環(huán)境決定，主要是內(nèi)存數(shù)量，更少的內(nèi)存消耗，可以讓每個(gè)CU容納更多的workgroup和每個(gè)workgroup容納更多線程。workgroup內(nèi)線程被分成若干個(gè)wavefront(等同于NVIDIA硬件中的warp)，它是硬件調(diào)度線程執(zhí)行的最小單位，其內(nèi)部的線程以嚴(yán)格鎖同步方式執(zhí)行。如果wavefront內(nèi)線程存在不同分支，則每個(gè)線程會(huì)因?yàn)殒i同步方式而執(zhí)行全部分支(無計(jì)算任務(wù)線程執(zhí)行空操作)，導(dǎo)致執(zhí)行時(shí)間增加。數(shù)量足夠的wavefront可以保證在一個(gè)wavefront等待內(nèi)存訪問結(jié)果時(shí)，其他的wavefront可以被調(diào)入執(zhí)行單元執(zhí)行(即交叉訪問)，這種方式大大提高了GPU的利用效率。因此wavefront對(duì)程序的執(zhí)行速度有著巨大的影響。OpenCL并未對(duì)開發(fā)者提供wavefront抽象，但是通過對(duì)不同線程處理數(shù)據(jù)的合理安排可以提高GPU的運(yùn)行效率，即提高wavefront數(shù)量以及減少單個(gè)wavefront內(nèi)的線程分支。

2 基于計(jì)算性能與數(shù)據(jù)分布的負(fù)載均衡方法

在Kriging插值過程中，相鄰的未知點(diǎn)通常有相同的鄰近點(diǎn)。由于變異函數(shù)矩陣是基于待估未知點(diǎn)的鄰近點(diǎn)構(gòu)造的，因此相鄰的未知點(diǎn)通常具有相同的變異函數(shù)矩陣。根據(jù)這一特點(diǎn)，在Kriging插值算法中增加一個(gè)步驟用于檢查相鄰未知點(diǎn)間是否具有相同的鄰近點(diǎn):若存在，則只存儲(chǔ)其中一個(gè)未知點(diǎn)的鄰近點(diǎn)，并且僅對(duì)其構(gòu)造變異函數(shù)矩陣和求逆矩陣，即將相同鄰近矩陣合并存儲(chǔ)及計(jì)算，其他的未知點(diǎn)在計(jì)算過程中使用這個(gè)計(jì)算的結(jié)果。

采樣點(diǎn)一般是不規(guī)則(不均勻)分布的，局部Kriging插值在對(duì)每個(gè)未知點(diǎn)進(jìn)行插值時(shí)，需要求出離它最近的若干個(gè)采樣點(diǎn)，在采樣點(diǎn)密度較小的情況下，相鄰未知點(diǎn)具有相同鄰近點(diǎn)的概率更大，如圖1左上角所示，兩個(gè)未知點(diǎn)(*)具有相同的臨近采樣點(diǎn)(·)；而采樣點(diǎn)較密集時(shí)則相反(如圖1右下角所示):兩個(gè)未知點(diǎn)(*)具有不同的采樣點(diǎn)(·)。對(duì)于GPU，較多的具有相同鄰近點(diǎn)的線程使wavefront內(nèi)產(chǎn)生更少的分支；由于合并存儲(chǔ)和計(jì)算，采樣點(diǎn)稀疏區(qū)域的未知點(diǎn)預(yù)測(cè)會(huì)消耗更少的內(nèi)存和計(jì)算；內(nèi)存消耗的減少讓GPU能夠容納更多的線程并發(fā)執(zhí)行以便GPU線程的交叉執(zhí)行減少內(nèi)存延遲，即不同采樣點(diǎn)密度會(huì)影響GPU的性能。因而在負(fù)載均衡過程中不僅需考慮CPU與GPU自身的計(jì)算能力差異，還應(yīng)考慮CPU與GPU對(duì)不同數(shù)據(jù)空間分布特征的適應(yīng)性差異。在算法中，將插值區(qū)域劃分為若干個(gè)網(wǎng)格，統(tǒng)計(jì)每一個(gè)網(wǎng)格里面的采樣點(diǎn)個(gè)數(shù)，包含較多采樣點(diǎn)的網(wǎng)格中的未知點(diǎn)預(yù)測(cè)交給CPU處理，反之，交給GPU處理(如圖2所示，灰色表示密度較大，白色較小)。

圖1 鄰近點(diǎn)查找與采樣點(diǎn)分布的關(guān)系Fig.1 Relation between searching nearest neighbor and the distribution of samples

CPU與GPU之間任務(wù)的分配比例通常依據(jù)設(shè)備浮點(diǎn)計(jì)算能力，然而，考慮到Kriging插值的復(fù)雜性及數(shù)據(jù)傳輸?shù)挠绊?，浮點(diǎn)計(jì)算能力不能體現(xiàn)出CPU與GPU在計(jì)算Kriging插值時(shí)的性能差異，因此，依據(jù)CPU與GPU單獨(dú)計(jì)算Kriging插值時(shí)的時(shí)間初步估計(jì)GPU任務(wù)分配比例:

圖2 CPU與GPU負(fù)載分配Fig.2 Load allocation between CPU and GPU

然后根據(jù)結(jié)果向GPU適當(dāng)傾斜任務(wù)量。上述任務(wù)分配估計(jì)方法體現(xiàn)了CPU和GPU對(duì)本算法的性能差異，因此僅需CPU或GPU單獨(dú)運(yùn)行一次就可以估算出結(jié)果，在之后的計(jì)算中即便針對(duì)不同的數(shù)據(jù)集也不需要再重新估算任務(wù)分配比例。由于CPU端的串行執(zhí)行并不能完全利用CPU的計(jì)算能力，因此式(5)中TimeCPU指的是OpenMP并行方式下的執(zhí)行時(shí)間。

在LBCPDD算法的實(shí)現(xiàn)中，CPU端以O(shè)penMP方式并行。為了對(duì)提出的GPU算法的性能進(jìn)行比較，實(shí)現(xiàn)了同樣采用局部插值的Shi和Ye描述的Kriging算法［8］。

3 試驗(yàn)與分析

采用的GPU為華碩R9 280，顯示核心為AMD Tahiti XTL次世代圖形核心(Graphics Core Next，GCN)架構(gòu)，擁有3G GDDR5顯存，流處理器數(shù)量為1792個(gè)；CPU為AMD FX-8150主頻為3.6GHz，8核心，8線程；操作系統(tǒng)為Win7 64位。實(shí)驗(yàn)數(shù)據(jù)為從美國(guó)國(guó)家海洋和大氣局(National Oceanic and Atmospheric Administration，NOAA)下載的全球降雨數(shù)據(jù)，為了保證魯棒性，根據(jù)實(shí)驗(yàn)所需采樣點(diǎn)數(shù)據(jù)集的大小，隨機(jī)選擇相應(yīng)數(shù)量的點(diǎn)作為采樣點(diǎn)。所有的實(shí)驗(yàn)中插值的輸出網(wǎng)格大小均為1280×800個(gè)像素。

試驗(yàn)1：CPU性能。為了測(cè)試算法在不同數(shù)據(jù)量下的表現(xiàn)，選取了5組數(shù)據(jù)集進(jìn)行測(cè)試，數(shù)據(jù)量每次增加1000個(gè)采樣點(diǎn)；OpenMP分別選擇2核、4核和8核進(jìn)行測(cè)試(在表1中表示為OMP2，OMP4和OMP8)。算法執(zhí)行時(shí)間見表1:隨著核數(shù)的增加，運(yùn)行時(shí)間持續(xù)減少；隨著數(shù)據(jù)量增加，不同算法的執(zhí)行時(shí)間都有所增加。圖3給出了OpenMP在不同線程(核心)下的加速比，從圖3可以看出隨著線程數(shù)的增加，OpenMP的加速比也隨之增加，最高達(dá)到了3.9倍左右；不同線程的OpenMP方法加速比對(duì)數(shù)據(jù)集大小不敏感，只是數(shù)據(jù)量比較大時(shí)有些輕微波動(dòng)。

表1 串行與OpenMP運(yùn)行時(shí)間對(duì)比Tab.1 Time comparison of sequential code and OpenMP ms

圖3 OpenMP加速比比較Fig.3 Comparison of speed-up of OpenMP

試驗(yàn)2：GPU性能。表2給出了GPU并行的運(yùn)行時(shí)間及加速比。GPU1并行程序依據(jù)Shi和Ye描述的方法實(shí)現(xiàn)［8］，GPU2是改進(jìn)后的GPU算法，增加了檢查相鄰未知點(diǎn)間是否具有相同的鄰近點(diǎn)的步驟。從表2可以看出:GPU算法在不同的數(shù)據(jù)集下都表現(xiàn)出很好的加速效果，GPU2最高達(dá)到21.53倍；GPU2由于對(duì)Kriging插值過程中各未知點(diǎn)的鄰近點(diǎn)進(jìn)行了比較，對(duì)擁有相同鄰近點(diǎn)的未知點(diǎn)，只計(jì)算其中的一個(gè)未知點(diǎn)的變異函數(shù)矩陣和逆矩陣，因此GPU2的加速比明顯高于GPU1的加速比；同OpenMP算法類似，GPU算法的運(yùn)行時(shí)間隨數(shù)據(jù)集的大小增加而增加，但其加速比同數(shù)據(jù)集的大小無關(guān)，波動(dòng)不大。

試驗(yàn)3：CPU-GPU性能。表3給出了通過LBCPDD進(jìn)行負(fù)載均衡后的CPU-GPU協(xié)同執(zhí)行時(shí)間。表中，OpenMP表示CPU端并行方式，采用8核并行，任務(wù)量占1/8；GPU2L表示GPU端使用表2中GPU2算法且通過LBCPDD方法負(fù)載均衡分配數(shù)據(jù)，任務(wù)量占7/8。由于GPU并行與OpenMP并行同時(shí)執(zhí)行，因此算法的執(zhí)行時(shí)間取決于較長(zhǎng)的時(shí)間(負(fù)載分配時(shí)間小于3ms，未列入統(tǒng)計(jì))。表3中性能提升指總時(shí)間相對(duì)GPU單獨(dú)執(zhí)行時(shí)間(表2中GPU2)的性能提升((GPU2-總時(shí)間)/GPU2)。從表3中可以看出，CPU-GPU的運(yùn)算總時(shí)間比GPU單獨(dú)運(yùn)算時(shí)在不同的數(shù)據(jù)集下都有提高，最高達(dá)到了29.95%。CPU-GPU算法減少的時(shí)間一部分來自于CPU分擔(dān)了部分計(jì)算，另外一部分來自于GPU由于處理數(shù)據(jù)的優(yōu)化而節(jié)約的時(shí)間。

表2 GPU程序運(yùn)行時(shí)間及加速比Tab.2 Time and speed-up of GPU program

表3 引入LBCPDD后CPU-GPU協(xié)同運(yùn)行時(shí)間Tab.3 Run time of CPU-GPU cooperation with LBCPDD

試驗(yàn)4：LBCPDD方法對(duì)性能的影響。表4給出了OpenMP及GPU并行在應(yīng)用LBCPDD前后完成各自分配任務(wù)量的計(jì)算時(shí)間及性能變化。標(biāo)準(zhǔn)方法指在分配任務(wù)時(shí)根據(jù)插值點(diǎn)在二維平面上的坐標(biāo)順序?qū)⑶?/8分配給GPU，剩余部分分配給CPU。表中GPU2S和GPU2L分別表示經(jīng)過標(biāo)準(zhǔn)方法和LBCPDD方法進(jìn)行任務(wù)分配后的GPU端執(zhí)行，任務(wù)量為7/8；OpenMP1和OpenMP2分別表示經(jīng)過標(biāo)準(zhǔn)方法和LBCPDD方法進(jìn)行任務(wù)分配后的CPU端執(zhí)行，任務(wù)量為1/8；GPU2L性能提升指GPU2L相對(duì)于GPU2S的性能提升((GPU2S-GPU2L)/GPU2S)；OpenMP2性能提升指OpenMP2相對(duì)OpenMP1的性能提升((OpenMP1-OpenMP2)/OpenMP1)。從表4中可以看出，LBCPDD方法有效減少了GPU的計(jì)算時(shí)間，性能最多提高50.43%，而對(duì)OpenMP方法的性能影響相對(duì)較小。這主要是由于將適合GPU計(jì)算的數(shù)據(jù)分給了GPU，而將其余數(shù)據(jù)分給了對(duì)數(shù)據(jù)分布并不敏感的CPU。由于OpenMP運(yùn)行時(shí)，各線程間以無序方式異步運(yùn)行，這樣做有利于OpenMP線程間動(dòng)態(tài)負(fù)載均衡，但如果各線程間需要同步，則會(huì)極大地影響其速度，故OpenMP程序無法從減少冗余矩陣和數(shù)據(jù)重組中獲得好處。

表4 LBCPDD對(duì)CPU和GPU的影響Tab.4 Impact of LBCPDD on GPU and CPU

在CPU與GPU協(xié)同計(jì)算中，對(duì)采樣點(diǎn)的密度進(jìn)行了分析，將采樣點(diǎn)分布密度較低的區(qū)域分給了GPU。這樣做有很多好處:更多的冗余矩陣分布在一個(gè)workgroup中，將有利于單個(gè)wavefront內(nèi)的線程具有更少甚至沒有分支。大量的冗余矩陣分布在一個(gè)workgroup內(nèi)會(huì)使后續(xù)計(jì)算讀取同一塊內(nèi)存區(qū)域，從而可以基于GPU內(nèi)存存取機(jī)制(廣播)減少延遲。CPU與GPU之間解決內(nèi)存延遲使用兩種不同策略，CPU用了大量的芯片空間構(gòu)造片內(nèi)緩存，主要通過多級(jí)緩存來減少內(nèi)存訪問的延遲；而GPU芯片大量空間被用來構(gòu)造計(jì)算單元，通過大量線程的交叉訪問來隱藏內(nèi)存延遲，更多的冗余矩陣導(dǎo)致更少的內(nèi)存消耗，從而可以讓更多的線程調(diào)度到CU中執(zhí)行，為線程的交叉訪問提供條件。在冗余矩陣合并存儲(chǔ)時(shí)，通過一個(gè)全局變量記錄每個(gè)線程對(duì)應(yīng)的矩陣編號(hào)，由于OpenCL不支持全局同步，因此，通過對(duì)全局變量的原子操作來完成編號(hào)的記錄，原子操作具有排他性，會(huì)嚴(yán)重影響性能，冗余矩陣減少后，原子操作減少。一個(gè)workgroup內(nèi)冗余矩陣增多，意味著線程計(jì)算時(shí)的內(nèi)存消耗減少(大量線程空操作)，這樣會(huì)減少變量溢出到全局存儲(chǔ)器中，全局存儲(chǔ)器的存儲(chǔ)周期約500個(gè)時(shí)鐘周期，由于等待時(shí)間還可能翻倍，而寄存器存儲(chǔ)周期只有1個(gè)時(shí)鐘周期，馬安國(guó)等［15］在通過預(yù)取對(duì)GPU程序進(jìn)行優(yōu)化時(shí)，性能影響最高達(dá)38%?；谝陨显?，數(shù)據(jù)重分配后GPU計(jì)算的時(shí)間明顯減少。從表4可以看到，隨著采樣點(diǎn)數(shù)據(jù)的增多，采樣點(diǎn)的密度增加，導(dǎo)致冗余矩陣減少，這將導(dǎo)致性能改善降低，表4中數(shù)據(jù)重分配與按序分配時(shí)GPU性能改善隨采樣點(diǎn)數(shù)據(jù)增加而減少就驗(yàn)證了這一點(diǎn)。

4 結(jié)論

Kriging插值算法是一種廣泛應(yīng)用的算法。利用CPU與GPU協(xié)同計(jì)算對(duì)Kriging插值進(jìn)行加速，基于CPU與GPU的計(jì)算性能差異和插值數(shù)據(jù)采樣點(diǎn)的不均勻分布，對(duì)CPU與GPU進(jìn)行負(fù)載均衡。測(cè)試結(jié)果表明，采用了LBCPDD后的CPU-GPU協(xié)同加速方法優(yōu)于單純依賴CPU的OpenMP加速方法、完全GPU的算法和未采用LBCPDD的CPU-GPU協(xié)同加速方法。LBCPDD法對(duì)其他數(shù)據(jù)分布敏感的CPU-GPU協(xié)同加速算法在進(jìn)行負(fù)載均衡時(shí)也同樣具有參考價(jià)值。

References)

［1］Krige D G.A statistical approach to some basic mine valuation problems on the witwatersrand［J］.Journal of the Chemical Metallurgical＆Mining Society of South Africa，1951，94(3):95-111.

［2］De Baar JH S，Dwight R P，Bijl H.Speeding up Kriging through fast estimation of the hyperparameters in the frequency-domain［J］.Computers＆Geosciences，2013，54:99-106.

［3］吳立新，楊宜舟，秦成志，等.面向新型硬件構(gòu)架的新一代GIS基礎(chǔ)并行算法研究［J］.地理與地理信息科學(xué)，2013，29(4):1-8.WU Lixin，YANG Yizhou，QIN Chengzhi，et al.On basic geographic parallel algorithms of new generation GIS for new hardware architectures［J］.Geography and Geo-Information Science，2013，29(4):1-8.(in Chinese)

［4］程果，陳犖，吳秋云，等.一種面向復(fù)雜地理空間柵格數(shù)據(jù)處理算法并行化的任務(wù)調(diào)度方法［J］.國(guó)防科技大學(xué)學(xué)報(bào)，2012，34(6):61-65.CHENG Guo，CHEN Luo，WU Qiuyun，et al.A task schedulingmethod for parallelization of complicated geospatial raster data processing algorithms［J］.Journal of National University of Defense Technology，2012，34(6):61-65.(in Chinese)

［5］Hu H D，Shu H.An improved coarse-grained parallel algorithm for computational acceleration of ordinary Kriging interpolation［J］.Computers＆Geosciences，2015，78: 44-52.

［6］Cheng T P，Li D D，Wang Q.On parallelizing universal Kriging interpolation based on OpenMP［C］//Proceedings of the9th International Symposium on Distributed Computing and Applications to Business，Engineering and Science，Hong Kong:IEEE，2010:36-39.

［7］Cheng T P.Accelerating universal Kriging interpolation algorithm using CUDA-enabled GPU［J］.Computers＆Geosciences，2013，54:178-183.［8］Shi X，Ye F.Kriging interpolation over heterogeneous computer architectures and systems［J］.GIScience＆Remote Sensing，2013，50(2):196-211.

［9］盧風(fēng)順，宋君強(qiáng)，銀福康，等.CPU/GPU協(xié)同并行計(jì)算研

究綜述［J］.計(jì)算機(jī)科學(xué)，2011，38(3):5-9.

LU Fengshun，SONG Junqiang，YIN Fukang，et al.Survey of CPU/GPU synergetic parallel computing［J］.Computer Science，2011，38(3):5-9.(in Chinese)

［10］方留楊，王密，李德仁，等.負(fù)載分配的CPU/GPU高分

辨率衛(wèi)星影像調(diào)制傳遞補(bǔ)償方法［J］.測(cè)繪學(xué)報(bào)，2014，43(6):598-606.FANG Liuyang，WANG Mi，LIDeren，et al.A workloaddistribution based CPU/GPU MTF compensation approach for high resolution satellite images［J］.Acta Geodaetica et Cartographica Sinica，2014，43(6):598-606.(in Chinese)［11］Wang S，Armstrong M P.A theoretical approach to the use of cyberinfrastructure in geographical analysis［J］.International Journal of Geographical Information Science，2009，23(2): 169-193.

［12］Dong B，Li X，Wu QM，et al.A dynamic and adaptive load balancing strategy for parallel file system with large-scale I/O servers［J］.Journal of Parallel and Distributed Computing，2012，72(10):1254-1268.

［13］夏飛，朱強(qiáng)華，金國(guó)慶.基于CPU-GPU混合計(jì)算平臺(tái)的RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)算法并行化研究［J］.國(guó)防科技大學(xué)學(xué)報(bào)，2013，35(6):138-146.XIA Fei，ZHU Qianghua，JIN Guoqing.Accelerating RNA secondary structure prediction applications based on CPUGPU hybrid platforms［J］.Journal of National University of Defense Technology，2013，35(6):138-146.(in Chinese)

［14］趙斯思，周成虎.GPU加速的多邊形疊加分析［J］.地理科學(xué)進(jìn)展，2013，32(1):114-120.ZHAO Sisi，ZHOU Chenghu.Accelerating polygon overlay analysis by GPU［J］.Progress in Geography，2013，32(1): 114-120.(in Chinese)

［15］馬安國(guó)，成玉，唐遇星，等.GPU異構(gòu)系統(tǒng)中的存儲(chǔ)層次和負(fù)載均衡策略研究［J］.國(guó)防科技大學(xué)學(xué)報(bào)，2009，31(5):38-43.MA Anguo，CHENG Yu，TANG Yuxing，et al.Research on memory hierarchy and load balance strategy in heterogeneous system based on GPU［J］.Journal of National University of Defense Technology，2009，31(5):38-43.(in Chinese)

A load balancing method in accelerating K riging algorithm on CPU-GPU heterogeneous p latforms

JIANG Chunlei1，2，ZHANG Shuqing1
(1.Northeast Institute of Geography and Agroecology，Chinese Academy of Sciences，Changchun 130102，China；2.University of Chinese Academy of Sciences，Beijing100049，China)

Kriging interpolation algorithm is of great practical significance and is widely applied to various fields of geoscience.However，Kriging interpolation would inevitably encounter the performance bottleneck when the output grid or input samples increase.Implemented with OpenCL and OpenMP，the ordinary Kriging interpolation was accelerated on heterogeneous platforms:GPU and CPU.By considering the performance difference of CPU and GPU on the densities of samples，a new load balancing method of LBCPDD(Load Balancing based on Computation Performance and Data Distribution)was proposed，in which not only hardware performance but also data distribution characteristics were taken into account.Experiment results show that LBCPDDmethod can effectively enhance the speed of ordinary Kriging，savememory space and improve the efficiency ofmemory access.

general purpose graphics processor units；open computing language；Kriging interpolation；load balancing

F209

A

1001-2486(2015)05-035-05

10.11887/j.cn.201505006

http://journal.nudt.edu.cn

2015-06-24

國(guó)家自然科學(xué)基金資助項(xiàng)目(41271196)；中國(guó)科學(xué)院重點(diǎn)部署資助項(xiàng)目(KZZD-EW-07-02)

姜春雷(1981—)，男，吉林德惠人，博士研究生，E-mail:jiangchunlei@iga.ac.cn；張樹清(通信作者)，男，研究員，博士，博士生導(dǎo)師，E-mail:zhangshuqing@iga.ac.cn