基于CUDA的并行PCG方法自動生成系統(tǒng)研究與實(shí)現(xiàn)

1、碩士學(xué)位論文論文題目： 基于CUDA的并行PCG方法自動生成系統(tǒng)研究與實(shí)現(xiàn)作者姓名壬空 指導(dǎo)教師高家全教授 學(xué)科專業(yè)計(jì)算機(jī)技術(shù) ， 培養(yǎng)類別 全日制專業(yè)學(xué)位碩士所在學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院浙江工業(yè)大學(xué)碩士學(xué)位論文基于CUDA的并行PCG方法自動生成系統(tǒng)研究與實(shí)現(xiàn)作者姓名：王宇指導(dǎo)教師：高家全教授浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Dissertation Submitted to Zhejiang University of Technologyfor the Degree of MasterThe Automatic Generation System of the Parallel PCGM

2、ethod Based on CUDACandidate: Yu WangAdvisor: Prof. Jiaquan GaoCollege of Computer Science and TechnologyZhejiang University of TechnologyMar. 2017浙江工業(yè)大學(xué)學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所提交的學(xué)位論文是本人在導(dǎo)師的指導(dǎo)下，獨(dú)立進(jìn)行研究工作 所取得的研究成果。除文中已經(jīng)加以標(biāo)注引用的內(nèi)容外，本論文不包含其他個人或 集體已經(jīng)發(fā)表或撰寫過的研究成果，也不含為獲得浙江工業(yè)大學(xué)或其它教育機(jī)構(gòu)的 學(xué)位證書而使用過的材料。對本文的研究作出重要貢獻(xiàn)的個人和集

3、體，均已在文中 以明確方式標(biāo)明。本人承擔(dān)本聲明的法律責(zé)任。作者簽名：日期:I產(chǎn)3月2g日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留 并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本 人授權(quán)浙江工業(yè)大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢 索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。本學(xué)位論文屬于1、保密口，在一年解密后適用本授權(quán)書。2、保密口，在二年解密后適用本授權(quán)書。3、保密口，在三年解密后適用本授權(quán)書。4、不保密SZ（請?jiān)谝陨舷鄳?yīng)方框內(nèi)打“ J”）作者簽名: 王亨日期：2W筍3月2了日導(dǎo)

4、師簽名：而氟*日期：年J月左日基于CUDA的并行PCG方法自動生成系統(tǒng)研究與實(shí)現(xiàn)摘 要預(yù)條件共轆梯度(PCG)算法作為求解稀疏線性方程組的主流方法之一，近年來隨著 問題規(guī)模的增大和GPU計(jì)算能力的快速提高，用于求解大規(guī)模問題的并行PCG算法引起 了更廣泛的關(guān)注。并行PCG算法的研究重點(diǎn)是針對該方法的主要成分研究實(shí)現(xiàn)高效的并行 方法。如果通過人為方式尋找各個成分的最優(yōu)實(shí)現(xiàn)，由于每個成分實(shí)現(xiàn)方式多樣，而且影 響其性能的參數(shù)取值范圍廣，顯然需要極大的工作量。為此，本論文通過優(yōu)化建模技術(shù)，對PCG算法的主要成分分別構(gòu)建并行優(yōu)化性能模型, 從現(xiàn)有的核函數(shù)中選擇出最優(yōu)的核函數(shù)和參數(shù)配置，達(dá)到快速生成高效并

5、行PCG算法的目 的。本論文的主要工作和貢獻(xiàn)如下：提出矢量運(yùn)算、矢量內(nèi)積的并行優(yōu)化性能模型。分別對矢量運(yùn)算、矢量內(nèi)積建立并 行優(yōu)化性能模型，通過決策樹生成算法，自動生成決策樹。實(shí)驗(yàn)證明，本論文的矢量運(yùn)算、 矢量內(nèi)積決策樹對核函數(shù)以及參數(shù)的選擇非常有效。提出稀疏矩陣矢量乘(SpMV)的并行優(yōu)化性能模型。以5種經(jīng)典的存儲格式為例, 建立并行優(yōu)化性能模型，并通過自動選擇最優(yōu)核函數(shù)算法，自動選擇稀疏矩陣最佳的存儲 格式、最優(yōu)的核函數(shù)以及參數(shù)配置。實(shí)驗(yàn)證明，本論文的SpMV并行優(yōu)化性能模型預(yù)測核 函數(shù)的執(zhí)行時間的精度達(dá)95%以上，自動選擇核函數(shù)算法具有魯棒性，可靠性強(qiáng)。提出PCG并行優(yōu)化框架。該框架包含

6、PCG算法各個成分的并行優(yōu)化性能模型，各 個模型相互獨(dú)立，具有很強(qiáng)的可擴(kuò)展性。設(shè)計(jì)并實(shí)現(xiàn)基于CUDA的并行PCG方法自動生成系統(tǒng)。該系統(tǒng)使用圖形化界面為 PCG算法的主要成分構(gòu)建并行優(yōu)化性能模型，自動生成高效的并行PCG方法。實(shí)驗(yàn)證明， 自動生成系統(tǒng)是有效可行的，通過本系統(tǒng)自動生成的并行PCG方法在單個GPU上的平均 加速比為56.91,在單節(jié)點(diǎn)2個GPU上的平均加速比可達(dá)到104.06o關(guān)鍵詞：并行PCG方法，性能模型，自動生成系統(tǒng)，CUDA, GPUThe Automatic Generation System of the Parallel PCGMethod Based on CUDA

7、ABSTRACTThe preconditioned conjugate gradient (PCG) algorithm is one of the popular methods for solving large sparse linear systems. In recent years, accelerating the PCG algorithm on GPU has attracted considerable attention. However, on a specific multi-GPU platform, producing a highly parallel PCG

8、 implementation for any laige-sized problem requires significant time because several manual steps are involved in adjusting the related parameters and selecting an appropriate storage format for the matrix block that is assigned to each GPU.Therefore, using the optimizing model technology, we const

9、ruct the performance model for each one of main components of the PCG algorithm, and thus rapidly generate the parallel PCG algorithm by automatically selecting the optimal kernel and corresponding parameters from existing kernels. The main work and contributions are summarized as follows:Construct

10、the parallel optimization performance models for the vector operation and inner product. Utilizing the vector-operation and inner-product optimization models, decision trees are automatically generated.Construct parallel optimization performance model for SpMV. We take five classical storage formats

