基于CUDA的直方圖問題并行優(yōu)化

吳志輝，徐小紅，朱同林

（1.華南農(nóng)業(yè)大學(xué)信息與數(shù)學(xué)學(xué)院，廣州　510642；2.華南農(nóng)業(yè)大學(xué)圖像圖形研究中心，廣州　510642）

基于CUDA的直方圖問題并行優(yōu)化

吳志輝1，2，徐小紅2，朱同林1，2

（1.華南農(nóng)業(yè)大學(xué)信息與數(shù)學(xué)學(xué)院，廣州510642；2.華南農(nóng)業(yè)大學(xué)圖像圖形研究中心，廣州510642）

1　研究內(nèi)容

現(xiàn)有使用文件保存的輸入數(shù)據(jù)集N條，其中數(shù)據(jù)為浮點(diǎn)數(shù)，取值范圍為a≤x

直方圖問題是一個(gè)經(jīng)典的問題，要解決這個(gè)問題需要遍歷所有的數(shù)據(jù)集中的數(shù)據(jù)，判斷所在的區(qū)間分布。隨著數(shù)據(jù)規(guī)模的增加，問題的規(guī)模也隨著增大。而數(shù)據(jù)間并沒有關(guān)聯(lián)性，適合使用并行計(jì)算的方法來實(shí)現(xiàn)。因此本文以該問題為切入點(diǎn)，來研究基于CUDA （Compute Unified Device Architecture）即英偉達(dá)公司推出的通用并行計(jì)算架構(gòu)的并行計(jì)算的特點(diǎn)和優(yōu)劣。

2　直方圖問題的串行化方法

串行化方法即使用單線程的方法，數(shù)據(jù)集采用文件的形式，保存一個(gè)擁有n行的浮點(diǎn)數(shù)，然后統(tǒng)計(jì)完結(jié)果直接輸出到命令行中。串行化方法步驟如下：

①通過讀取文件的形式讀取出浮點(diǎn)數(shù)，由于后續(xù)的操作主要是查詢操作，所以使用數(shù)組形式保存即可。建立一個(gè)大小為N的實(shí)數(shù)類型的數(shù)組Inp，并全部初始化為0。然后依次i=0，1，…，N-2，N-1讀取數(shù)據(jù)到Inp［i］。

②保存結(jié)果的投票箱同樣使用數(shù)組，建立一個(gè)大小M的整數(shù)數(shù)組，其中M=b-a，并全部初始化為0。

③使用基于正序的順序遍歷，下標(biāo)從小到大取出數(shù)字對(duì)應(yīng)的浮點(diǎn)數(shù)。判斷浮點(diǎn)數(shù)屬于哪個(gè)投票箱。使用以下的方法來簡化，直接將浮點(diǎn)數(shù)轉(zhuǎn)化為對(duì)應(yīng)的整數(shù)，此時(shí)的整數(shù)剛好是投票箱的下標(biāo)，這樣就避免了重復(fù)比較，提高了效率。

④直接將投票箱的內(nèi)容輸出到命令行，串行程序結(jié)束。

3　基于CPU的并行化方法

根據(jù)串行化的方法步驟，利用分布式內(nèi)存并行系統(tǒng)的特點(diǎn)，不同的進(jìn)程擁有相互不共享的內(nèi)存，因此所有的數(shù)據(jù)的交換都要通過通信來實(shí)現(xiàn)，而通信的時(shí)間消耗非常大，所以要減少數(shù)據(jù)的交換。具體優(yōu)化如下：

首先要確定串行程序那些步驟可以進(jìn)行并行化。串行化程序中，其中時(shí)間消耗最大的就是遍歷數(shù)組所有的浮點(diǎn)數(shù)，統(tǒng)計(jì)范圍的分布。因此并行化該步驟，將數(shù)組根據(jù)進(jìn)程數(shù)N平均分為n份，每個(gè)進(jìn)程即處理N/n個(gè)。

其次確定不同進(jìn)程哪些數(shù)據(jù)需要進(jìn)行數(shù)據(jù)交換。串行程序中主要涉及到的數(shù)據(jù)包括：①輸入浮點(diǎn)數(shù)數(shù)組，大小為N；②投票箱數(shù)組，大小為M。由于數(shù)據(jù)通信是非常大的時(shí)間消耗，為了縮短時(shí)間，浮點(diǎn)數(shù)數(shù)組的數(shù)據(jù)來自數(shù)據(jù)集文件，而一個(gè)進(jìn)程讀取文件與多個(gè)進(jìn)程讀取文件的時(shí)間相當(dāng)，因此采用每個(gè)進(jìn)程均讀取文件的方法來減少數(shù)據(jù)通信。而對(duì)于投票箱數(shù)組，則每個(gè)進(jìn)程建立一個(gè)投票箱副本，然后再利用數(shù)據(jù)通信匯總。

