【正文】 余元件。在計算涉及只有非常有限的快速內(nèi)存（ GB）的商品GPU（圖形處理器）時，這將成為一個問題。問題是找到一個高效的內(nèi)存矩陣的存儲格式，它也適用于在GPU上快速執(zhí)行稀疏矩陣的向量積，甚至更為明顯在計算電磁學(xué)方面，人們常常處理復(fù)雜的矩陣時。在本文中，我們提出了一種新的高效，快速的內(nèi)存存儲格式，非常適合用于實現(xiàn)稀疏矩陣的時間向量乘法用于由英偉達設(shè)計的CUDA（統(tǒng)一計算設(shè)備架構(gòu)）。我們還通過使用可配置的緩存和并發(fā)內(nèi)核執(zhí)行顯示如何調(diào)整SPMV操作最新的英偉達的費米系列GPU。我們證明了追求效率的新的格式和SPMV操作在來自電介質(zhì)天線問題有限元離散化的一些復(fù)雜的價值稀疏矩陣。新方法不僅顯著降低多余的零填充，但它也允許一個實現(xiàn)SPMV的性能，這等同于至今最好的結(jié)果報告。二、GPUS 程序設(shè)計我們將簡要回顧一下幾個概念是必要的理解追求效率的GPU計算[26，27]。GPU（圖形處理器）有很多處理器稱為內(nèi)核對不同的數(shù)據(jù)并行執(zhí)行的相同的代碼。在CUDA架構(gòu)[28]，GPU的處理器被收集到多處理器。在一個CPU里被稱為內(nèi)核的。在內(nèi)核一個線程是并行化的最小單元。線程將被收集到線程塊，共享內(nèi)存在一臺單一的多重處理器。線程塊將被收集到線性塊的網(wǎng)格，在邏輯上是并行執(zhí)行的一個內(nèi)核執(zhí)行期間。線程可以訪問GPU內(nèi)存幾種：全球記憶體（大，讀寫延遲），共享內(nèi)存（片上，低延時，限每塊16 KB），紋理內(nèi)存（低延遲，只讀），和寄存器（低延遲）。為了獲得高效率的代碼執(zhí)行，重要的是要注意以下規(guī)則：◎保證聯(lián)合訪問全局內(nèi)存◎如果聯(lián)合訪問全局存儲器是不可能的 使用紋理內(nèi)存代替◎盡可能地使用共享內(nèi)存◎用共享內(nèi)存訪問取代全局存儲器訪問（如果可能）◎GPU和CPU之間的傳輸降到最低費米，這是最新一代的CUDA架構(gòu)的代碼名稱[29]，增加了新的功能，可以利用以提高性能。特別是，費米架構(gòu)：◎支持可配置的緩存，可分配的共享內(nèi)存和16 KB，48 KB的L1額外的緩存或48 KB的可分配的共享內(nèi)存和16 kB的L1額外的緩存◎允許并行執(zhí)行的并行執(zhí)行內(nèi)核（最多16個不同的GPU功能）◎執(zhí)行雙精度計算顯著快于前代GPU 壓縮存儲使SPMV更高效如引言中所解釋的矩陣存儲的格式，同時影SPMV操作的性能和使用的內(nèi)存量。影響速度的第二個因素是明智地使用各種功能的CUDA架構(gòu)。在本節(jié)中，我們將討論的幾個矩陣存儲格式，可用于在SPMV產(chǎn)品的功能和GPU計算的背景下展示自己的優(yōu)點和缺點。 壓縮行存儲在一個CRS（壓縮行存儲）格式，一個稀疏矩陣被壓縮成三個矢量：一個非零項的向量，一個非零項的向量的列指數(shù)，在一行中的第一非零項的矢量列索引[17]。這種格式采用的是英特爾MKL（數(shù)學(xué)核心函數(shù)庫），它對于稀疏矩陣矢量運算在多核心的CPU上實施是有效的。盡管GPU實現(xiàn)SPMV基于CRS[21，30]比MKL有著更好的表現(xiàn)，由于缺乏聯(lián)合訪問全局存儲器，它們顯示更壞的吞吐量比基于狀Ellpacklike格式的SPMV。然而，從存儲器的角度來看，這種格式是非常有效的，因為沒有需要零填充。對于雙精度和復(fù)雜的值的矩陣所需的存儲在CRS格式的字節(jié)的數(shù)目是： （1）其中：NNZ為非零項向量的長度，N為數(shù)行。 ELLR為了確保聯(lián)合訪問內(nèi)存，同時執(zhí)行SPMV在一個GPU Ellpack（ELL）格式[21]中提出的。在的ELL格式，壓縮的矩陣的每一行存儲兩個向量中的非零項的矢量和矢量的非零項的列指數(shù)（包括一些額外的零）。此格式允許在GPU上實現(xiàn)更好的性能相對于在CPU上，但是在內(nèi)存方面引入了顯著的冗余，用行零填充的方法來獲得長度最長的非零項行（Nmax）。以ELLR格式為基礎(chǔ)的SPMV產(chǎn)品以一列線程的工作方式在GPU上實現(xiàn)。然而，可以進一步改善SPMV的性能通過增加一個額外的矢量提供了有關(guān)下列內(nèi)容的信息的數(shù)量在每行中的非零點。此修改的格式被稱為ELLR和增強的性能，因為只有非零在計算中被涉及的22]。為了更好地執(zhí)行在一個GPU上行數(shù)是程序塊尺寸的除數(shù)，否則就沒有全局存儲器的聯(lián)合訪問。要滿足這樣的條件只有用零元素添加一些額外的行（）。從以上的描述得知ELLR格式?jīng)]有CRS有效是顯而易見的從存儲器的角度來看。在ELLR格式里，對于雙精度和復(fù)雜的值的矩陣所需存儲字節(jié)的數(shù)量是： （2）其中：——數(shù)最長行中的非零項。 Sliced ELLPACK在ELL格式中為了消除固有的冗余，Monakovetal [23]提出限制矩陣在壓縮之前。在這種被稱為Slicde ELL的格式中，有一個特定的預(yù)處理應(yīng)用，也就是一個稀疏矩陣首先被劃分成由子矩陣（切片）組成的S相鄰行（S=1，...，N），然后切片存儲在ELL格式。其結(jié)果是，額外零的數(shù)量被確定通過切片的行之間最短和最長的距離，而不是由整個矩陣的距離來確定。 ELLRT在SPMV操作在GPU上的浮點運算方面表現(xiàn)出最佳性能是至今以被報道的一種存儲格式先前被提到在[24]。格式被稱為ELLRT，它是一個擴張的ELLR，ELLR需要施加預(yù)處理[24]。在這種預(yù)處理非零元素和它們的列索引被置換和零填充時，每行是16的倍數(shù)。由于此修改，使聚結(jié)和對齊訪問全局內(nèi)存發(fā)生。相比于ELLR，多線程（T = 1，2，4，8，16，32）在單行執(zhí)行時同時執(zhí)行SP運營。無論是在ELL片和ELLRT都有許多線程在單行上執(zhí)行，但有完全不同的尋址方案，從而得到不同的處理的結(jié)果。絕對尋址和線程并行結(jié)合使用的共享內(nèi)存的平均收益率為80％和性能提升分別超過ELLR和ELL片15%。不幸的是，在ELLRT中，也有類似零填充的問題像在ELLR中一樣?？們?nèi)存需要存儲的在ELLRT取決于T（線程數(shù)運行在一個單行），但所有的一切與ELLR相比沒有多少不同。 ELLRT本文提出的格式是利用上述的格式。事實上，它是一個修改過的Sliced ELL和ELLRT格式。至于在Sliced ELLR，矩陣被用S行分為片。此外，在ELLRT中，多線程（T = 1，2，4，8，16，32）在單行執(zhí)行同時執(zhí)行SPMV。對于每個片層排列的非零項和填充零的發(fā)生，是為了實現(xiàn)行是16的倍數(shù)。因此發(fā)生聚結(jié)和對齊訪問的全局內(nèi)存在片里。由于新的格式相結(jié)合的特點，ELLRT和Sliced ELL我們稱之為Sliced ELLRT（圖1）。顯而易見，這種格式可以使其能達到足夠的性能，歸因于聚結(jié)訪問全局內(nèi)存，多線程工作在一個單行上，和使用共享內(nèi)存在執(zhí)行中。在同一時間，由于矩陣切割成片，這種格式的顯著降低存儲所需的內(nèi)存量。圖1 稀疏矩陣分成片（S=4），和每個片用ELLRT方案來存儲。四、性能測試本節(jié)介紹了的SPMV操作在一個使用CRS矩陣存儲格式的CPU上和一個使用第3節(jié)中所描述的各種格式的GPU上的性能比較。操作系統(tǒng)是Windows 7 64位和測試平臺：GPU NVIDIA的GTX480（480個內(nèi)核，CUDA ）CPUXeon 5680（6芯）。為了獲得一個公平的比較，所有GPU實現(xiàn)將于CUP計算涉及優(yōu)化的英特爾174。MKL函數(shù)（英特爾（R），）。最好的結(jié)果，就是SPMV執(zhí)行在CPU上獲得CRS格式[31]用于RCM（反向 Cuthill McKee）的矩陣排序[17]，六個核心啟用和超線程禁用（英特爾建議禁用超線程在使用MKL時，當(dāng)這種特殊的計算類型的庫的螺紋部行使用了大部分可用資源高效率執(zhí)，并執(zhí)行相同的操作在每個線程[32]）。另一方面，在GPU上，我們在每一個矩陣改變行從最短到最長，這不僅保證平衡的線程塊，而且也最大限度地減少ELLRT片格式的每個片冗余的非零元素的數(shù)目。我們的測試的問題是一個介質(zhì)諧振器天線（DRA），這是用SMA連接器[33]連接矩形空腔諧振器的。測試問題是離散的通用過PML（完全匹配層）的有限元方法和三階的向量元素。因此，我們獲得了復(fù)雜的稀疏矩陣A，其有著146517行和超過21M非零項。該矩陣進一步分九個子矩陣，每個子矩陣相對應(yīng)的向量元素的順序用于評估內(nèi)積，同時裝配FEM矩陣。這導(dǎo)致在以下的方式布置在測試矩陣： 結(jié)果和意見測試問題產(chǎn)生10個不同大小和非零元素的復(fù)雜價值矩陣。這些矩陣的細節(jié)已經(jīng)在表1給出。表1的最后一欄顯示出的是存儲非零元素所需的內(nèi)存量。正如在第3個額外的空間是必要的在使用各種存儲方案的SPMV計算中。表1 測試問題的說明表2 比較在雙精度里面儲存不同格式所需的內(nèi)存（MB）。A——基本矩陣，A0022——表1的九個矩陣。所需的內(nèi)存用于存儲整個復(fù)雜的矩陣A和所有的成分矩陣A0022在表2。很明顯，相比到ELLRT（ELLR也一樣）方案，新的ELLRT片格式的明顯減少（大約下降三分之一）矩陣存儲所需的內(nèi)存量，它是幾乎與CRS格式一樣有效。假設(shè)以CRS格式的壓縮為參考，ELLRT至少需要350％以上內(nèi)存量。ELLRT片格式的冗余只有8％左右。從內(nèi)存經(jīng)濟性明確地選擇ELLRT片格式。然而，必需要驗證的是，如果它不導(dǎo)致性能下降。為此，我們已經(jīng)測試了使用第3節(jié)中描述的格式的SPMV積的性能在每個子矩陣Aij上，以驗證一ELLRT片格式的為基礎(chǔ)SPMV的有效執(zhí)行情況。單和雙精度的結(jié)果分別示于圖2和3中。相對于一個CPU，其性能下降，或更大的問題，在這兩種情況下（單精度和雙精度）也是一個大問題，在GPU上的性能就越好。圖2，3揭示了ELLR格式，只有一個線程上操作在單行的限制。圖SPMV在復(fù)雜矩陣A0022的單精度浮點運算的性能。 （GTX 480 VS英特爾處理器5680）。圖3 SPMV對于復(fù)雜矩陣的雙精度浮點運算的性能（GTX 480 VS英特爾處理器5680）。當(dāng)每行的非零項的數(shù)目的增長，一個單線程需要較長的時間來完成的計算，所以SPMV的性能下降。ELLRT和ELLRT片格式?jīng)]有遭受這種情況，因為他們允許每行多個線程操作。每行并發(fā)線程數(shù)（T）調(diào)整以適應(yīng)每個矩陣A00A22。我們的測試顯示，達到最佳的性能為T = 2時，每行的矩陣A00，A10，A20，A21，有少于40個非零元素的每行，T = 4的矩陣A11，A22（超過40和不到80個非零元素的每列）中，T= 8矩陣A01，A12，A02（超過80，每行的非零元素）。由于更快的雙精度在費米架構(gòu)上，GPU和CPU之間的速度差于雙方精度和更大的測試問題，它達到6因素（圖4）。圖4 從單精度和雙精度比較GPU（ELLRT片）和CPU（英特爾MKL）的加速。GTX480 VS英特爾處理器5680。正如第2節(jié)中提到的，費米架構(gòu)配備可設(shè)置的高速緩沖儲存器，并允許同時執(zhí)行內(nèi)核。至于緩存內(nèi)存方面，我們發(fā)現(xiàn)，16 KB的共享內(nèi)存，48 KB的額外的L1高速緩，在GPU上效果提升了20%相比于比其他的方式（48 KB的共享內(nèi)存和額外的L1高速緩存16 KB）。 并行內(nèi)核的影響在第2部分中，費米架構(gòu)是能夠執(zhí)行多達16個GPU功能（內(nèi)核）。探討并發(fā)內(nèi)核執(zhí)行的影響，我們用矩陣A進行了三次測試。在本節(jié)中指出我們評估的的SPMV操作執(zhí)行對整個矩陣A，對于并發(fā)內(nèi)核具有了顯著的影響。讓我們回顧一下，矩陣是由所有上一節(jié)中介紹的矩陣為基準（見式（3））。對于CPU執(zhí)行（英特爾MKL，CRS） 當(dāng)6個核心都被使用時。這一結(jié)果將作為評估GPU加速的參考。對于涉及GPU的測試，我們已經(jīng)實施了三種不同的SPMV操作方式：原文說明題名：A MEMORY EFFICIENT AND FAST SPARSE MATRIX VECTOR PRODUCT ON A GPU.作者：A. Dziekonski, A. Lamecki, and M. Mrozowski.來源：WiComm Center of Excellence, Faculty of ElectronicsTelemunications and Informatics (ETI)Gdansk University of Technology (GUT), Gdansk 80233, Poland.