11、 and corresponding kernels to construct the performance models. Experimental results show that the accuracy of the execution time that is estimated by our proposed SpMV optimization performance model is more than 95%.Design a parallel optimization framework of PCG. In our proposed PCG optimization f

12、ramework, each model is independent and easily extensible.Implement an automatic generation system of the PCG method. This system can use the graphical visualization interface to build the parallel optimization performance model for each one of main components of the PCG algorithm, and thus automati

13、cally generate the PCG algorithm with high performance. Experimental results show that the average speedup ratios of the parallel PCG algorithm are 56.91 and 104.06 on one GPU and two GPUs, respectively.Key Words: parallel PCG method, performance model, automatic generation system,CUDA, GPU摘 要第1章緒 論

14、1.1課題研究的背景和意義 TOC o 1-5 h z HYPERLINK l bookmark64 o Current Document 國內(nèi)外研究現(xiàn)狀及趨勢21.2.1并行SpMV算法的研究2并行PCG算法的研究3SpMV性能評估的研究31.3研究內(nèi)容1.4論文章節(jié)安排相關(guān)技術(shù)及PCG并行優(yōu)化框架 TOC o 1-5 h z HYPERLINK l bookmark91 o Current Document CUDA 介紹7CUDA并行計(jì)算7CUDA編程模型8CUDA存儲器模型9 HYPERLINK l bookmark101 o Current Document 2.2稀疏矩陣存儲格式1

15、0COO存儲格式10CSR存儲格式10DIA存儲格式11ELL存儲格式11HYB存儲格式11 HYPERLINK l bookmark112 o Current Document PCG 算法12 HYPERLINK l bookmark125 o Current Document PCG并行優(yōu)化框架14 HYPERLINK l bookmark128 o Current Document 本章小結(jié)15 HYPERLINK l bookmark133 o Current Document 第3章矢量運(yùn)算和矢量內(nèi)積并行優(yōu)化性能模型研究16 HYPERLINK l bookmark136 o Cu

16、rrent Document 3.1矢量運(yùn)算的并行優(yōu)化性能模型16獲取GPU特性163.1.2核模型16實(shí)驗(yàn)設(shè)置173.1.4并行優(yōu)化性能模型的構(gòu)建173.1.5生成決策樹18 HYPERLINK l bookmark150 o Current Document 矢量內(nèi)積的并行優(yōu)化性能模型19獲取GPU特性20核模型20實(shí)驗(yàn)設(shè)置203.2.4并行優(yōu)化性能模型的構(gòu)建203.2.5生成決策樹22 HYPERLINK l bookmark161 o Current Document 本章小結(jié)22 HYPERLINK l bookmark166 o Current Document 第4章SpMV和預(yù)

17、條件子的并行優(yōu)化性能模型研究24 HYPERLINK l bookmark169 o Current Document SpMV的并行優(yōu)化性能模型24獲取GPU特性24核模型25實(shí)驗(yàn)設(shè)置254.1.4并行優(yōu)化性能模型建立274.1.5自動選擇最優(yōu)核函數(shù)算法32 HYPERLINK l bookmark208 o Current Document 4.2預(yù)條件子并行算法以及并行優(yōu)化性能模型33 HYPERLINK l bookmark211 o Current Document 本章小結(jié)34 HYPERLINK l bookmark216 o Current Document 第5章系統(tǒng)實(shí)現(xiàn)與實(shí)

18、驗(yàn)比較35 HYPERLINK l bookmark219 o Current Document 5.1系統(tǒng)設(shè)計(jì)與圖形化交互建模35系統(tǒng)設(shè)計(jì)35圖形化交互建模37 HYPERLINK l bookmark236 o Current Document 實(shí)驗(yàn)比較435.2.1測試矢量運(yùn)算、矢量內(nèi)積決策樹的有效性435.2.2測試SpMV并行優(yōu)化性能模型預(yù)測核函數(shù)執(zhí)行時間的精準(zhǔn)度455.2.3測試自動選擇最優(yōu)核函數(shù)算法選擇最優(yōu)核函數(shù)的精準(zhǔn)度48自動生成的并行PCG方法性能測試49 HYPERLINK l bookmark239 o Current Document 本章小結(jié)51 HYPERLINK

19、l bookmark244 o Current Document 第6章結(jié)論與展望53 HYPERLINK l bookmark247 o Current Document 結(jié)論53 HYPERLINK l bookmark255 o Current Document 展望54 HYPERLINK l bookmark261 o Current Document 參考文獻(xiàn)55 HYPERLINK l bookmark322 o Current Document 致 謝59 HYPERLINK l bookmark325 o Current Document 攻讀學(xué)位期間參加的科研項(xiàng)目和成果60

20、第1章緒 論1.1課題研究的背景和意義大型稀疏線性方程組的求解一直是科學(xué)與工程計(jì)算領(lǐng)域里最重要的問題之一。目前， 求解稀疏線性方程組的方法主要分為直接法和迭代法兩大類。直接法是經(jīng)過有限步四則 運(yùn)算求得近似解，該方法對于低階稠密矩陣方程組的求解比較有效。迭代法是經(jīng)過迭代計(jì) 算，在迭代的過程中逐漸逼近于精確解。相比直接法，迭代法的運(yùn)算量和存儲量小而備 受研究者們的青睞。預(yù)條件共貌梯度（PCG）算法是迭代法中最流行的方法之一，近年 來，隨著人們探索問題規(guī)模和深度的增大，迫切需要提高其計(jì)算效率。隨著互聯(lián)網(wǎng)的發(fā)展，大數(shù)據(jù)時代已經(jīng)悄然而至。大數(shù)據(jù)帶來的其中一個挑戰(zhàn)就是要求 處理速度快囹，在海量的數(shù)據(jù)面前，

21、處理數(shù)據(jù)的效率就顯得尤為重要。近年來，GPU已經(jīng) 演變成一個具有高度并行、多線程的多核處理器，并且擁有強(qiáng)大的計(jì)算能力和極高的內(nèi)存 帶寬。2006年11月，NVIDIA公司發(fā)布了通用并行計(jì)算平臺和編程模型CUDA，它允許 程序員使用高級語言進(jìn)行CUDA編程，并且還提供了大量并行庫，例如用于基本線性代數(shù) 的cuBLAS和用于加速訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)的cuDNN等，使GPU編程變得非常容易。由于GPU的高計(jì)算能力，研究者為了提高PCG算法的計(jì)算效率，將PCG算法遷移到 GPU平臺上。目前，GPU加速的并行PCG算法已有較多的研究成果，例如并行MIC預(yù)條 件PCG算法A和并行SSOR預(yù)條件PCG算法等。不