根據(jù)串行化的方法步驟，利用共享式內(nèi)存并行系統(tǒng)的特點(diǎn)，不同的線程共享同一個(gè)內(nèi)存系統(tǒng)，所以數(shù)據(jù)交換方便，但容易出現(xiàn)數(shù)據(jù)出錯(cuò)以及死鎖等問題，所以并行化時(shí)盡量多地防止數(shù)據(jù)出現(xiàn)的錯(cuò)誤。

首先要確定串行化哪些步驟可以并行化，而其他的步驟直接使用串行即可。串行化時(shí)間銷售最大的就是遍歷數(shù)組所有浮點(diǎn)數(shù)，統(tǒng)計(jì)范圍分布了。因此，采用與分布式內(nèi)存并行系統(tǒng)類似的方法。將數(shù)組根據(jù)線程數(shù)n，平均分為n份，每個(gè)線程處理個(gè)N/n。

其次，要確定是否出現(xiàn)死鎖、數(shù)據(jù)錯(cuò)誤等問題。程序涉及到的數(shù)據(jù)包括：①輸入浮點(diǎn)數(shù)數(shù)組，大小為N；②投票箱數(shù)組，大小為M。其中對(duì)于浮點(diǎn)數(shù)數(shù)組，所有的線程均只進(jìn)行讀操作，所以不存在問題。而對(duì)于投票箱數(shù)組，則會(huì)出現(xiàn)多線程同時(shí)寫入的問題，因此解決方案為，首先各線程先建立投票箱副本，然后針對(duì)匯總投票箱時(shí)增加鎖，使得匯總時(shí)只能有一個(gè)線程操作投票箱。這樣就實(shí)現(xiàn)了防止數(shù)據(jù)錯(cuò)誤的問題。

4　基于CUDA的并行優(yōu)化算法

市場對(duì)實(shí)時(shí)、高清晰度的三維圖形具有無法滿足的需求，由于這種需求的推動(dòng)，可編程圖形處理器（GPU）已經(jīng)演化成高并行度、多線程、擁有強(qiáng)大計(jì)算能力和極高存儲(chǔ)器帶寬的多核處理器［1］。

GPU和CPU的浮點(diǎn)計(jì)算能力差異的原因是：GPU是特別為計(jì)算密集、高并行度計(jì)算（如同圖像渲染）設(shè)計(jì)的，因此將更多的晶體管用于數(shù)據(jù)處理而不是數(shù)據(jù)緩存和流控，如圖1所示。

基于這樣的原因，2006年11月，英偉達(dá)推出了CUDA，一種基于新的并行編程模型和指令集架構(gòu)的通用計(jì)算架構(gòu)，CUDA能夠利用英偉達(dá)GPU的并行計(jì)算引擎比CPU更高效地解決許多復(fù)雜計(jì)算任務(wù)。

圖1　CPU與GPU

CUDA核心包含三個(gè)重點(diǎn)抽象：線程組層次、共享存儲(chǔ)器和柵欄同步，這些被作為一個(gè)最小的語言擴(kuò)展集簡單呈現(xiàn)（expose）給程序員。這些抽象提供了細(xì)粒度數(shù)據(jù)并行度和線程并行度，嵌套在粗粒度數(shù)據(jù)并行和任務(wù)并行中。它們引導(dǎo)程序員將問題劃分為可以被多個(gè)塊內(nèi)線程獨(dú)立并行處理的粗粒度子問題，而每個(gè)子問題又被分為可以被一個(gè)塊內(nèi)線程并行協(xié)作處理的更小的片段。這種分解通過在處理子問題的時(shí)候允許線程協(xié)作保持了語言的表達(dá)性，同時(shí)保證了自動(dòng)可擴(kuò)展性。事實(shí)上，每個(gè)塊可被調(diào)度到可用處理器核心的任意一個(gè)上，以任何順序，并行或者串行執(zhí)行，這使得已編譯好的CUDA程序能夠在任意核心的GPU上執(zhí)行。

圖2　系統(tǒng)可擴(kuò)展性

基于CUDA的GPU程序同樣支持類似于在CPU下的并行優(yōu)化方法，完全可以簡單地將原來針對(duì)多核CPU下的共享式內(nèi)存并行系統(tǒng)程序移植到基于CUDA 的GPU程序下。而所不同的就在于GPU下有自己的存儲(chǔ)系統(tǒng)，所以要利用CUDA使用GPU進(jìn)行計(jì)算，要將數(shù)據(jù)傳輸?shù)紾PU上。

