《大規(guī)模稀疏矩陣并行計算》由會員分享，可在線閱讀，更多相關(guān)《大規(guī)模稀疏矩陣并行計算（21頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,Footer Text,*,大規(guī)模稀疏矩陣并行計算,李修宇,QQ,：,295553381,10/28/2024,1,主流求解方法,直接法,GAUSS,消去法,波前法,多波前法,迭代法,經(jīng)典迭代法,Jacobi,、,SOR,、,SSOR,投影方法,CG,、,GMRES,預(yù)處理技術(shù),不完全分解預(yù)處理條件,代數(shù)多重網(wǎng)格技術(shù),10/28/2024,大規(guī)模稀疏矩陣并行計算,2,矩陣性質(zhì)對求解的影響,性質(zhì),影響,10/28/2024,大規(guī)模稀疏矩陣并行計算,3,非零元的分布,帶狀分布,按塊分布,正定性,對稱性,矩陣的存

2、儲方式,求解方法的選擇,求解速度,直接法,矩陣圖重排：一般分為兩大類，帶寬縮減算法（也常稱為外形縮減）和區(qū)域分解算法，應(yīng)用較多的帶寬縮減算法,CM,，,RCM,，,GPS,，,Rosen,算法。一般建議多重方法結(jié)合使用：全局方法的全局平衡性、局部方法的局部最優(yōu)特性。,符號分解：確定非零元結(jié)構(gòu)以及相應(yīng)的消元索引，以便在實際數(shù)值分解前確定所需存儲資源大小，避免數(shù)值分解中動態(tài)分配存儲空間和復(fù)雜的索引策略。,構(gòu)建消去樹,(elimination tree),：確定分解節(jié)點之間的分解依賴，即確定分解的順序并構(gòu)成并行分解的層次結(jié)構(gòu)。,10/28/2024,大規(guī)模稀疏矩陣并行計算,4,直接法,數(shù)值分解：利用

3、符號分解得到的非零元結(jié)構(gòu)和索引沿消去樹路徑進行分解。,回代求解：包括前向（,forward,）和后向（,backward,）回代，可先構(gòu)建消去依賴樹或頂點著色技術(shù)實現(xiàn)并行回代求解。,在有限元領(lǐng)域應(yīng)用最廣的直接求解方法常使用帶寬縮減或多區(qū)域分解的多波前法（,multifrontal,）。,10/28/2024,大規(guī)模稀疏矩陣并行計算,5,對稱正定矩陣的求解,10/28/2024,大規(guī)模稀疏矩陣并行計算,6,對稱矩陣的不完全分解,10/28/2024,大規(guī)模稀疏矩陣并行計算,7,代數(shù)多重網(wǎng)格法,V-Cycle AMG,（,V,循環(huán)多重網(wǎng)格法）,W-Cycle AMG,（,W,循環(huán)多重網(wǎng)格法）,FM

4、G,（完全多重網(wǎng)格法：嵌套網(wǎng)格與,V,循環(huán)或者,W,循環(huán)結(jié)合）,10/28/2024,大規(guī)模稀疏矩陣并行計算,8,代數(shù)多重網(wǎng)格法,10/28/2024,大規(guī)模稀疏矩陣并行計算,9,代數(shù)多重網(wǎng)格法,在粗網(wǎng)格上對殘差方程進行求解（可用迭代法或直接解法）。,延拓或插值（,interpolation,）：將細網(wǎng)格節(jié)點上的值通過分片插值延拓到細網(wǎng)格節(jié)點上。,通過光滑的殘差對解進行修正。,后光滑（,post-smooth,），類似于前光滑。,10/28/2024,大規(guī)模稀疏矩陣并行計算,10,代數(shù)多重網(wǎng)格法方法選擇,對于非結(jié)構(gòu)化網(wǎng)格形成的矩陣，,SGS,，,SSOR,方法不易并行，即使使用頂點著色技術(shù)，因

5、其粗粒度的并行更適合于傳統(tǒng)的多核處理器，并不非常適合,GPU,這樣的細粒度并行的架構(gòu)。,Jacobi,方法不具有低通濾波性，因此推薦使用,damp-Jacobi,和,PCG,方法作為迭代子，其中,damp-Jacobi,方法的權(quán)值一般取為,2/3,。,在最粗網(wǎng)格上的計算推薦使用直接解法。,通常對于二階橢圓邊值問題，幾何多重網(wǎng)格法具有更好的計算效率以及收斂速度。,10/28/2024,大規(guī)模稀疏矩陣并行計算,11,代數(shù)多重網(wǎng)格法方法選擇,一般遵循兩個原則：,對于某個頂點，其鄰接頂點要么屬于粗網(wǎng)格頂點，要么至少連接到一個粗網(wǎng)格頂點。,粗網(wǎng)格頂點集應(yīng)是任意兩個粗網(wǎng)格節(jié)點不相鄰的極大獨立集。,有時很難