22、難發(fā)現(xiàn)，PCG算法主要由矢量運(yùn) 算、矢量內(nèi)積、預(yù)條件子方程求解和稀疏矩陣矢量乘（SpMV）等主要成分組成。如果想 獲得高性能的并行PCG算法，那就必須研究這些主要成分的高效并行實(shí)現(xiàn)方法。高效的CUDA程序不僅要求程序要充分使用GPU稀有的片上資源（寄存器、共享內(nèi) 存等），使其利用率達(dá)到最大化，而且在運(yùn)行核函數(shù)時，還需要人工進(jìn)行合理地分配線程, 使得程序并行達(dá)到最大化。不同的GPU,它達(dá)到最佳性能的參數(shù)往往是不同的，需要遍歷 塊內(nèi)線程數(shù)，以找到最合適的線程分配。對于PCG算法來說，現(xiàn)有GPU加速的矢量運(yùn)算、 矢量內(nèi)積、預(yù)條件子方程求解和稀疏矩陣矢量乘（SpMV）方法較多，特別是SpMV,還 與存

23、儲格式相關(guān)。因此，如果生成并行PCG算法的過程中使用人工參與方式進(jìn)行調(diào)優(yōu)和選 擇最優(yōu)的核函數(shù)，當(dāng)面對計(jì)算機(jī)集群時，就會變得繁重，需要極大的工作量。這促使了我 們的動機(jī)：通過優(yōu)化建模技術(shù)，對PCG算法的主要成分分別構(gòu)建并行優(yōu)化性能模型，以達(dá) 到能自動從現(xiàn)有的核函數(shù)中為PCG算法的主要成分快速選擇出最優(yōu)的核函數(shù)和參數(shù)配置, 自動生成高效的并行PCG算法，避免大量繁瑣的人工調(diào)優(yōu)過程。因此，本論文研究不是構(gòu)造一個新的核或算法，而是從PCG算法的主要成分出發(fā)，通 過構(gòu)造其與問題無關(guān)的優(yōu)化模型，達(dá)到自動快速生成高效并行PCG算法的目的，這與其他 的PCG算法加速研究有著本質(zhì)的區(qū)別。1.2國內(nèi)外研究現(xiàn)狀及趨

24、勢與并行PCG方法自動生成系統(tǒng)相關(guān)的研究包括并行SpMV算法、并行PCG算法和 SpMV性能評估等方面，下面從這幾個方面分別介紹其國內(nèi)外研究現(xiàn)狀。1.2.1并行SpMV算法的研究如果一個矩陣中的零元素個數(shù)遠(yuǎn)遠(yuǎn)多于它的非零元素個數(shù)，那么這樣的矩陣稱之為稀 疏矩陣。對于稀疏矩陣，為了減少不必要的冗余計(jì)算和存儲空間，通常需要對稀疏矩陣進(jìn) 行存儲。目前，存在多種稀疏存儲格式，每種存儲格式都有自身的特點(diǎn)，對同一個稀疏矩 陣來說，采用不同的存儲格式就會獲得不同的SpMV性能。對于稀疏矩陣而言，只有根據(jù) 它的非零元素特征分布，選擇最合適的存儲格式，SpMV核函數(shù)才能發(fā)揮最佳性能。由于在迭代方法中，SpMV占

25、有重要的地位I%研究者們著重對它進(jìn)行了研究。2008 年，Bell和Garlandtl3詳細(xì)分析了 COO、CSR、ELL和DIA這4種經(jīng)典稀疏存儲格式的優(yōu) 缺點(diǎn)，并提出HYB存儲格式，將ELL和COO存儲格式一起使用，減少了 ELL存儲格式 零元素的填充?；谶@些存儲格式，作者們提出了一些高效的SpMV CUDA核函數(shù)，并把 它們封裝在CUSP開源包中供研究者們下載使用。后來研究者們又對這些存儲格式進(jìn)行了改進(jìn)和擴(kuò)展。Zheng等Ml對ELL進(jìn)行了改進(jìn)， 提出了 BiELL存儲格式，可以減少零元素的填充，并在GPU上基于BiELL存儲格式實(shí)現(xiàn) 了 SpMV,當(dāng)矩陣每行非零元素不均勻的時候，Bi

26、ELL存儲格式性能要比ELL好o Maggioni 等I*在ELL基礎(chǔ)上提出了一種自適應(yīng)的ELL存儲格式：AdELL,使得每個warp計(jì)算時負(fù) 載均衡。Dang等提出sliced COO (SCOO),進(jìn)而實(shí)現(xiàn)一種SCOO SpMV核，當(dāng)矩陣是 單精度浮點(diǎn)數(shù)時，SCOO SpMV性能要比COO和CSR SpMV核都要好。Liu等刀為了克 服CSR線程負(fù)載不平衡的缺點(diǎn)，設(shè)計(jì)了一種CSR5存儲格式，提出了高通量的SpMV核。 為了減少存儲空間，Yan等18使用分塊技術(shù)，提出了 BCCOO和BCCOO+存儲格式，有效 減少了傳統(tǒng)COO的存儲空間。Choi等19提出了 BCSR存儲格式，減少了 CSR

27、行索引和列浙江工業(yè)大學(xué)碩士學(xué)位論文 索引的存儲空間，利用基于模型的自動選擇參數(shù)框架，自動調(diào)節(jié)塊block大小。當(dāng)選擇合 適塊大小(Blocksize)的時候，BCSR SpMV核的性能比CSR SpMV核優(yōu)。Tang等刖使 用位表示優(yōu)化技術(shù)壓縮index和data數(shù)組來減少存儲空間，提出BRO-ELL、BRO-COO、 BRO-HYB 等 SpMV 核。另外，研究者們還提出很多新的存儲格式，例如CSX存儲格式21, BRC存儲格式22, BRO存儲格式，AMB存儲格式網(wǎng)，SELL-C-o存儲格式和JAD存儲格式網(wǎng)等，基于 這些存儲格式，也提出了一些有效的SpMV核。1.2.2并行PCG算法的研