首先要確定基于共享內(nèi)存式并行系統(tǒng)有沒有存在基于CUDA的GPU程序下無法實(shí)現(xiàn)的情況。基于共享式內(nèi)存并行系統(tǒng)的程序主要的并行步驟為遍歷數(shù)組的所有數(shù)據(jù)，統(tǒng)計(jì)分布。此步驟只涉及到讀操作，同樣適用于基于CUDA的GPU程序，因此直接移植即可。

其次要確定主機(jī)（即CPU）與GPU之間的數(shù)據(jù)傳輸。主要數(shù)據(jù)包括：①輸入浮點(diǎn)數(shù)數(shù)組，大小為N；②投票箱數(shù)組。其中，浮點(diǎn)數(shù)數(shù)組是并行計(jì)算的主要數(shù)據(jù)來源，因此此數(shù)據(jù)需要從主機(jī)傳輸?shù)紾PU。而投票箱數(shù)組是保存結(jié)果的主要來源，針對(duì)各線程，同樣需要將數(shù)據(jù)從GPU傳輸?shù)街鳈C(jī)中。

最后要根據(jù)GPU的不同，確定可使用GPU線程數(shù)。與CPU針對(duì)超過核心的線程數(shù)并行串行化不同，基于CUDA的GPU程序?qū)Τ^核心數(shù)的線程很敏感，申請(qǐng)超過核心的線程非常容易導(dǎo)致程序出錯(cuò)，因此無法超出核心數(shù)的使用線程。而相比CPU的核心，GPU擁有非常多的核心，例如本文實(shí)驗(yàn)所用的GPU英偉達(dá)GT 540m就有多達(dá)96個(gè)核。

基于CUDA的GPU程序不僅提供了基于多線程的方法，還提供了線程網(wǎng)格的方法。有3個(gè)組件的向量，所以線程可以使用一維、二維、三維索引標(biāo)識(shí)，形成相對(duì)應(yīng)的線程塊。這提供了一種自然的方式來調(diào)用作用在域內(nèi)元素上的計(jì)算，如向量、矩陣、體元（volume）。線程塊被組織成一維、二維或三維的線程網(wǎng)格。所以使用線程網(wǎng)格。通過構(gòu)建線程網(wǎng)格，可以專門針對(duì)CUDA 做GPU的程序并行優(yōu)化，這個(gè)是GPU相比CPU獨(dú)有的。

因此，在申請(qǐng)GPU的線程時(shí)，可以構(gòu)建從一維到二維，乃至最高維的線程網(wǎng)格。對(duì)提供線程的效率也有幫助。由于數(shù)組為二維矩陣，因此采用二維網(wǎng)格優(yōu)化。建立一個(gè)n×n的二維網(wǎng)格線程，將數(shù)組根據(jù)線程數(shù)k= n×n，平均分為k份，每個(gè)線程處理N/k。

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

實(shí)驗(yàn)的平臺(tái)如下:

硬件方面：使用華碩A43SV系列筆記本作為測試平臺(tái)．其配置為：Intel Core i5-2410M CPU＠2.30 GHz（即雙核四線程，主頻2.3GHz），NVIDIA GeForce GT540M CUDA.1GB（即顯存1G，支持CUDA的顯卡），4.00G內(nèi)存。搭載64bits Windows 7操作系統(tǒng)。

軟件方面：使用VS 2008為基本平臺(tái)，基于分布式內(nèi)存使用MPICH軟件；基于共享式內(nèi)存系統(tǒng)使用OpenMP庫作為基礎(chǔ)；基于CUDA的GPU使用CUDA 4.0作為基礎(chǔ)。

實(shí)驗(yàn)的數(shù)據(jù)：

數(shù)據(jù)集的大小取10，000，000，其中數(shù)據(jù)為浮點(diǎn)數(shù)，取值范圍為0≤x＜10。

串行程序使用C++語言進(jìn)行編寫，分別使用Query PerformanceFrequency和 QueryPerformanceCoun-ter這兩個(gè)函數(shù)統(tǒng)計(jì)時(shí)間消耗，單獨(dú)計(jì)算統(tǒng)計(jì)的耗時(shí)，時(shí)間穩(wěn)定在33毫秒左右。

圖3　串行化方法實(shí)驗(yàn)結(jié)果

