行壓縮存儲表示下的稀疏矩陣向量乘并行算法

行壓縮存儲表示下的稀疏矩陣向量乘并行算法

事實上，許多問題可以用稀疏矩陣來表達。稀疏矩陣向量乘(Sparsematrix-vectormultiplication,SpMV)運算廣泛地應用于大規(guī)模線性求解系統(tǒng)和求解矩陣特征值等問題,尤其在迭代方法中,SpMV成為影響算法性能的關(guān)鍵步驟。然而,SpMV是典型的存儲器瓶頸類運算,即運算/訪存比很低,運算器嚴重不飽和,難以達到高浮點運算吞吐量。SpMV具有本質(zhì)的并行性,利用現(xiàn)代多處理器平臺研究并行SpMV是提高其性能的可行方向之一?，F(xiàn)今,圖形處理器(GraphicsProcessingUnit,GPU)成為個人計算機的標準配置。傳統(tǒng)上,GPU的主要任務是圖形圖像的繪制和渲染。隨著其可編程接口的開放以及高級繪制語言的普及,GPU以其強大的并行處理能力和極高的存儲器帶寬向通用計算領(lǐng)域擴展。在模式識別、小波變換、計算智能和實時仿真等方面都取得了很好的效果。GPU將成為高性能計算領(lǐng)域極具性價比的一個分支。本文基于NVIDIAGPU的統(tǒng)一計算架構(gòu)CUDA(ComputeUnifiedDeviceArchitecture)的特殊體系結(jié)構(gòu),在線程映射、數(shù)據(jù)復用等方面研究了一系列優(yōu)化方法,從而完成了一種行壓縮存儲(compressedsparserow,CSR)表示下的稀疏矩陣向量乘并行算法。這些優(yōu)化方法包括:(1)利用Warp內(nèi)線程天然同步特性,Half-warp完成結(jié)果向量一個元素的計算;(2)取整讀取數(shù)據(jù),實現(xiàn)合并訪問;(3)輸入向量放入紋理存儲器,數(shù)據(jù)復用;(4)申請分頁鎖定內(nèi)存,加速數(shù)據(jù)傳輸;(5)使用共享存儲器,加速數(shù)據(jù)存取。實驗分析表明,本文的各種手段起到了優(yōu)化的作用。與已有的CUDPP和SpMVlibrary中的CSR-vector算法相比,本文算法獲得了更高的帶寬和浮點運算吞吐量;整體性能比CPU串行執(zhí)行版本快了3倍以上。1gpu性能研究和結(jié)論存儲器訪問(gatherorscatter)是影響SpMV效率的重要方面,而多核架構(gòu)使存儲器瓶頸的問題更加突出?？傮w來說,多核架構(gòu)可以分為通用和專用兩類體系結(jié)構(gòu)。在通用架構(gòu),如AMDDual-core,IntelQuadcore平臺上,主要手段是將局部數(shù)據(jù)放入Cache和寄存器(Register)中,調(diào)度算法的優(yōu)劣影響算法的性能。而本文所基于的專用結(jié)構(gòu)GPU具有多級存儲器體系,需要根據(jù)問題的特征設計不同的優(yōu)化策略,才能發(fā)揮GPU存儲器高帶寬的優(yōu)勢。稀疏矩陣有多種存儲格式,文獻給出了包括本文使用的CSR在內(nèi)的6種存儲方式,結(jié)果顯示對于沒有規(guī)律的數(shù)據(jù),CSR具有一定的優(yōu)勢。我們研究的矩陣整體上是稀疏的,但是可能存在較小的稠密子矩陣,這些密集子塊有助于提高數(shù)據(jù)重用性。文獻對如何抽取一致尺寸的、非一致尺寸的、規(guī)則排列的和非規(guī)則排列的稠密子矩陣都進行了研究,把抽取的結(jié)果整塊放入Register加速。此外,數(shù)據(jù)運行時排序也是提升性能的手段之一,Strout等提出了一個該策略的框架,這需要額外的計算,是否能夠帶來整體性能的提高還有待驗證?？傮w上,GPU架構(gòu)不同于基于高速緩存的通用架構(gòu),具有大規(guī)模并行性,即同一時刻有大量的線程處于活動狀態(tài),通過有效的線程調(diào)度隱藏全局存儲器的高延遲訪問。因此,細粒度線程級并行更適合GPU。Buatois等開發(fā)了基于AMDCTM(closetotheMeta)環(huán)境的稀疏線性求解器,然而AMD的GPU維持傳統(tǒng)的向量處理器架構(gòu)(R,G,B,A),與本文的CUDA標量架構(gòu)有很大的區(qū)別。2稀疏矩陣的存儲通常用m×n數(shù)組來存放m×n的稠密矩陣(m行n列),但這對稀疏矩陣而言效率很低。研究高效的稀疏矩陣存儲方式,不僅可節(jié)省存儲單元,還能夠減少計算時間。目前稀疏矩陣尚無一種通用的最佳數(shù)據(jù)結(jié)構(gòu),不同的數(shù)據(jù)結(jié)構(gòu)適合不同的變換操作和不同的實現(xiàn)方法。表現(xiàn)某些現(xiàn)實問題的矩陣有明顯的特征,如主對角線對稱。但絕大多數(shù)實際問題只具有稀疏的性質(zhì),矩陣本身沒有規(guī)律。CSR是存儲稀疏矩陣的有效方式之一。對于具有q個非零元素的稀疏矩陣,應用CSR格式存儲時,使用3個數(shù)組:一個q×1維的值數(shù)組Data,它按行序分成了m個段;一個q×1維的列下標數(shù)組Indices;一個(m+1)×1維的數(shù)組Ptr,該數(shù)組中的元素指向各段中首元素在稀疏矩陣中的順序號。圖1給出了矩陣在CSR結(jié)構(gòu)下的存儲示例。與稀疏矩陣的其他存儲格式相比,CSR進行了行壓縮,具有最佳的空間效率,同時能夠方便地計算出第i行非零元素的個數(shù)(Ptr[i+1]-Ptr[i])。本文即采用該格式完成SpMV。3監(jiān)控性能分析現(xiàn)代處理器在單個芯片內(nèi)集成了或多或少的多個處理核心,并通過并行流水來提高處理器理論上的最高運算能力,未來會延續(xù)這一趨勢。如NVIDIAGTX280的GPU理論上的峰值性能約為933GFLOPS,全局存儲器帶寬的峰值超過141GBPS。這一方面為程序的高性能提供了條件,另一方面眾多核心的并行化也使得內(nèi)存器壁壘越來越突出。尤其是對本文的SpMV計算而言,數(shù)據(jù)從存儲器取出后基本上只做一次計算,無法發(fā)揮緩存的效力。另外,由于GPU的SIMT(SingleInstructionMultipleThread)架構(gòu),多級存儲器體系模型及尺寸、訪問等諸多限制使得基于GPU的內(nèi)存瓶頸類算法困難重重。只有將計算本身的數(shù)據(jù)結(jié)構(gòu)、計算特征等與GPU的線程映射、數(shù)據(jù)訪問結(jié)合在一起,才有望獲得較高的性能。由此,針對NVIDIA的CUDA研究了如下若干SpMV的優(yōu)化策略。3.1穩(wěn)定性條件拓展根據(jù)SpMV計算行無關(guān)的特性,并行SpMV最自然的想法是結(jié)果向量的每個元素由一個線程計算,即每個線程負責將稀疏矩陣的一行與輸入向量相乘。這種方式較適合比較少的處理器核心且線程獨立調(diào)度的并行計算平臺。而對于CUDA的體系架構(gòu),SM(StreamMultiprocessors)將線程塊劃分為多個Warp,以Warp為執(zhí)行單元,同一Warp內(nèi)線程自然同步,如圖2所示。若處于一個Warp內(nèi)線程對應處理的各行非零元素數(shù)目差異較大,則會造成諸多線程計算資源的空轉(zhuǎn)等待,即條件分支。此外,GPU需要調(diào)度大量線程才能有效掩蓋全局存儲器存取延遲,該策略在處理較小規(guī)模的矩陣(m值)時更不具優(yōu)勢。文獻的CSR(scalar)的實驗也證實了該策略是低效的。利用塊內(nèi)線程可同步的特性,一個線程塊(Block)對應一行是一種較為適合GPU的模式。但是,通常一個Block也要含有諸多線程(256是推薦設置),當一行的非零元素個數(shù)不能被Block內(nèi)線程總數(shù)整除時,也會有很大的概率導致若干線程無事可做;線程同步的額外開銷也是該模式的劣勢之一。文獻的CSR(vector)利用Warp內(nèi)線程天然同步的特性,嘗試了一個Warp計算一行(對應一個結(jié)果矩陣元素的計算),每個Block計算Block/Warp_Size行。如圖3所示,一個Warp有32個線程,在每行非零元素個數(shù)較少的時候仍然存在很多空轉(zhuǎn)。在上述策略的基礎(chǔ)上,結(jié)合合并訪問的需要,以Half-warp為單位完成稀疏矩陣一行與輸入向量相乘的計算,進一步縮減每行需要的線程數(shù)目,降低線程橫向空轉(zhuǎn)的比例。圖4給出了本文的策略。顯然,當非零元個數(shù)在相鄰行差異較大時,自然對應方式的缺陷則再次出現(xiàn),空轉(zhuǎn)無法絕對避免,但可以減少Warp內(nèi)同步等待。文獻采用了與本文相同的策略。3.2合并訪問首地址對齊和合并訪問是優(yōu)化GPU數(shù)據(jù)訪問的重要方面,尤其是針對計算能力1.2以下的設備而言,因為首地址沒有對齊而造成的非合并訪問會嚴重影響整體性能。本文采用取整提取的方法,即將前一行的尾巴當作這一行的開始,多余的部分只提取、不計算,如圖5所示。這與文獻的兩階段處理方法有所不同。合并訪問是Half-warp內(nèi)線程一起訪問存儲器,相鄰線程訪問相鄰的數(shù)據(jù),數(shù)據(jù)在存儲器的一個段上,才有最佳的效率。如此,我們將數(shù)據(jù)以行優(yōu)先的自然序存儲,以滿足合并訪問的要求。3.3存儲片式存儲GPU提供了多層次存儲器體系,不同的存儲器分級管理。它們?nèi)缦?(1)片外的全局存儲器;(2)片外的局部存儲器;(3)片上的共享存儲器;(4)片外的常量存儲器,擁有片上的Cache;(5)片外的紋理存儲器,擁有片上的Cache;(6)本地Register。由于全局存儲器的高延遲(200個時鐘周期),應盡量減少全局存儲器的訪問。將數(shù)據(jù)先讀入共享存儲器復用,以提高訪問存儲器的性能。Ptr的數(shù)據(jù)重用如圖6所示。最后將輸入向量放入紋理存儲器,通過紋理Cache提升性能。3.4高效主機的樹立CPU和GPU之間的傳輸是基于GPU通用計算的額外開銷。使用分頁鎖定的傳輸方式申請一塊CPU內(nèi)存,再將其拷貝到顯存,這在一定程度上減少了數(shù)據(jù)傳輸?shù)臅r間。然而,矩陣規(guī)模增大到一定程度時,鎖定了太多的內(nèi)存,同樣會影響GPU程序(Kernel)的執(zhí)行時間。實驗部分我們將對此進行分析。3.5重新設定ster平臺·減少Register使用量,提高處理器占用率優(yōu)化前一個線程的Register使用量是12個,occupancy僅為0.667,即三分之二。經(jīng)過分析,還有減少Register的余地。首先,將每個部分需要的計算量part_size作為參數(shù)傳入Kernel,盡量避免指令周期較長的除運算,減少了1個Register的使用。其次,乘積加和的reduction代碼做如圖7、圖8所示的改動,減少了3個if條件判斷語句,同時減少了1個Register的使用。至此Register的使用量減少為10個。從Profile可以看到,多處理器的使用率occupancy達到1?！な褂脙?nèi)部函數(shù)和位運算Kernel中盡量使用CUDA提供的標準數(shù)學函數(shù),使用位運算代替指令周期較長的除法運算。4采用octorsor博弈實驗是在CPU為AMDAthlonDualCoreProcessor3600+,GPU是Geforce8800GTX(CUDA2.0),2GB主存的環(huán)境中進行的,本文方法命名為CUDASpMV。稀疏矩陣來源于線性系統(tǒng)的標準測試用例。4.1合并訪問的數(shù)量線程映射和數(shù)據(jù)訪問是GPU優(yōu)化的最重要的兩個方面。首先,給出對齊訪問策略的有效性。如表1所列,Profiler統(tǒng)計顯示本文方法大幅度地提高了合并訪問的數(shù)量。圖9、圖10給出了Warp,Half-warp及數(shù)據(jù)復用所帶來的帶寬和浮點吞吐量的提升,顯示了本文各種策略的有效性,其中對齊訪問和高速存儲器對性能影響更大。4.2cudaspvm與cudpp、hyb的比較CUDPP和SpMVlibrary是來自NVIDIA的最新的基于CUDA的SpMV,IBM研究院的方法獲得了與SpMVlibrary相近的結(jié)果。本節(jié)將CUDASpMV與CUDPP和SpMVlibrary中的CSR(vector),ELL和HYB進行比較,如圖11、圖12所示。從圖中可以看出,CUDASpMV在帶寬和浮點性能上全面超越了CUDPP和CSR(Vector);HYB和ELL在帶寬上比CUDASpMV高的原因是它比CSR存儲了更多的數(shù)據(jù)。在實際浮點性能上,三者在不同的稀疏矩陣實例各有優(yōu)勢?？傮w上,在同樣存儲格式CSR下,本文的方法是最高效的。4.3高效數(shù)據(jù)的比較本小節(jié)我們與CPU的串行執(zhí)行的結(jié)果進行對比,圖13給出了計算部分的加速比,圖14給出了整體性能的加速比。從上圖中可以看出,隨著矩陣規(guī)模和非零元素個數(shù)的增大,計算部分的加速比也隨之增大,但CPU與GPU的數(shù)據(jù)傳輸時間也隨之增大。圖15特別給出了數(shù)據(jù)傳輸與計算時間的對比。從圖中可以看出數(shù)據(jù)的傳輸時間在整體時間中占了絕對的比重,SpMVCUDA用