矩陣乘法的gpu實現(xiàn)

《矩陣乘法的gpu實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、矩陣乘法的GPU實現(xiàn)使用圖形硬件來進行通用數(shù)值計算已經(jīng)成為一個主流的討論話題。以利用少量重用輸入數(shù)據(jù)進行高度并行計算為代表的流算法的實現(xiàn)，已經(jīng)廣泛應(yīng)用在GPU領(lǐng)域。其中密度矩陣乘法頻繁的數(shù)據(jù)執(zhí)行模式和高度并行計算的特點，使得矩陣乘法成為GPU高效計算的很好的一個選擇。但令人驚訝的是，如此接近完美的GPU算法執(zhí)行起來效率卻不如目前采用的CPU緩存已知方式。我們發(fā)現(xiàn)導(dǎo)致這個現(xiàn)象的原因是在計算鄰近的高速緩存時，GPU效率大大落后CPU，高速緩存帶寬的限制降低了GPU執(zhí)行計算重要重用數(shù)據(jù)的性能?！　￡P(guān)鍵詞矩陣；乘法；GPU　　TP39A16

2、74-6708（2011）54-0189-01　　1算法介紹　　可編程圖形硬件的出現(xiàn)，使得人們對降低GPU數(shù)值計算的興趣大為提升。結(jié)合高帶寬的內(nèi)存和比傳統(tǒng)CPU更快進行浮點數(shù)計算的硬件，使得圖形處理器更加適合進行高度并行化的數(shù)值計算工作流。算法如果采用流計算結(jié)構(gòu)，通常能夠獲得顯著的性能提高?！　×饔嬎憧梢员幻枋鰹槔蒙倭恐赜脭?shù)據(jù)進行高度并行化和數(shù)字集中計算。然而，許多計算雖然高度并行化和數(shù)字集中，但卻重用了所有的數(shù)據(jù)。我們研究了目前圖形計算架構(gòu)，這種架構(gòu)中每個輸入都作用于多個輸出。針對傳統(tǒng)的CPU，對這些問題進行優(yōu)化，可以有效的擴大

3、內(nèi)存帶寬，提供處理器單元的效率。我們認(rèn)為這種“分塊”內(nèi)存的策略，可以提高運算效率，并且可以有效的在GPU上執(zhí)行；甚至類似的“分塊”策略可以使用在可編程模式和當(dāng)前的圖形架構(gòu)。　　為此，我們特別研究密度矩陣乘法。這種算法提供固定的內(nèi)存訪問，高度的并行化計算，卻只需O（n）復(fù)雜度的數(shù)據(jù)重用，被認(rèn)為是天然的快速GPU實現(xiàn)算法?！　PU架構(gòu)中的緩存已知[1]已經(jīng)被很好的實現(xiàn)，多種GPU算法[2]也已被開發(fā)。Larsen和McAllister最先支持在圖形硬件上進行矩陣的計算。他們認(rèn)識到這種算法同CPU的效率相當(dāng)，但卻受限于8比特的定點計算。

4、我們根據(jù)他們的推斷，研究并認(rèn)為GPU不能提供高帶寬來訪問那些頻繁被讀取的數(shù)據(jù)，從而導(dǎo)致了了算法上的帶寬限制。為了得到更高的性能，就需要一個架構(gòu)上的調(diào)整?！　?矩陣乘法的實現(xiàn)　　我們考慮計算兩個大規(guī)模、高密度的N*N矩陣的乘法：C=A*B。我們先快速的在CPU上建立原型并進行優(yōu)化，再為GPU進行深入的改善。　　1）矩陣算法在CPU上的實現(xiàn)　　　　圖1矩陣相乘在CPU上實現(xiàn)的偽代碼　　不幸的是，雖然算法簡單，但數(shù)據(jù)的位置卻十分復(fù)雜。矩陣B中的元素是通過列的位置進行訪問的，因此它們在內(nèi)存中不是順序存放（通常二維數(shù)組在內(nèi)存中以行為主進行存儲

5、）。當(dāng)j的迭代計算中重用了矩陣A的i行，然而此行的數(shù)據(jù)卻可能已經(jīng)在最內(nèi)部循環(huán)計算結(jié)束后拋出緩存。因此，算法的帶寬受到限制，表現(xiàn)出極低的性能和低下的效率（進行數(shù)據(jù)讀取的時間相比于進行計算的時間）?！　≡诔掷m(xù)的緩存讀取時，P4處理器在一個循環(huán)中可以讀取128位的流式單指令數(shù)據(jù)[3]。原始的三層循環(huán)算法的最大缺點是每次循環(huán)工作集的大小阻止了通過最快的內(nèi)存層次來放大帶寬。標(biāo)準(zhǔn)的解決方法是將輸入分塊成適合處理器緩存大小的子矩陣，將原有的計算分解為針對子矩陣的子運算。此外，將矩陣B按照更適合內(nèi)存讀取的轉(zhuǎn)置陣的格式進行存儲。針對CPU矩陣相乘的高

6、效的緩存已知實現(xiàn)，獲得了更高效的帶寬，進而得到高效的計算。　　2）矩陣算法在GPU上的實現(xiàn)　　一個實現(xiàn)矩陣相乘的簡單方法是：在一個著色通道中計算結(jié)果矩陣，只要著色器過大。我們把這種方法成為單通道NV算法。我們把2*2的矩陣單元存儲在四個紋理結(jié)構(gòu)中[4]。通過這個結(jié)構(gòu)，在一個程序片段中，內(nèi)存中的輸入可以被使用兩次。因此數(shù)據(jù)的第二次讀取就可以認(rèn)為是寄存器的讀取。根據(jù)圖2中的算法，著色器從矩陣A讀取兩行，從矩陣B讀取兩列，用于計算輸出矩陣的4個數(shù)值。變量i和j通過插入紋理變化提供給著色器?！　　　D2矩陣相乘在GPU上實現(xiàn)的偽代碼　　每個

7、著色器計算圖1中的4個內(nèi)部循環(huán)迭代。GPU的紋理緩存用于捕獲2D位置信息，因此無論列和行的數(shù)據(jù)在緩存中都是連續(xù)的。此外，由于著色器并行的處理鄰近的片段，因此將會同時從輸入中讀到相同的行或列的數(shù)據(jù)。實際中，處理太大的矩陣，指令計數(shù)器將會超過架構(gòu)限制，并且需要多個著色通道來完成計算。　　與單個著色通道相比，多通道的算法通過進行額外的幀緩沖器的讀寫，更加的符合緩存計算。我們的實現(xiàn)基于Larsen和McAllister的變種多通道算法[5]。這種算法將矩陣列中4個連續(xù)的數(shù)據(jù)打包到一個紋理內(nèi)，再將其與著色器中一個4*1的矢量計算出一個4*4的

8、矩陣[6]。在這種算法中，矩陣B的數(shù)據(jù)被使用了四次，但矩陣A中的數(shù)據(jù)卻使用了一次。這種算法需要的紋理數(shù)是單通道NV算法的1.5倍。但是因為在渲染過程中，只訪問了輸入中少量的行列數(shù)據(jù)，因此快取命中率將會大大提升。圖3為一個著色器計算一個