針對(duì)通用方法的并行化程序，利用VMWare虛擬機(jī)軟件模擬了一個(gè)雙核的平臺(tái)。時(shí)間與前面串行的程序沒有對(duì)比性，因此單獨(dú)在此平臺(tái)下利用串行程序測試了一遍，時(shí)間穩(wěn)定在0.17秒左右。

針對(duì)分布式內(nèi)存并行系統(tǒng)，本文采用了單機(jī)MPICH2軟件來實(shí)現(xiàn)，測試了進(jìn)程數(shù)為1，2，4的時(shí)間消耗。

針對(duì)共享式內(nèi)存并行系統(tǒng)，本文利用OpenMP庫作為現(xiàn)實(shí)的載體，測試了線程數(shù)為1，2，4的時(shí)間消耗。

表1　基于CPU并行化程序?qū)嶒?yàn)結(jié)果

針對(duì)基于CUDA的GPU程序?qū)嶒?yàn)結(jié)果，包括兩個(gè)內(nèi)容：①基于CUDA的通用方法的并行優(yōu)化的結(jié)果；②基于CUDA的線程網(wǎng)格的并行優(yōu)化的結(jié)果。

表2　基于CUDA的并行優(yōu)化實(shí)驗(yàn)結(jié)果

6　結(jié)語

實(shí)驗(yàn)的最終每種方法的最小平均時(shí)間結(jié)果如表3所示:

表3　實(shí)驗(yàn)結(jié)果比較

本文使用將基于CUDA的GPU程序與普通的串行以及傳統(tǒng)的CPU的相關(guān)并行方法做了比較。從實(shí)驗(yàn)的結(jié)果可以看出，在本文舉例的直方圖中，采用GPU來進(jìn)行并行計(jì)算更具有優(yōu)勢。表現(xiàn)在以下:

（1）GPU的基于計(jì)算密集，高并行度計(jì)算設(shè)計(jì)的。采用多核心的流式結(jié)構(gòu)，本身就更適合用于做并行計(jì)算。本文所采用的CPU和GPU，論主頻來說CPU是擁有更快的速度，但是在具體實(shí)驗(yàn)中，GPU利用多核的優(yōu)勢達(dá)到了和CPU差不多的效率。

（2）基于CUDA的GPU程序開發(fā)提供相比針對(duì)CPU的并行更多的功能。例如：本文使用的基于線程網(wǎng)格的優(yōu)化，比使用傳統(tǒng)CPU并行計(jì)算方法提升了效率，減少了時(shí)間的消耗。

因此，在可以預(yù)見的未來，基于GPU的并行計(jì)算會(huì)發(fā)揮重要的作用。而針對(duì)GPU的CUDA架構(gòu)也將大有用處。

［1］盧風(fēng)順，宋君強(qiáng)，銀?？?，張理論.CPU/GPU協(xié)同并行計(jì)算研究綜述［J］.重慶:計(jì)算機(jī)科學(xué)，2011，03:5-9.

Histogram；Serialization；Distributed Memory；Shared Memory；CUDA

Parallel Optimization of Histogram Problem Based on CUDA

WU Zhi-hui1，2，XU Xiao-hong2，ZHU Tong-lin1，2
（1．College of Mathematics and Information，South China Agricultural University，Guangzhou 510642；2．Research Center of Image&Graphics，South China Agricultural University，Guangzhou 510642）

1007-1423（2015）19-0058-05

10.3969/j.issn.1007-1423.2015.19.015

吳志輝（1989-），男，廣東揭陽人，在讀碩士研究生，研究方向?yàn)閿?shù)字圖像處理

朱同林（1963-），男，江西南康人，博士，教授，博士生導(dǎo)師，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)及數(shù)字圖像處理

2015-05-12

2015-06-25

直方圖問題是一個(gè)經(jīng)典的問題，以該問題為切入點(diǎn)，比較基于CUDA的GPU（圖形處理器）程序，與串行和傳統(tǒng)的基于CPU（中央處理器）的并行程序的比較，從而找出基于CUDA的GPU程序的特點(diǎn)與優(yōu)勢。

直方圖；串行化；分布式內(nèi)存；共享內(nèi)存；CUDA

高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金聯(lián)合資助課題（No.20124404110018:2013.1-2015.12）

徐小紅（1975-），女，湖南寧鄉(xiāng)人，博士，講師，研究方向?yàn)樯锝y(tǒng)計(jì)、計(jì)算機(jī)視覺和圖像處理

Histogram program is a classic problem，takes the the problem as starting point，compares the GPU program based on comparison CUDA with the serial and traditions based on the CPU comparison of parallel programs，in order to identify the features and advantages of GPU program based on CUDA.