28、究Jacobi預(yù)條件子是較早提出用于CG算法的預(yù)條件子2728,為了提高其效率，研究者 又設(shè)計(jì)了 ILU預(yù)條件子29、SSOR預(yù)條件子3、代數(shù)多級網(wǎng)格預(yù)條件子8刖和Gauss-Seidel 預(yù)條件子皿等，進(jìn)而提出了許多有效的PCG算法。由于PCG算法中預(yù)條件子方程求解時, 需要前推和回代過程，導(dǎo)致不易并行化，為提高其效率，有研究者對其進(jìn)行了研究。Liu和Chen等閔釧在GPU上實(shí)現(xiàn)了多個預(yù)條件PCG并行算法，實(shí)驗(yàn)數(shù)據(jù)顯示可以有 效求解大型線性系統(tǒng)。Li和Saad?！繉?shí)現(xiàn)了 MIC預(yù)條件PCG并行算法，獲得了 3倍的加速 比。Gao和Liang等in對稀疏對稱正定的七對角矩陣，提出了一種有效的M

29、IC預(yù)條件GPU 并行實(shí)現(xiàn)方法，比cuSPARSE庫實(shí)現(xiàn)快3倍左右。為了避免預(yù)條件子方程求解過程中的前 推和回代，也有研究者利用稀疏近似逆技術(shù)，將預(yù)條件子方程求解轉(zhuǎn)變成僅需一個SpMV 的運(yùn)算，提高并行效率。例如，Helfenstein和 險(xiǎn)村提出了 SSSOR近似逆預(yù)條件PCG算 法，獲得了 10倍的加速比。王志超等D習(xí)利用諾依曼多項(xiàng)式分解技術(shù)，給出了在GPU上一 階和二階SSOR稀疏近似逆并行PCG算法。1.2.3 SpMV性能評估的研究性能評估是本論文模型建立的核心，直接影響模型預(yù)測的精準(zhǔn)度。Monteiro等使用 矩陣樣本集合訓(xùn)練靜態(tài)模型(STOMP),通過靜態(tài)模型預(yù)測SpMV的執(zhí)行時

30、間，該靜態(tài)模 型預(yù)測精度達(dá)到95.3%。Neelima等閔閔提出稀疏矩陣存儲格式預(yù)測模型，通過分析稀疏矩 陣非零元素的分布特點(diǎn)，按照事先制定好的規(guī)則進(jìn)行預(yù)測，如果有不滿足規(guī)則的稀疏矩陣, 需要結(jié)合CPU跟GPU的傳輸開銷再進(jìn)行判斷，但該模型在預(yù)測稀疏矩陣存儲格式的過程 中并未考慮到SpMV計(jì)算的時間。Li等39,4。利用概率模型，可以準(zhǔn)確描述稀疏矩陣的非零 元素分布情況，能預(yù)測稀疏矩陣存儲格式的選擇，但每次預(yù)測前都需要對目標(biāo)稀疏矩陣進(jìn) 行概率模型分析，再根據(jù)GPU硬件參數(shù)進(jìn)行性能評估。Zardoshti等叩】提出一種自適應(yīng)的 -3-運(yùn)行時系統(tǒng)來選擇稀疏矩陣最佳的存儲格式，該系統(tǒng)需要將目標(biāo)矩陣劃

31、分成幾個樣例矩陣 輸入系統(tǒng)中，系統(tǒng)根據(jù)樣例矩陣來測試和對比，最后輸出最佳存儲格式。GUO等42,43通過 構(gòu)造基矩陣集合，提出了一種基于profile的GPU SpMV性能模型，能預(yù)測CSR、ELL、 COO和HYB SpMV核函數(shù)的執(zhí)行時間，該模型只跟GPU資源本身有關(guān)，它只需要一次建 模，后面不管有多少測試矩陣，都不要再重新建模，但論文中沒有考慮到GPU參數(shù)（線 程分布等）對SpMV性能的影響。Guo和Lee】44】對Guo等的模型做了進(jìn)一步改進(jìn)，增加 了 Li等I的矩陣分析方法，但準(zhǔn)確率還是跟原來一樣。本論文是受到Guo等性可性能模型的啟發(fā)，在此基礎(chǔ)上進(jìn)行優(yōu)化、擴(kuò)充，并作進(jìn)一步更 深的研

32、究，提出了只跟GPU資源有關(guān)并且具有很強(qiáng)擴(kuò)展能力的并行優(yōu)化框架。1.3研究內(nèi)容本論文研究目標(biāo)并不是為了提出一種新的PCG并行加速算法，而是系統(tǒng)根據(jù)所需要的 運(yùn)算及給定的問題，通過并行優(yōu)化建模技術(shù)，構(gòu)造矢量運(yùn)算、矢量內(nèi)積、稀疏矩陣矢量乘 （SpMV）和預(yù)條件子方程求解等優(yōu)化模型，從現(xiàn)有的核函數(shù)中挑選出最優(yōu)的核函數(shù)，自 動生成高效的PCG并行算法。本論文的核心是結(jié)合CUDA特性，分析影響PCG算法性能的關(guān)鍵成分：矢量運(yùn)算、 矢量內(nèi)積、稀疏矩陣矢量乘（SpMV）和預(yù)條件子方程求解，分別對這些關(guān)鍵成分構(gòu)建并 行優(yōu)化性能模型。構(gòu)建的模型只與GPU本身資源有關(guān)，對一種類型的GPU,我們的模型 僅需構(gòu)建一次

33、。本論文的自動生成系統(tǒng)具有很強(qiáng)的可擴(kuò)展性，假設(shè)沒有包括在系統(tǒng)框架中 的核模型，只要能建立起性能模型，就能將它加入到系統(tǒng)框架中。下面是本論文的具體研 究內(nèi)容：矢量運(yùn)算的并行優(yōu)化性能模型研究對于矢量運(yùn)算而言，影響它們的性能好壞主要是核函數(shù)的選擇以及線程資源分配。通 過建立矢量運(yùn)算的并行優(yōu)化性能模型，最后生成決策樹。給定一個矢量，通過決策樹能夠 自動快速地找出最優(yōu)的核函數(shù)以及運(yùn)行時的線程參數(shù)分配，使得矢量運(yùn)算核函數(shù)性能達(dá)到 最優(yōu)。矢量內(nèi)積的并行優(yōu)化性能模型研究由于矢量內(nèi)積運(yùn)算存在歸約操作，我們定義最小線程塊數(shù)來權(quán)衡線程塊數(shù)大小。構(gòu)建 矢量內(nèi)積的并行優(yōu)化性能模型，最后生成決策樹。給定一個矢量，通過決策

