利用GPU進(jìn)行高性能數(shù)據(jù)并行計(jì)算

高性能計(jì)算

數(shù)據(jù)庫(kù)技術(shù)的成熟，數(shù)據(jù)挖掘應(yīng)用，生物基因技術(shù)的發(fā)展，歷史數(shù)據(jù)的幾何級(jí)膨脹等要求高性能計(jì)算(High Performance Computing，HPC)。雖然通過(guò)創(chuàng)建分布式系統(tǒng)可以解決部分大型計(jì)算的問(wèn)題，但是分布式系統(tǒng)有通信開(kāi)銷(xiāo)大，故障率高；數(shù)據(jù)的存取結(jié)構(gòu)復(fù)雜，開(kāi)銷(xiāo)大；數(shù)據(jù)的安全性和保密性較難控制等弱點(diǎn)。隨著計(jì)算機(jī)處理器，特別是GPU (Graphical Processing Unit)計(jì)算能力的飛速提高，高性能計(jì)算逐步進(jìn)入桌面（低端）領(lǐng)域，這就要求我們探討并行編程模型與并行編程等軟件技術(shù)。

GPU 強(qiáng)大計(jì)算能力

早期的3D游戲，顯卡只是為屏幕上顯示像素提供一個(gè)緩存，所有的圖形處理都是由CPU單獨(dú)完成。圖形渲染適合并行處理，擅長(zhǎng)于執(zhí)行串行工作的CPU實(shí)際上難以勝任這項(xiàng)任務(wù)。直到1995年，PC機(jī)領(lǐng)域第一款GPU 3dfx Voodoo出來(lái)以后，游戲的速度、畫(huà)質(zhì)才取得了一個(gè)飛躍。GPU的功能更新很迅速，平均每一年多便有新一代的GPU誕生，運(yùn)算速度也越來(lái)越快。

Intel Core2Due
Woodcrest G80 Chip 運(yùn)算能力比較
24 GFLOPS 520 GFLOPS GPU快21.6倍

為什么GPU跑得快？

GPU具有兩點(diǎn)主要特征：超長(zhǎng)流水線與并行計(jì)算[4]。

如果裝配一臺(tái)汽車(chē)需要10個(gè)時(shí)間單元，將它分成10個(gè)流水線階段，每個(gè)階段分配一個(gè)時(shí)間單元，那么一條裝配線每一個(gè)時(shí)間單元就可以生產(chǎn)一輛汽車(chē)。顯然流水線模式的生產(chǎn)在理想狀況下要比串行方式快了十倍。
GPU通過(guò)單指令多數(shù)據(jù)(SIMD)指令類(lèi)型來(lái)支持?jǐn)?shù)據(jù)并行計(jì)算。在單指令多數(shù)據(jù)流的結(jié)構(gòu)中，單一控制部件向每條流水線分派指令，同樣的指令被所有處理部件同時(shí)執(zhí)行。例如NVIDIA 8800GT顯卡中包含有14組多處理器(Multiprocessor)，每組處理器有8個(gè)處理單元(Processor)，但每組多處理器只包含一個(gè)指令單元(Instruction Unit)。

GPU流式編程模型

GPU編程以流式編程模型為基礎(chǔ)，它以允許高效計(jì)算和通信的方式構(gòu)造程序[3]。在流式編程模型中，所有數(shù)據(jù)都表現(xiàn)為流。我們把流定義為具有相同數(shù)據(jù)類(lèi)型的數(shù)據(jù)的有序集。數(shù)據(jù)類(lèi)型可以是簡(jiǎn)單的(整數(shù)或浮點(diǎn)數(shù)流)或復(fù)雜的(點(diǎn)或三角形或變換矩陣流)。流可以是任意長(zhǎng)度，如果流很長(zhǎng)(流中有上百或更多的元素)，那么流上的操作并行度將很高。流上允許的操作包括復(fù)制它們，從它們導(dǎo)出子流，用一個(gè)單獨(dú)的索引流索引入它們，以及用核在它們上執(zhí)行計(jì)算。GPU程序稱(chēng)為核，核操作整個(gè)流，獲取一個(gè)或多個(gè)流作為輸入并產(chǎn)生一個(gè)或多個(gè)流作為輸出。核的特征是它操作多個(gè)流上的所有元素而不是獨(dú)立的元素。

