大規(guī)模稀疏矩陣并行計(jì)算

單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,Footer Text,*,大規(guī)模稀疏矩陣并行計(jì)算,李修宇,QQ,：,295553381,10/28/2024,1,主流求解方法,直接法,GAUSS,消去法,波前法,多波前法,迭代法,經(jīng)典迭代法,Jacobi,、,SOR,、,SSOR,投影方法,CG,、,GMRES,預(yù)處理技術(shù),不完全分解預(yù)處理?xiàng)l件,代數(shù)多重網(wǎng)格技術(shù),10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,2,矩陣性質(zhì)對(duì)求解的影響,性質(zhì),影響,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,3,非零元的分布,帶狀分布,按塊分布,正定性,對(duì)稱(chēng)性,矩陣的存儲(chǔ)方式,求解方法的選擇,求解速度,直接法,矩陣圖重排：一般分為兩大類(lèi)，帶寬縮減算法（也常稱(chēng)為外形縮減）和區(qū)域分解算法，應(yīng)用較多的帶寬縮減算法,CM,，,RCM,，,GPS,，,Rosen,算法。一般建議多重方法結(jié)合使用：全局方法的全局平衡性、局部方法的局部最優(yōu)特性。,符號(hào)分解：確定非零元結(jié)構(gòu)以及相應(yīng)的消元索引，以便在實(shí)際數(shù)值分解前確定所需存儲(chǔ)資源大小，避免數(shù)值分解中動(dòng)態(tài)分配存儲(chǔ)空間和復(fù)雜的索引策略。,構(gòu)建消去樹(shù),(elimination tree),：確定分解節(jié)點(diǎn)之間的分解依賴(lài)，即確定分解的順序并構(gòu)成并行分解的層次結(jié)構(gòu)。,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,4,直接法,數(shù)值分解：利用符號(hào)分解得到的非零元結(jié)構(gòu)和索引沿消去樹(shù)路徑進(jìn)行分解。,回代求解：包括前向（,forward,）和后向（,backward,）回代，可先構(gòu)建消去依賴(lài)樹(shù)或頂點(diǎn)著色技術(shù)實(shí)現(xiàn)并行回代求解。,在有限元領(lǐng)域應(yīng)用最廣的直接求解方法常使用帶寬縮減或多區(qū)域分解的多波前法（,multifrontal,）。,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,5,對(duì)稱(chēng)正定矩陣的求解,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,6,對(duì)稱(chēng)矩陣的不完全分解,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,7,代數(shù)多重網(wǎng)格法,V-Cycle AMG,（,V,循環(huán)多重網(wǎng)格法）,W-Cycle AMG,（,W,循環(huán)多重網(wǎng)格法）,FMG,（完全多重網(wǎng)格法：嵌套網(wǎng)格與,V,循環(huán)或者,W,循環(huán)結(jié)合）,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,8,代數(shù)多重網(wǎng)格法,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,9,代數(shù)多重網(wǎng)格法,在粗網(wǎng)格上對(duì)殘差方程進(jìn)行求解（可用迭代法或直接解法）。,延拓或插值（,interpolation,）：將細(xì)網(wǎng)格節(jié)點(diǎn)上的值通過(guò)分片插值延拓到細(xì)網(wǎng)格節(jié)點(diǎn)上。,通過(guò)光滑的殘差對(duì)解進(jìn)行修正。,后光滑（,post-smooth,），類(lèi)似于前光滑。,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,10,代數(shù)多重網(wǎng)格法方法選擇,對(duì)于非結(jié)構(gòu)化網(wǎng)格形成的矩陣，,SGS,，,SSOR,方法不易并行，即使使用頂點(diǎn)著色技術(shù)，因其粗粒度的并行更適合于傳統(tǒng)的多核處理器，并不非常適合,GPU,這樣的細(xì)粒度并行的架構(gòu)。,Jacobi,方法不具有低通濾波性，因此推薦使用,damp-Jacobi,和,PCG,方法作為迭代子，其中,damp-Jacobi,方法的權(quán)值一般取為,2/3,。,在最粗網(wǎng)格上的計(jì)算推薦使用直接解法。,通常對(duì)于二階橢圓邊值問(wèn)題，幾何多重網(wǎng)格法具有更好的計(jì)算效率以及收斂速度。,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,11,代數(shù)多重網(wǎng)格法方法選擇,一般遵循兩個(gè)原則：,對(duì)于某個(gè)頂點(diǎn)，其鄰接頂點(diǎn)要么屬于粗網(wǎng)格頂點(diǎn)，要么至少連接到一個(gè)粗網(wǎng)格頂點(diǎn)。,粗網(wǎng)格頂點(diǎn)集應(yīng)是任意兩個(gè)粗網(wǎng)格節(jié)點(diǎn)不相鄰的極大獨(dú)立集。,有時(shí)很難同時(shí)滿(mǎn)足兩個(gè)條件，優(yōu)先滿(mǎn)足第一個(gè)條件時(shí)盡量滿(mǎn)足第二個(gè)條件。,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,12,代數(shù)多重網(wǎng)格法方法選擇,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,13,代數(shù)多重網(wǎng)格法的局限性,任意幾何網(wǎng)格不適用于所有問(wèn)題。,需要高質(zhì)量的網(wǎng)格劃分。,不便于編寫(xiě)通用的程序。,重點(diǎn)要解決的問(wèn)題：網(wǎng)格粗化（對(duì)應(yīng)于粗水平方程組）。,常用的網(wǎng)格粗化方法復(fù)雜：,RS,，,RS2,，,RS3,，,Falgout,，,HIPS,，,CLJP,。,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,14,大規(guī)模稀疏矩陣,GPU,計(jì)算程序優(yōu)化設(shè)計(jì)探索,內(nèi)核執(zhí)行的優(yōu)化,在大循環(huán)中具有大量入口參數(shù)的內(nèi)核，其不變的參數(shù)在循環(huán)開(kāi)始前放入常量?jī)?nèi)存。避免多余的內(nèi)存操作,合理的網(wǎng)格布局。,有時(shí)將一個(gè)大,grid,拆分成多個(gè)階段小的,grid,將有助于提高網(wǎng)格利用率，提高計(jì)算效率，例如對(duì)稱(chēng)矩陣的分解以及三角方程組的計(jì)算。,寄存器優(yōu)化,一個(gè)線(xiàn)程中計(jì)算輸出多個(gè)變量，用寄存器內(nèi)存替換共享內(nèi)存。,在,Fermi,上，如果程序中存取操作占多數(shù)，則對(duì)于大于,32bit,的數(shù)據(jù)，以字節(jié)流的形式訪問(wèn)，因?yàn)閷?duì)于例如雙精度數(shù)據(jù)，這時(shí)只有一個(gè),warp,調(diào)度器可以工作。,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,15,大規(guī)模稀疏矩陣,GPU,計(jì)算程序優(yōu)化設(shè)計(jì)探索,合并訪問(wèn),存取操作以,half-warp,（計(jì)算能力,b),a=c;,else,a=0;,可以替換為：,a=(ab)*c;,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,17,大規(guī)模稀疏矩陣,GPU,計(jì)算程序優(yōu)化設(shè)計(jì)探索,指令按照,half-warp,（計(jì)算能力,=1.3,）或者,warp,對(duì)齊。例如：每個(gè)線(xiàn)程計(jì)算輸出,7,個(gè)變量，每個(gè)變量的計(jì)算差別很大。這時(shí)可以讓,block,的第一個(gè),warp,的所有線(xiàn)程計(jì)算第一個(gè)變量，第二個(gè),warp,計(jì)算第二個(gè)變量，,可以利用函數(shù)指針（在計(jì)算能力,=1.3,的硬件上可以使用對(duì)齊到,warp,邊界的控制語(yǔ)句，這時(shí)并不會(huì)在,warp,內(nèi)造成路徑分支（,uniform divergence,），通過(guò),warp,編號(hào)來(lái)選擇；但是對(duì)于相近的計(jì)算則不建議使用函數(shù)指針?lè)炊鴷?huì)降低效率。,10/28/2024,Footer Text,18,大規(guī)模稀疏矩陣,GPU,計(jì)算程序優(yōu)化設(shè)計(jì)探索,對(duì)于矢量類(lèi)型數(shù)據(jù)，使用,SOA,（,Structure of Array,）格式代替,例如，,float4,可使用,xxxx yyyy zzzz wwww,的存儲(chǔ)結(jié)構(gòu)代替，一般更有效。,在,Fermi,硬件上，讀,float4,類(lèi)型的數(shù)據(jù)，雖然顯存帶寬可以被充分利用，但是會(huì)有部分,CUDA Core,暫時(shí)閑置，并且必須等待兩次的存儲(chǔ)請(qǐng)求完成才開(kāi)始計(jì)算，而如果使用,SOA,，則在其后的各分量獨(dú)立的計(jì)算中可以更有效隱藏延遲。,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,19,大規(guī)模稀疏矩陣,GPU,計(jì)算程序優(yōu)化設(shè)計(jì)探索,如果按照顯式的,warp,模式進(jìn)行操作，則盡量將每個(gè),warp,對(duì)應(yīng)操作的存儲(chǔ)器起始地址對(duì)齊。如果每個(gè),warp,的活動(dòng)線(xiàn)程數(shù)小于,75%,左右時(shí)，則不建議使用。,數(shù)據(jù)結(jié)構(gòu)應(yīng)該和網(wǎng)格布局相互適應(yīng)來(lái)有效利用存儲(chǔ)控制器的帶寬。例如矩陣的轉(zhuǎn)置。,10/28/2024,大規(guī)模稀疏矩陣并行計(jì)算,20,謝謝！,10/28/2024,21,大規(guī)模稀疏矩陣并行計(jì)算,