34、樹快速找出線 程數(shù)配置，使得矢量內(nèi)積核函數(shù)性能達(dá)到最優(yōu)。SpMV的并行優(yōu)化性能模型研究SpMV的情況要比矢量運(yùn)算和矢量內(nèi)積復(fù)雜。除了要合理分配線程外，還要找出最合 適的存儲格式，只有選擇最合適的存儲格式，SpMV核函數(shù)才能發(fā)揮最佳性能。本論文以 5個經(jīng)典的稀疏存儲格式CSR、DIA、ELL、COO和HYB以及它們對應(yīng)核函數(shù)為例，建立 SpMV的并行優(yōu)化性能模型，通過自動選擇最優(yōu)核函數(shù)算法，給定一個稀疏矩陣，能夠快 速找出最適合的存儲格式、核函數(shù)以及線程分配。預(yù)條件子的并行優(yōu)化模型研究通過建立的近似逆預(yù)條件子，預(yù)條件子方程求解轉(zhuǎn)變成為SpMV,這樣在預(yù)條件子求 解過程即可使用SpMV并行優(yōu)化性能

35、模型來調(diào)優(yōu)程序性能。PCG的并行優(yōu)化框架提出PCG并行優(yōu)化框架，該框架包含各個運(yùn)算的并行優(yōu)化性能模型，具有很強(qiáng)的可擴(kuò) 展性。并行PCG方法自動生成系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)并行PCG方法自動生成系統(tǒng)，使用圖形化界面操作，為PCG算法的主要 成分構(gòu)建并行優(yōu)化性能模型，選擇最優(yōu)核函數(shù)，自動生成高效的并行PCG算法。1.4論文章節(jié)安排第一章緒論首先介紹基于CUDA的并行PCG方法自動生成系統(tǒng)研究與實(shí)現(xiàn)的研究背景，以及 研究的目的和意義。其次介紹并行SpMV算法、并行PCG算法和SpMV性能評估這三方面的國內(nèi)外研 究現(xiàn)狀及趨勢。介紹本文的主要研究內(nèi)容。第二章相關(guān)技術(shù)及PCG并行優(yōu)化框架介紹本論文的相關(guān)技術(shù)，CUD

36、A、5種經(jīng)典的稀疏存儲格式和PCG算法。提出PCG并行優(yōu)化框架。第三章矢量運(yùn)算和矢量內(nèi)積的并行優(yōu)化性能模型研究詳細(xì)介紹矢量運(yùn)算、矢量內(nèi)積的并行優(yōu)化性能模型的構(gòu)建過程，以及決策樹生成算法。第四章SpMV和預(yù)條件子的并行優(yōu)化性能模型研究SpMV的并行優(yōu)化性能模型研究按照PCG并行優(yōu)化框架，詳細(xì)介紹了獲取GPU特性、核模型、實(shí)驗(yàn)設(shè)置、各個存儲 格式的并行優(yōu)化性能模型建立以及自動選擇最優(yōu)核函數(shù)算法這五個模塊。預(yù)條件子的并行優(yōu)化性能模型研究使用SSOR稀疏近似逆預(yù)條件子，將預(yù)條件子方程求解過程變成SpMV運(yùn)算。第五章系統(tǒng)實(shí)現(xiàn)與實(shí)驗(yàn)比較詳細(xì)介紹系統(tǒng)設(shè)計(jì)，通過ELL存儲格式案例來介紹系統(tǒng)圖形化建模的過程。實(shí)

37、驗(yàn)比較，分別從以下四個方面進(jìn)行實(shí)驗(yàn)對比：1）測試矢量運(yùn)算、矢量內(nèi)積的決策樹有效性；2）測試SpMV并行優(yōu)化性能模型預(yù)測 核函數(shù)執(zhí)行時間的精準(zhǔn)度以及跟其他研究者模型對比；3）測試自動選擇最優(yōu)核函數(shù)算法 選擇最優(yōu)核函數(shù)的精準(zhǔn)度；4）自動生成的PCG方法性能測試。第六章結(jié)論與展望。對本文的研究工作進(jìn)行總結(jié)，并展望未來的研究內(nèi)容。第2章 相關(guān)技術(shù)及PCG并行優(yōu)化框架本章主要有兩個方面的內(nèi)容，一、介紹本論文涉及的相關(guān)技術(shù)，主要包括CUDA、稀 疏矩陣存儲格式和PCG算法。二、提出本文的PCG并行優(yōu)化框架。CUDA 介紹CUDA并行計(jì)算隨著計(jì)算機(jī)芯片制作工藝的不斷提升，現(xiàn)代計(jì)算機(jī)已經(jīng)演變?yōu)槎嗪恕⒍嗑€程處理

38、器， 這就要求編程人員要從以前的串行、單線程的問題求解方法切換到多線程并行執(zhí)行的問題 求解方法4習(xí)。并行計(jì)算的產(chǎn)生得益于多核多線程處理器的出現(xiàn)，它通常要把一個大問題分 解為很多獨(dú)立的小問題，使用多個處理器或者計(jì)算機(jī)同時進(jìn)行計(jì)算I。并行計(jì)算最主要的 目的就是提高計(jì)算的速度。近年來，GPU憑借著高計(jì)算強(qiáng)度和高內(nèi)存帶寬在并行計(jì)算領(lǐng)域中如火如荼。在某種程 度上講，也得益于成熟的編程模型。2006年11月，NVIDA提供了一個易用的編程接口， 也就是通用并行計(jì)算平臺和編程模型CUDA。CUDA是在標(biāo)準(zhǔn)語言的基礎(chǔ)上進(jìn)行了擴(kuò)展， 使得程序員只要學(xué)習(xí)目前流行的編程語言（C語言等），就能夠非常容易地使用它。為了

39、讓 不同領(lǐng)域的人都能簡單地使用CUDA技術(shù)，NVIDA公司還發(fā)布了很多已經(jīng)封裝好的并行 庫，如:cuBLAS, cuSPARSE48等。DRAMDRAMGPUCPU圖2-1 CPU結(jié)構(gòu)與GPU結(jié)構(gòu)GPU與CPU結(jié)構(gòu)有很大區(qū)別，如圖2-1所示。從圖2-1中，可以非常直觀地發(fā)現(xiàn)GPU 的處理器（綠色部分）要比CPU多，而CPU的控制器（黃色部分）和高速緩存（紅色部 分）要比GPU多?？梢?，GPU設(shè)計(jì)了更多的處理器去處理數(shù)據(jù)而不是數(shù)據(jù)緩存和邏輯控 制，是一個面向計(jì)算、吞吐量的多線程、多核處理器。CUDA編程模型在GPU上實(shí)現(xiàn)程序并行化一般需要滿足以下三個條件：a）細(xì)粒度并行；b）計(jì)算密集 型；c）各