6、同時滿足兩個條件，優(yōu)先滿足第一個條件時盡量滿足第二個條件。,10/28/2024,大規(guī)模稀疏矩陣并行計算,12,代數(shù)多重網(wǎng)格法方法選擇,10/28/2024,大規(guī)模稀疏矩陣并行計算,13,代數(shù)多重網(wǎng)格法的局限性,任意幾何網(wǎng)格不適用于所有問題。,需要高質(zhì)量的網(wǎng)格劃分。,不便于編寫通用的程序。,重點要解決的問題：網(wǎng)格粗化（對應(yīng)于粗水平方程組）。,常用的網(wǎng)格粗化方法復(fù)雜：,RS,，,RS2,，,RS3,，,Falgout,，,HIPS,，,CLJP,。,10/28/2024,大規(guī)模稀疏矩陣并行計算,14,大規(guī)模稀疏矩陣,GPU,計算程序優(yōu)化設(shè)計探索,內(nèi)核執(zhí)行的優(yōu)化,在大循環(huán)中具有大量入口參數(shù)的內(nèi)核，

7、其不變的參數(shù)在循環(huán)開始前放入常量內(nèi)存。避免多余的內(nèi)存操作,合理的網(wǎng)格布局。,有時將一個大,grid,拆分成多個階段小的,grid,將有助于提高網(wǎng)格利用率，提高計算效率，例如對稱矩陣的分解以及三角方程組的計算。,寄存器優(yōu)化,一個線程中計算輸出多個變量，用寄存器內(nèi)存替換共享內(nèi)存。,在,Fermi,上，如果程序中存取操作占多數(shù)，則對于大于,32bit,的數(shù)據(jù)，以字節(jié)流的形式訪問，因為對于例如雙精度數(shù)據(jù)，這時只有一個,warp,調(diào)度器可以工作。,10/28/2024,大規(guī)模稀疏矩陣并行計算,15,大規(guī)模稀疏矩陣,GPU,計算程序優(yōu)化設(shè)計探索,合并訪問,存取操作以,half-warp,（計算能力,b),

8、a=c;,else,a=0;,可以替換為：,a=(ab)*c;,10/28/2024,大規(guī)模稀疏矩陣并行計算,17,大規(guī)模稀疏矩陣,GPU,計算程序優(yōu)化設(shè)計探索,指令按照,half-warp,（計算能力,=1.3,）或者,warp,對齊。例如：每個線程計算輸出,7,個變量，每個變量的計算差別很大。這時可以讓,block,的第一個,warp,的所有線程計算第一個變量，第二個,warp,計算第二個變量，,可以利用函數(shù)指針（在計算能力,=1.3,的硬件上可以使用對齊到,warp,邊界的控制語句，這時并不會在,warp,內(nèi)造成路徑分支（,uniform divergence,），通過,warp,編號來

9、選擇；但是對于相近的計算則不建議使用函數(shù)指針反而會降低效率。,10/28/2024,Footer Text,18,大規(guī)模稀疏矩陣,GPU,計算程序優(yōu)化設(shè)計探索,對于矢量類型數(shù)據(jù)，使用,SOA,（,Structure of Array,）格式代替,例如，,float4,可使用,xxxx yyyy zzzz wwww,的存儲結(jié)構(gòu)代替，一般更有效。,在,Fermi,硬件上，讀,float4,類型的數(shù)據(jù)，雖然顯存帶寬可以被充分利用，但是會有部分,CUDA Core,暫時閑置，并且必須等待兩次的存儲請求完成才開始計算，而如果使用,SOA,，則在其后的各分量獨立的計算中可以更有效隱藏延遲。,10/28/2024,大規(guī)模稀疏矩陣并行計算,19,大規(guī)模稀疏矩陣,GPU,計算程序優(yōu)化設(shè)計探索,如果按照顯式的,warp,模式進行操作，則盡量將每個,warp,對應(yīng)操作的存儲器起始地址對齊。如果每個,warp,的活動線程數(shù)小于,75%,左右時，則不建議使用。,數(shù)據(jù)結(jié)構(gòu)應(yīng)該和網(wǎng)格布局相互適應(yīng)來有效利用存儲控制器的帶寬。例如矩陣的轉(zhuǎn)置。,10/28/2024,大規(guī)模稀疏矩陣并行計算,20,謝謝！,10/28/2024,21,大規(guī)模稀疏矩陣并行計算,