CPU程序以異步的方式調(diào)用GPU核程序。GPU作為CPU的協(xié)處理器(Coprocessor)提供服務(wù)。


實(shí)驗(yàn)

我們的實(shí)驗(yàn)基于CUDA的SDK以及C語(yǔ)言編譯器在8800GT顯卡上開(kāi)發(fā)運(yùn)行的。CPU版程序?yàn)殡p線程，用VC++6.0開(kāi)發(fā)，運(yùn)行于Intel Core2Duo主頻為2.6G赫茲。實(shí)驗(yàn)結(jié)果中，GPU版程序運(yùn)行時(shí)間包括輸入數(shù)據(jù)流和輸出數(shù)據(jù)流上傳和下載到顯卡的I/O時(shí)間。

1　DES 編解碼

DES算法對(duì)64位數(shù)據(jù)進(jìn)行加密后輸出64位數(shù)據(jù)。DES算法可以用流計(jì)算模型來(lái)實(shí)現(xiàn)，輸入與輸出流的基本數(shù)據(jù)類(lèi)型為64位數(shù)據(jù)。核程序?yàn)镈ES算法。

DES 編碼 CPU 時(shí)間 GPU時(shí)間 GPU版比CPU版快
64 M字節(jié) 11.4秒 1秒 11.4 倍

表2：CPU/GPU DES編碼實(shí)驗(yàn)結(jié)果

2　MD5密碼破解