40、計(jì)算任務(wù)之間松耦合，最好相互獨(dú)立。CUDA編程模型允許程序在異構(gòu)系統(tǒng)上執(zhí) 行，通常把串行代碼放在主機(jī)端（host）執(zhí)行，并行代碼放在設(shè)備端（device）執(zhí)行。把在GPU 設(shè)備上的運(yùn)行代碼稱為核函數(shù)（kernel），使用_global_關(guān)鍵字聲明。核函數(shù)一旦被調(diào)用, 控制權(quán)馬上會返回給主機(jī)端（host）, GPU和CPU交替執(zhí)行。如圖2-246所示。CUDA C ApplilcationHost=CPUHost codeParallel kernelDevice=GPUHost codeHost=CPUParallel kernelDevice=GPU圖2-2 CUDA CPU與GPU交替執(zhí)行

41、CPU調(diào)用核函數(shù)時，必須按照以下語法：Kernel_function （parml, parm2, .）其中，gridDim表示網(wǎng)格內(nèi)線程塊數(shù)量和維度，blockDim表示線程塊內(nèi)線程數(shù)量和維 度，Ns用于動態(tài)分配共享內(nèi)存時指定的空間大小，s指定調(diào)用核函數(shù)時對應(yīng)的流。CUDA內(nèi)核以線程塊構(gòu)成的網(wǎng)格（grid）進(jìn)行啟動，一個網(wǎng)格由許多線程塊（block） 構(gòu)成，每個線程塊（block）由許多線程（thread）組成，如圖2-3所示。線程塊內(nèi)的每個線程共享同一個線程塊索引(blockldx),它是CUDA內(nèi)置的uint3類型的變量，作為線程 塊在網(wǎng)格內(nèi)的唯一索引。線程塊內(nèi)的每個線程也有內(nèi)置的uin

42、t3類型變量threadldx,作為 線程在線程塊中的唯一索引，通過訪問thieadldx和blockldx很容易區(qū)分每個線程。CUDA 中網(wǎng)格和線程塊都是三維的，通過dim3類型的CUDA內(nèi)置變量gridDim和blockDim來指 定。1111 /七 ，/1111、 ;、1 、1gridDim.x（網(wǎng)格） AEapC8blockDim.x(線程塊)圖2-3 CUDA線程層次結(jié)構(gòu)CUDA把32個線程稱為一個waip (線程束)，并作為它的基本執(zhí)行單元。一個warp 里的線程執(zhí)行同一條指令，因此需要減少或者避免程序中判斷語句的出現(xiàn)，比如if, for 語句等，防止出現(xiàn)warp分支。因?yàn)橐粋€wa

43、rp里的不同線程執(zhí)行不同的路徑，會導(dǎo)致程序 性能下降。CUDA存儲器模型CUDA存儲器模型提供了很多可編程的內(nèi)存類型：寄存器(Registers)本地內(nèi)存(Local memory) 共享內(nèi)存(Shared memory) 全局內(nèi)存(Global memory) 常量內(nèi)存(Constant memory)和質(zhì)地內(nèi)存(Texture memory),編程人員可以自由地控制數(shù)據(jù)的存儲。每個內(nèi)存 類型都有不同的使用范圍、生命周期以及緩存行為，如表2-1所示。寄存器是GPU稀有的 片上資源，是GPU最快的存儲器。寄存器變量是每個線程私有的，當(dāng)線程執(zhí)行結(jié)束，寄 存器變量就會失效。共享內(nèi)存也是GPU片上資

44、源，它跟CPU的L1高速緩存相似，但共 享內(nèi)存是可編程存儲器，可以被同一個塊內(nèi)的線程訪問，在使用的過程中需要避免bank 沖突的產(chǎn)生，防止程序性能下降。在編寫CUDA程序時，需要充分利用GPU的片上資源, 才能獲得更高的加速比。表2-1各種存儲器比較存儲器位置擁有緩存生命周期寄存器GPU片上N/A與Thread相同本地內(nèi)存板載顯存無與Thread相同共享內(nèi)存GPU片上N/A與bock相同常量內(nèi)存板載顯存有主機(jī)程序配置質(zhì)地內(nèi)存板載顯存有主機(jī)程序配置全局內(nèi)存板載顯存無主機(jī)程序配置2.2稀疏矩陣存儲格式由于稀疏矩陣存在大量的零元素，為了節(jié)省存儲空間和減少計(jì)算冗余量，需要對矩陣 做壓縮處理。近年來，學(xué)

45、者們對稀疏矩陣存儲格式進(jìn)行了很多的研究，也做了很多改進(jìn)。 常見經(jīng)典的稀疏矩陣壓縮格式有：COO、CSR、DIA、ELL和HYB等。COO存儲格式COO (Coordinate Format)是我們最簡單、通用的一種存儲格式網(wǎng)。這種存儲結(jié)構(gòu)使 用row, col, data這三個數(shù)組把稀疏矩陣的每個非零元素值保存下來，其中mvv數(shù)組存儲非 零元素對應(yīng)原始矩陣的行索引，c。/數(shù)組存儲非零元素對應(yīng)原始矩陣的列索引，也幻數(shù)組 存儲對應(yīng)的非零元素值。這三個數(shù)組的長度由稀疏矩陣總的非零元素個數(shù)決定的。COO存 儲格式具有通用性、簡單靈活易于操作，它可以存儲任何類型的稀疏矩陣，但我們需要存 儲每個非零元素的

46、坐標(biāo)和非零值，需要較大的存儲空間。具體例子如圖2-4 (b)所示。CSR存儲格式CSR( Compressed Sparse Row Format)在COO基礎(chǔ)上進(jìn)行了改進(jìn)，使用行偏移數(shù)組ptr 來代替COO的mw數(shù)組，列數(shù)組必力ces和非零元素值數(shù)組出億存儲方式跟COO 一樣。行 偏移數(shù)組P”保存也如數(shù)組每行第一個元素的起始偏移位置。假設(shè)稀疏矩陣有N行，則ptr 數(shù)組長度為N+1。稀疏矩陣第，行的非零元素個數(shù)可以通過計(jì)算p tri+l-ptri來獲得。 CSR同樣具有COO的靈活、易操作的特點(diǎn)，同時要比COO存儲空間少，是存儲格式中比 較常用的一種。具體例子請參考如圖2-4 (c)。DIA存

