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

利用GPU進(jìn)行高性能數(shù)據(jù)并行計(jì)算 2009-10-15 作者: 丁藝明 劉波 來源: 程序員關(guān)鍵字: 高性能計(jì)算GPUCPU 圖形處理芯片GPU通過單指令多數(shù)據(jù)(SIMD)指令類型來支持?jǐn)?shù)據(jù)并行計(jì)算，提供驚人的計(jì)算能力。本文探討基于GPU的并行編程模型與并行編程等軟件技術(shù)。雖然GPU最初專門是為圖形渲染設(shè)計(jì)的，通過我們的DES 編解碼, MD5密碼破解, 字符串匹配等實(shí)驗(yàn)，證明GPU還可以有效地執(zhí)行多種通用的基于整數(shù)的計(jì)算。本文還討論了以通用計(jì)算為目的GPU發(fā)展趨勢(shì)。實(shí)驗(yàn) 我們的實(shí)驗(yàn)基于CUDA的SDK以及C語言編譯器在8800GT顯卡上開發(fā)運(yùn)行的。CPU版程序?yàn)殡p線程，用VC+6.0開發(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ì)算模型來實(shí)現(xiàn)，輸入與輸出流的基本數(shù)據(jù)類型為64位數(shù)據(jù)。核程序?yàn)镈ES算法。 表2：CPU/GPU DES編碼實(shí)驗(yàn)結(jié)果 2、MD5密碼破解 在我們的程序中，允許用戶輸入一長(zhǎng)度為五的密碼的MD5值，每位密碼變化范圍是AZaz_|，共64種字符。窮舉所有的密碼并用MD5算法得到所有的MD5值，與用戶輸入的MD5值比較，若枚舉的密碼MD5值與用戶輸入匹配，輸出該密碼。 MD5 破解可以用流計(jì)算模型來實(shí)現(xiàn)，輸入流基本數(shù)據(jù)為長(zhǎng)度為5個(gè)字符的密碼，可以枚舉出來。所有基于密碼產(chǎn)生的128比特 MD5值可看為中間結(jié)果流。核程序?yàn)镸D5算法。最后，把中間結(jié)果和輸入的MD5值比較的布爾值組成最終結(jié)果流。 表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）字符串匹配算法. 字符串匹配問題用流計(jì)算模型來實(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)的距離，也就是下次讀取字符的位置，是不一樣的。參見圖 NVDIA GeForce 8體系結(jié)構(gòu)，每次從GPU設(shè)備存儲(chǔ)器(Device Memory)讀取數(shù)據(jù)需要耗費(fèi)400600個(gè)時(shí)鐘周期1。本實(shí)驗(yàn)把輸入文本和一兩維圖像(紋理)進(jìn)行綁定，這樣也就利用了紋理緩存(Texture Cache)來提高設(shè)備存儲(chǔ)器的訪問速度，減少大量的I/O時(shí)間。 表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所沒有的局限性。GPU只提供單指令多數(shù)據(jù)類型處理，適合于數(shù)據(jù)并行計(jì)算。GPU在條件控制能力方面非常弱，若程序使用條件控制語句會(huì)極大影響GPU程序的執(zhí)行效率。當(dāng)然，有部分條件控制語句可以用計(jì)算來代替，例如，判斷兩個(gè)整數(shù)是否相等可以用兩個(gè)整數(shù)異或后再映射成0和1來代替。本文中的實(shí)驗(yàn)中，利用了這些技巧來避免使用條件控制語句。另外現(xiàn)在的GPU與主機(jī)(host)數(shù)據(jù)交換只能通過總線來實(shí)現(xiàn)，對(duì)于需要大量I/O的應(yīng)用，通訊就會(huì)成為GPU性能瓶頸。 以通用計(jì)算為目的GPU發(fā)展趨勢(shì) NVIDIA發(fā)布Tesla通用計(jì)算架構(gòu)方案，Tesla GPU運(yùn)算處理器不是一圖形處理專業(yè)卡，可以看作之前的NVIDIA圖形處理專業(yè)卡的通用計(jì)算版本。 可以看出，以通用計(jì)算為目的GPU發(fā)展趨勢(shì)是GPU和CPU的整合，適合于大量數(shù)據(jù)并行計(jì)算的任務(wù)由GPU來承擔(dān)，GPU定位為CPU的協(xié)處理器。需要復(fù)雜條件控制的，只能串行處理的任務(wù)由CPU來承擔(dān)。CPU和GPU互相配合工作。 參考文獻(xiàn)： 1 NVED