在我們的程序中，允許用戶輸入一長(zhǎng)度為五的密碼的MD5值，每位密碼變化范圍是A~Za~z[]^_`{}|~，共64種字符。窮舉所有的密碼并用MD5算法得到所有的MD5值，與用戶輸入的MD5值比較，若枚舉的密碼MD5值與用戶輸入匹配，輸出該密碼。
MD5 破解可以用流計(jì)算模型來(lái)實(shí)現(xiàn)，輸入流基本數(shù)據(jù)為長(zhǎng)度為5個(gè)字符的密碼，可以枚舉出來(lái)。所有基于密碼產(chǎn)生的128比特 MD5值可看為中間結(jié)果流。核程序?yàn)镸D5算法。最后，把中間結(jié)果和輸入的MD5值比較的布爾值組成最終結(jié)果流。

MD5 破解   CPU 時(shí)間 GPU時(shí)間 GPU版比CPU版快
窮舉1G種可能 201秒 15.3秒 13.1 倍 #p#page_title#e#

表3：CPU/GPU MD5 破解實(shí)驗(yàn)結(jié)果

3　字符串匹配

本實(shí)驗(yàn)隨機(jī)產(chǎn)生64M字節(jié)的文本和64個(gè)長(zhǎng)度為8的關(guān)鍵字，找出在輸入的文本中出現(xiàn)的關(guān)鍵字。本實(shí)驗(yàn)的程序采用的是Boyer-Moore-Horspool-Sunday（BMHS）字符串匹配算法.

字符串匹配問(wèn)題用流計(jì)算模型來(lái)實(shí)現(xiàn)，輸入流為64M字節(jié)文本。核程序?yàn)榉謩e對(duì)64個(gè)關(guān)鍵字進(jìn)行字符串匹配的算法。把64個(gè)關(guān)鍵字字符串匹配結(jié)果的布爾值組成結(jié)果流。

值得一提的是，對(duì)每個(gè)關(guān)鍵詞的搜索在窗口內(nèi)進(jìn)行，窗口的大小于關(guān)鍵詞的長(zhǎng)度相等，窗口沿著文本向右滑動(dòng)。BMHS算法將窗口內(nèi)文本的最后一個(gè)字符(L)和關(guān)鍵字的最后一個(gè)字符進(jìn)行比較。如果相等，則需要在搜索窗口中從后向前對(duì)文本和關(guān)鍵字進(jìn)行比較，直到完全相等或者在某個(gè)字符處不匹配。然后，都將根據(jù)L在關(guān)鍵字的下一個(gè)出現(xiàn)的位置將 窗口向右移動(dòng)。對(duì)每個(gè)關(guān)鍵詞移動(dòng)的距離，也就是下次讀取字符的位置，是不一樣的。參見(jiàn)圖 NVDIA GeForce 8體系結(jié)構(gòu)，每次從GPU設(shè)備存儲(chǔ)器(Device Memory)讀取數(shù)據(jù)需要耗費(fèi)400~600個(gè)時(shí)鐘周期[1]。本實(shí)驗(yàn)把輸入文本和一兩維圖像(紋理)進(jìn)行綁定，這樣也就利用了紋理緩存(Texture Cache)來(lái)提高設(shè)備存儲(chǔ)器的訪問(wèn)速度，減少大量的I/O時(shí)間。

字符串匹配       CPU 時(shí)間 GPU時(shí)間 GPU版比CPU版快
64 M字節(jié)文本 14.5秒 1.4秒 10 倍

表4：CPU/GPU字符串匹配實(shí)驗(yàn)結(jié)果

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

吞吐量可由輸入數(shù)據(jù)大小比上處理器運(yùn)行時(shí)間。從圖3 CPU/GPU吞吐量實(shí)驗(yàn)結(jié)果表明，GPU在通用計(jì)算方面的性能能夠比CPU快10倍以上。MD5密碼破解程序的I/O最小，DES編碼程序次之，字符串匹配程序I/O最大。相對(duì)于CPU版程序吞吐量，GPU版MD5密碼破解相對(duì)性能最高，DES編碼程序次之，雖然字符串匹配程序相對(duì)性能最低，但GPU版程序也能比CPU版程序快一個(gè)數(shù)量級(jí)。

GPU能取代CPU嗎？

GPU在運(yùn)算能力的遠(yuǎn)遠(yuǎn)超越CPU，GPU是否能取代CPU呢？答案是否定的。GPU具有CPU所沒(méi)有的局限性。GPU只提供單指令多數(shù)據(jù)類(lèi)型處理，適合于數(shù)據(jù)并行計(jì)算。GPU在條件控制能力方面非常弱，若程序使用條件控制語(yǔ)句會(huì)極大影響GPU程序的執(zhí)行效率。當(dāng)然，有部分條件控制語(yǔ)句可以用計(jì)算來(lái)代替，例如，判斷兩個(gè)整數(shù)是否相等可以用兩個(gè)整數(shù)異或后再映射成0和1來(lái)代替。本文中的實(shí)驗(yàn)中，利用了這些技巧來(lái)避免使用條件控制語(yǔ)句。另外現(xiàn)在的GPU與主機(jī)(host)數(shù)據(jù)交換只能通過(guò)總線來(lái)實(shí)現(xiàn)，對(duì)于需要大量I/O的應(yīng)用，通訊就會(huì)成為GPU性能瓶頸。

以通用計(jì)算為目的GPU發(fā)展趨勢(shì)

NVIDIA發(fā)布Tesla通用計(jì)算架構(gòu)方案，Tesla GPU運(yùn)算處理器不是一圖形處理專(zhuān)業(yè)卡，可以看作之前的NVIDIA圖形處理專(zhuān)業(yè)卡的通用計(jì)算版本。

可以看出，以通用計(jì)算為目的GPU發(fā)展趨勢(shì)是GPU和CPU的整合，適合于大量數(shù)據(jù)并行計(jì)算的任務(wù)由GPU來(lái)承擔(dān)，GPU定位為CPU的協(xié)處理器。需要復(fù)雜條件控制的，只能串行處理的任務(wù)由CPU來(lái)承擔(dān)。CPU和GPU互相配合工作。

超越集群-240核/4G的Tesla C1060計(jì)算處理器