47、儲格式DIA (Diagonal),對角線壓縮存儲法，按對角線形式存儲，它使用次?柩和必M數(shù)組 來表示，其中，也幻數(shù)組存儲的是矩陣的非零元素的值，也2,數(shù)組存儲的是子對角線相 對于主對角線的位移。當(dāng)咖e心0時，則表示該非零元素位于主對角線上方，距離為 offseti的子對角線上。當(dāng)offseti0時，則表示該非零元素位于主對角線下方，距離為 offsets的子對角線上。當(dāng)offseti = 0時，表示該非零元素在主對角線上。DIA存儲格 式適合對角性很好的稀疏矩陣，執(zhí)行SPMV時，要比CSR、COO效率高。由于DIA存儲 格式的特殊特點(diǎn)，導(dǎo)致它不具有通用性。具體例子請參考如圖2-4 (d)。E

48、LL存儲格式ELL (ELLPACK),它由z所此攻和出幻這兩個數(shù)組來表示。對于一個MxN的稀疏矩 陣，我們把稀疏矩陣每行非零元素個數(shù)的最大值記為K。ELL存儲格式分別用一個MxK 的也幻數(shù)組和z如7詁紿數(shù)組來存儲非零元素值和對應(yīng)的列索引，那些每行平均非零元素個 數(shù)比K小的行用零元素填充。當(dāng)稀疏矩陣每行的非零元素個數(shù)較均勻的時候，就推薦使 用ELL存儲格式。如果每行平均非零元素個數(shù)跟K相差較大，則會占用不必要的存儲空 間和冗余計(jì)算，導(dǎo)致性能下降5。具體例子請參考圖2-4 (e)。HYB存儲格式由于ELL存儲格式在存儲每行非零元素個數(shù)分布不均勻的矩陣時，會降低程序性能。 Belltl3結(jié)合ELL

49、和COO的特點(diǎn)，提出了一種HYB的存儲格式。通過計(jì)算H值，把稀疏 矩陣每行H個非零元素采用ELL存儲格式來存儲，超出H部分的非零元素則采用COO存 儲格式存儲，其中H的取值標(biāo)準(zhǔn)是：矩陣包含H個非零元素個數(shù)的行至少要占稀疏矩陣總 行數(shù)的三分之一I%由于ELL執(zhí)行效率要比COO高，所以H值的選擇對HYB來說是至 關(guān)重要的。我們應(yīng)該把稀疏矩陣的主要部分使用ELL存儲，剩余少量部分使用COO來存 儲。具體例子請參考圖2-4 (f)。這里對稀疏存儲格式進(jìn)行簡單的總結(jié)：1、DIA和ELL存儲格式在執(zhí)行SpMV操作時效率最高。2、COO和CSR存儲格式比ELL和DIA靈活，易于操作，通用性強(qiáng)。3、HYB存儲

50、格式將ELL和COO的特點(diǎn)進(jìn)行了結(jié)合，但由于ELL的執(zhí)行效率要比 COO高的多，因此，應(yīng)該合理選擇H值，使得矩陣的絕大部分采用ELL存儲格式，剩余 小部分采用COO存儲格式。3070690208400051(a)稀疏矩陣row = 03ptr = 0 29col = 03indices = 03data = 32 8 4 5 1data = 3 71-*37-_02*-_37*-692offset = -1 0 2013692data =84*indices =12*data =84*51*23*51*(b) COO存儲格式(c) CSR存儲格式(d) DIA存儲格式(e) ELL存儲格式-3

51、7-0269indices =018412_51_23_data =ELL部分row = 1 co/ = 3data = 2(f)COO部分HYB存儲格式圖2-4稀疏矩陣表示2.3 PCG算法共軸梯度法(CG)是介于最速下降與Newton法之間的迭代方法，為了進(jìn)一步提高收斂的速度，研究者們引入預(yù)處理矩陣，大大提高了它的迭代收斂速度5此 比如：ICCG算 法52-54、ILUCG算法26和sSORCG算法52,55等。本論文使用的是Chronopoulous等56提 出來的PCG算法，因?yàn)樗咽噶窟\(yùn)算和內(nèi)積運(yùn)算聚集在一塊，這樣可以有效減少核函數(shù)的 數(shù)量，具體算法步驟見算法2-1。算法2-1： P

52、CG算法Input: A, b, , x (initialize x with zeros)Output: xr b Ax co = Mxr s = AcoPo = Fco； /z = sTa); a = Pq3, /? = 0for it 1, 2,., MAX_ ITER dop = + = p; q = s + gqx x+ap, r raqif |r|7 thenbreak;endco = Mxr, s Acopx rT/ = sTcoIL 6 = PjPo； a=pJ(N-pBla)； Po=P12. end無論什么版本的PCG算法，它的運(yùn)算主要包括SpMV、預(yù)條件子方程求解、矢量內(nèi)

53、積 運(yùn)算和矢量運(yùn)算等主要成分。假設(shè)稀疏矩陣A(x)的每行平均非零元素個數(shù)為k, PCG 算法運(yùn)行迭代次數(shù)為m ,則每個運(yùn)算的計(jì)算復(fù)雜度如表2-2所示。表2-2各個運(yùn)算的計(jì)算復(fù)雜度操作復(fù)雜度計(jì)算次數(shù)SpMVo(2kn)m + 1預(yù)條件子求解o(2kn)m + 1矢量內(nèi)積運(yùn)算o(2n)2m+ 2矢量運(yùn)算。()4m+ 1從表2-2可以看出，SpMV和預(yù)條件子方程組的求解占PCG算法的絕大部分時間。如 果k/?)次核函數(shù)，對應(yīng)的執(zhí)行時間為：7；和號，定義核函數(shù)的平均執(zhí) 行時間為：丁二億一功/(a一”)。3.1.4并行優(yōu)化性能模型的構(gòu)建給定塊內(nèi)線程數(shù)小、任意矢量大小，計(jì)算出ne = nntx Dx,泌=

54、/(ex小)。 當(dāng)塊內(nèi)線程數(shù)小一定時，同一個測試域里的矢量集對應(yīng)的再值總是相同的，這意味著在 同一個測試域中它們使用的是同一個核函數(shù)。通過實(shí)驗(yàn)發(fā)現(xiàn)，在一個測試域中，當(dāng)塊內(nèi)線程數(shù)小一定時，矢量大小跟核函數(shù)執(zhí)行 時間存在一種線性關(guān)系，即：(3-1)其中，nr = 128, 256, . , Bf,，表示第，個測試域。例如：基于NVIDIA K40c,在測試域（128x3x65535, 128x4x65535上，取小的值為：128, 256, 512, 1024,得到矢量大小和核函數(shù)執(zhí)行時間的線性關(guān)系曲線，如圖3-1所示 （x軸表示矢量尺寸，縮小了 10倍；y軸表示核函數(shù)的執(zhí)行時間）。xxXX圖3-

