利用GPU進行高性能數據并行計算
高性能計算
數據庫技術的成熟，數據挖掘應用，生物基因技術的發(fā)展，歷史數據的幾何級膨脹等要求高性能計算(High Performance Computing，HPC)。雖然通過創(chuàng)建分布式系統(tǒng)可以解決部分大型計算的問題，但是分布式系統(tǒng)有通信開銷大，故障率高；數據的存取結構復雜，開銷大；數據的安全性和保密性較難控制等弱點。隨著計算機處理器，特別是GPU (Graphical Processing Unit)計算能力的飛速提高，高性能計算逐步進入桌面（低端）領域，這就要求我們探討并行編程模型與并行編程等軟件技術。
GPU 強大計算能力
早期的3D游戲，顯卡只是為屏幕上顯示像素提供一個緩存，所有的圖形處理都是由CPU單獨完成。圖形渲染適合并行處理，擅長于執(zhí)行串行工作的CPU實際上難以勝任這項任務。直到1995年，PC機領域第一款GPU 3dfx Voodoo出來以后，游戲的速度、畫質才取得了一個飛躍。GPU的功能更新很迅速，平均每一年多便有新一代的GPU誕生，運算速度也越來越快。
表1：CPU/GPU計算能力比較
為什么GPU跑得快？
GPU具有兩點主要特征：超長流水線與并行計算[4]。
如果裝配一臺汽車需要10個時間單元，將它分成10個流水線階段，每個階段分配一個時間單元，那么一條裝配線每一個時間單元就可以生產一輛汽車。顯然流水線模式的生產在理想狀況下要比串行方式快了十倍。
GPU通過單指令多數據(SIMD)指令類型來支持數據并行計算。在單指令多數據流的結構中，單一控制部件向每條流水線分派指令，同樣的指令被所有處理部件同時執(zhí)行。例如NVIDIA 8800GT顯卡中包含有14組多處理器(Multiprocessor)，每組處理器有8個處理單元(Processor)，但每組多處理器只包含一個指令單元(Instruction Unit)。
GPU流式編程模型
GPU編程以流式編程模型為基礎，它以允許高效計算和通信的方式構造程序[3]。在流式編程模型中，所有數據都表現為流。我們把流定義為具有相同數據類型的數據的有序集。數據類型可以是簡單的(整數或浮點數流)或復雜的(點或三角形或變換矩陣流)。流可以是任意長度，如果流很長(流中有上百或更多的元素)，那么流上的操作并行度將很高。流上允許的操作包括復制它們，從它們導出子流，用一個單獨的索引流索引入它們，以及用核在它們上執(zhí)行計算。GPU程序稱為核，核操作整個流，獲取一個或多個流作為輸入并產生一個或多個流作為輸出。核的特征是它操作多個流上的所有元素而不是獨立的元素。
CPU程序以異步的方式調用GPU核程序。GPU作為CPU的協(xié)處理器(Coprocessor)提供服務。
實驗
我們的實驗基于CUDA的SDK以及C語言編譯器在8800GT顯卡上開發(fā)運行的。CPU版程序為雙線程，用VC++6.0開發(fā)，運行于Intel Core2Duo主頻為2.6G赫茲。實驗結果中，GPU版程序運行時間包括輸入數據流和輸出數據流上傳和下載到顯卡的I/O時間。
1、DES 編解碼
DES算法對64位數據進行加密后輸出64位數據。DES算法可以用流計算模型來實現，輸入與輸出流的基本數據類型為64位數據。核程序為DES算法。
表2：CPU/GPU DES編碼實驗結果
2、MD5密碼破解
在我們的程序中，允許用戶輸入一長度為五的密碼的MD5值，每位密碼變化范圍是A~Za~z[]^_`{}|~，共64種字符。窮舉所有的密碼并用MD5算法得到所有的MD5值，與用戶輸入的MD5值比較，若枚舉的密碼MD5值與用戶輸入匹配，輸出該密碼。
MD5 破解可以用流計算模型來實現，輸入流基本數據為長度為5個字符的密碼，可以枚舉出來。所有基于密碼產生的128比特 MD5值可看為中間結果流。核程序為MD5算法。最后，把中間結果和輸入的MD5值比較的布爾值組成最終結果流。
表3：CPU/GPU MD5 破解實驗結果
3、字符串匹配
本實驗隨機產生64M字節(jié)的文本和64個長度為8的關鍵字，找出在輸入的文本中出現的關鍵字。本實驗的程序采用的是Boyer-Moore-Horspool-Sunday（BMHS）字符串匹配算法. #p#page_title#e#
字符串匹配問題用流計算模型來實現，輸入流為64M字節(jié)文本。核程序為分別對64個關鍵字進行字符串匹配的算法。把64個關鍵字字符串匹配結果的布爾值組成結果流。
值得一提的是，對每個關鍵詞的搜索在窗口內進行，窗口的大小于關鍵詞的長度相等，窗口沿著文本向右滑動。BMHS算法將窗口內文本的最后一個字符(L)和關鍵字的最后一個字符進行比較。如果相等，則需要在搜索窗口中從后向前對文本和關鍵字進行比較，直到完全相等或者在某個字符處不匹配。然后，都將根據L在關鍵字的下一個出現的位置將 窗口向右移動。對每個關鍵詞移動的距離，也就是下次讀取字符的位置，是不一樣的。參見圖 NVDIA GeForce 8體系結構，每次從GPU設備存儲器(Device Memory)讀取數據需要耗費400~600個時鐘周期[1]。本實驗把輸入文本和一兩維圖像(紋理)進行綁定，這樣也就利用了紋理緩存(Texture Cache)來提高設備存儲器的訪問速度，減少大量的I/O時間。
表4：CPU/GPU字符串匹配實驗結果
4、實驗結果小結
吞吐量可由輸入數據大小比上處理器運行時間。從圖3 CPU/GPU吞吐量實驗結果表明，GPU在通用計算方面的性能能夠比CPU快10倍以上。MD5密碼破解程序的I/O最小，DES編碼程序次之，字符串匹配程序I/O最大。相對于CPU版程序吞吐量，GPU版MD5密碼破解相對性能最高，DES編碼程序次之，雖然字符串匹配程序相對性能最低，但GPU版程序也能比CPU版程序快一個數量級。
GPU能取代CPU嗎？
GPU在運算能力的遠遠超越CPU，GPU是否能取代CPU呢？答案是否定的。GPU具有CPU所沒有的局限性。GPU只提供單指令多數據類型處理，適合于數據并行計算。GPU在條件控制能力方面非常弱，若程序使用條件控制語句會極大影響GPU程序的執(zhí)行效率。當然，有部分條件控制語句可以用計算來代替，例如，判斷兩個整數是否相等可以用兩個整數異或后再映射成0和1來代替。本文中的實驗中，利用了這些技巧來避免使用條件控制語句。另外現在的GPU與主機(host)數據交換只能通過總線來實現，對于需要大量I/O的應用，通訊就會成為GPU性能瓶頸。
以通用計算為目的GPU發(fā)展趨勢
NVIDIA發(fā)布Tesla通用計算架構方案，Tesla GPU運算處理器不是一圖形處理專業(yè)卡，可以看作之前的NVIDIA圖形處理專業(yè)卡的通用計算版本。
可以看出，以通用計算為目的GPU發(fā)展趨勢是GPU和CPU的整合，適合于大量數據并行計算的任務由GPU來承擔，GPU定位為CPU的協(xié)處理器。需要復雜條件控制的，只能串行處理的任務由CPU來承擔。CPU和GPU互相配合工作。
參考文獻：
[ 1 ] NVEDIA。CUDA Programming Guide。
[ 2 ] Kapasi。流計算模型。
[ 3 ] Gonzalo Navarro, Mathieu Raffinot?！度嵝宰址ヅ洹?。
[ 4 ] 沈璐?！禛PU為什么跑得快·》。