55、1矢量運(yùn)算關(guān)系曲線3.1.5生成決策樹通過建立上面的并行優(yōu)化性能模型，最終可以生成決策樹。通過構(gòu)建的決策樹， 任給一個矢量尺寸，決策樹都能夠達(dá)到自動、快速、準(zhǔn)確地找到最優(yōu)核函數(shù)以及運(yùn)行 時對應(yīng)的參數(shù)配置。具體決策樹生成算法如下所示。算法3-1矢量運(yùn)算決策樹生成算法遍歷實(shí)驗(yàn)設(shè)置中的每個測試域（由,川（，=1,2.），執(zhí)行以下操作:a）通過公式（3-1）擬合出每個測試域的線性直線，求出任何兩條直線之間的 交點(diǎn)，并把交點(diǎn)保存在集合S中。b）如果5 = 0或者S集合中只有一個元素：為或者dj+i ,那么在測試 域中，最佳的塊內(nèi)線程數(shù)燈可以通過計(jì)算argmin”,7；巖 獲得，其結(jié)果保存在 集合 P =

56、邑,dj+nt, nej 中。否則，把為和d州加入到S集合中，將S中的元素進(jìn)行升序排序，對于每個 域(，必+1，(&e S , A = l,2,.,|s| , S S2 .七)，通過計(jì)算 argmin*；獲 得最佳的塊內(nèi)線程數(shù)其結(jié)果保存在集合P = sk, s,+t, nt, ne中。輸出集合P,即生成的決策樹。例如，基于NVIDIA Tesla K40c,生成矢量運(yùn)算的決策樹如圖3-2所示。圖3-2矢量運(yùn)算決策樹3.2矢量內(nèi)積的并行優(yōu)化性能模型矢量內(nèi)積運(yùn)算跟矢量運(yùn)算不同之處在于它包含歸約操作。因此，我們單獨(dú)對它進(jìn)行了 研究，并提出一種基于profile的矢量內(nèi)積并行優(yōu)化性能模型，如圖2-5的

57、線路b所示。它 主要包括：獲取GPU特性、核模型、實(shí)驗(yàn)設(shè)置、并行優(yōu)化性能模型的構(gòu)建和生成決策樹 這幾個步驟。通過構(gòu)建的決策樹，給定任意大小的矢量，決策樹能夠自動、快速幫你配置 參數(shù)，使得程序性能達(dá)到最優(yōu)。3.2.1獲取GPU特性對于矢量內(nèi)積運(yùn)算，需要獲取線程塊內(nèi)最大的線程數(shù)？，GPU全局內(nèi)存最大字節(jié)數(shù) G,網(wǎng)格X維度上最大的線程塊數(shù)GPU流處理器個數(shù)Nsm,流處理器中32位寄存 器的最大個數(shù)Neg ,流處理器最大共享內(nèi)存字節(jié)數(shù)Nmem ,流處理器最多線程塊數(shù)N以及 流處理器允許最多線程數(shù)N等參數(shù)值。3.2.2核模型核模型里包含著不同運(yùn)算的核函數(shù)。對于矢量內(nèi)積，本論文使用的是Gao等in論文里

58、的矢量內(nèi)積核函數(shù)。3.2.3實(shí)驗(yàn)設(shè)置實(shí)驗(yàn)設(shè)置主要的任務(wù)是找出所有可能的塊內(nèi)線程數(shù)力和構(gòu)建benchmark矢量集。矢 量內(nèi)積運(yùn)算的實(shí)驗(yàn)設(shè)置跟矢量運(yùn)算相似，這里只作簡單介紹，具體可參考矢量運(yùn)算的實(shí)驗(yàn) 設(shè)置。塊內(nèi)線程數(shù)小= 128, 256, 512, . , BL測試域設(shè)置為(1024,102400, (102400,1024x1024, (1024x1024,128x0,(128x0、,2x128x0,. ,(Bf xDAniax,其中，Nmx =Gm/(3x sizeof (double) o當(dāng)混一定時，在一個測試域的ne = n/(ntxDx)總是相同的。如果對某個測試域取若干 個值作為矢

59、量尺寸，分別進(jìn)行賦值操作，便形成一個benchmark矢量集。benchmark矢量中元素的值不會影響到矢量內(nèi)積并行優(yōu)化性能模型的性能，可以 根據(jù)均勻分布U0.5,1.5隨機(jī)產(chǎn)生。3.2.4井行優(yōu)化性能模型的構(gòu)建由于內(nèi)積核函數(shù)包含歸約操作，核函數(shù)運(yùn)行結(jié)束后會產(chǎn)生泌個局部歸約結(jié)果(partial result),需要把泌個局部歸約結(jié)果傳到CPU主機(jī)端進(jìn)行二次歸約操作。由于數(shù)據(jù)通過PCI 插槽傳輸?shù)紺PU的代價是非常昂貴的，所以線程塊數(shù)泌不能設(shè)置的太大。但是另一方面, 在CUDA程序中，線程塊數(shù)渺值越大，意味著程序并行化能力越強(qiáng)。所以必須要對展的取值進(jìn)行衡量，定義網(wǎng)格的最小線程塊數(shù)油混為：NBnt

60、 = Nsm x min(Nreg/N；e8, Nmem/N,；,em, Ntd/nt, Nrb)(3-2)其中，N筍表示每個線程塊需要的寄存器數(shù)量，NU表示每個線程塊需要的共享內(nèi)存 字節(jié)數(shù)。實(shí)驗(yàn)數(shù)據(jù)表明，當(dāng)塊內(nèi)線程數(shù)小一定，取線程塊數(shù)nb = NBlt時，核函數(shù)性能不一定是 最優(yōu)的。為了使最小線程塊數(shù)NBf的使用有更好的魯棒性，定義線程塊數(shù) nb = NBntxi, 1 = 1,2,.,20,用戶可以自己選擇，的取值。通過實(shí)驗(yàn)發(fā)現(xiàn)：當(dāng)位和泌一定時，在測試域中矢量大小跟核函數(shù)的執(zhí)行時間存在著 一種線性關(guān)系：T：b,j = K,j ()(3-3)其中，nt = 128, 256, . , BT,