《大規(guī)模稀疏矩陣并行計(jì)算課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《大規(guī)模稀疏矩陣并行計(jì)算課件（21頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、大規(guī)模稀疏矩陣并行計(jì)算李修宇QQ：2955533817/21/20241大規(guī)模稀疏矩陣并行計(jì)算李修宇8/15/20231主流求解方法直接法oGAUSS消去法o波前法o多波前法迭代法o經(jīng)典迭代法Jacobi、SOR、SSORo投影方法CG、GMRESo預(yù)處理技術(shù)不完全分解預(yù)處理?xiàng)l件o代數(shù)多重網(wǎng)格技術(shù)7/21/2024大規(guī)模稀疏矩陣并行計(jì)算2主流求解方法8/15/2023大規(guī)模稀疏矩陣并行計(jì)算2矩陣性質(zhì)對(duì)求解的影響性質(zhì)影響7/21/2024大規(guī)模稀疏矩陣并行計(jì)算3非零元的分布o(jì)帶狀分布o(jì)按塊分布o(jì)正定性對(duì)稱性矩陣的存儲(chǔ)方式求解方法的選擇求解速度矩陣性質(zhì)對(duì)求解的影響性質(zhì)影響8/15/2023大規(guī)模稀

2、疏矩陣直接法矩陣圖重排：一般分為兩大類，帶寬縮減算法（也常稱為外形縮減）和區(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)之間的分解依賴，即確定分解的順序并構(gòu)成并行分解的層次結(jié)構(gòu)。7/21/2024大規(guī)模稀疏矩陣并行計(jì)算4直接法8/15/2023大規(guī)模稀疏矩陣并行計(jì)算4直接法數(shù)值分解：利用符號(hào)分解得到的非零

3、元結(jié)構(gòu)和索引沿消去樹(shù)路徑進(jìn)行分解?；卮蠼猓喊ㄇ跋颍╢orward）和后向（backward）回代，可先構(gòu)建消去依賴樹(shù)或頂點(diǎn)著色技術(shù)實(shí)現(xiàn)并行回代求解。在有限元領(lǐng)域應(yīng)用最廣的直接求解方法常使用帶寬縮減或多區(qū)域分解的多波前法（multifrontal）。7/21/2024大規(guī)模稀疏矩陣并行計(jì)算5直接法8/15/2023大規(guī)模稀疏矩陣并行計(jì)算5對(duì)稱正定矩陣的求解7/21/2024大規(guī)模稀疏矩陣并行計(jì)算6對(duì)稱正定矩陣的求解8/15/2023大規(guī)模稀疏矩陣并行計(jì)算對(duì)稱矩陣的不完全分解7/21/2024大規(guī)模稀疏矩陣并行計(jì)算7對(duì)稱矩陣的不完全分解8/15/2023大規(guī)模稀疏矩陣并行計(jì)代數(shù)多重網(wǎng)格法V-C

4、ycle 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é)合）7/21/2024大規(guī)模稀疏矩陣并行計(jì)算8代數(shù)多重網(wǎng)格法8/15/2023大規(guī)模稀疏矩陣并行計(jì)算8代數(shù)多重網(wǎng)格法7/21/2024大規(guī)模稀疏矩陣并行計(jì)算9代數(shù)多重網(wǎng)格法8/15/2023大規(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），類似于前光滑。7/21/2024大

5、規(guī)模稀疏矩陣并行計(jì)算10代數(shù)多重網(wǎng)格法8/15/2023大規(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ì)算效率以及收斂速度。7/21/2024大規(guī)模稀疏矩陣并行計(jì)算11代數(shù)多重網(wǎng)格法方法選擇8/15/20

6、23大規(guī)模稀疏矩陣并行計(jì)代數(shù)多重網(wǎng)格法方法選擇一般遵循兩個(gè)原則：o對(duì)于某個(gè)頂點(diǎn)，其鄰接頂點(diǎn)要么屬于粗網(wǎng)格頂點(diǎn)，要么至少連接到一個(gè)粗網(wǎng)格頂點(diǎn)。o粗網(wǎng)格頂點(diǎn)集應(yīng)是任意兩個(gè)粗網(wǎng)格節(jié)點(diǎn)不相鄰的極大獨(dú)立集。有時(shí)很難同時(shí)滿足兩個(gè)條件，優(yōu)先滿足第一個(gè)條件時(shí)盡量滿足第二個(gè)條件。7/21/2024大規(guī)模稀疏矩陣并行計(jì)算12代數(shù)多重網(wǎng)格法方法選擇8/15/2023大規(guī)模稀疏矩陣并行計(jì)代數(shù)多重網(wǎng)格法方法選擇7/21/2024大規(guī)模稀疏矩陣并行計(jì)算13代數(shù)多重網(wǎng)格法方法選擇8/15/2023大規(guī)模稀疏矩陣并行代數(shù)多重網(wǎng)格法的局限性任意幾何網(wǎng)格不適用于所有問(wèn)題。需要高質(zhì)量的網(wǎng)格劃分。不便于編寫通用的程序。重點(diǎn)要解決的問(wèn)

7、題：網(wǎng)格粗化（對(duì)應(yīng)于粗水平方程組）。常用的網(wǎng)格粗化方法復(fù)雜：RS，RS2，RS3，F(xiàn)algout，HIPS，CLJP。7/21/2024大規(guī)模稀疏矩陣并行計(jì)算14代數(shù)多重網(wǎng)格法的局限性8/15/2023大規(guī)模稀疏矩陣并行計(jì)大規(guī)模稀疏矩陣GPU計(jì)算程序優(yōu)化設(shè)計(jì)探索內(nèi)核執(zhí)行的優(yōu)化o在大循環(huán)中具有大量入口參數(shù)的內(nèi)核，其不變的參數(shù)在循環(huán)開(kāi)始前放入常量?jī)?nèi)存。避免多余的內(nèi)存操作o合理的網(wǎng)格布局。o有時(shí)將一個(gè)大grid拆分成多個(gè)階段小的grid將有助于提高網(wǎng)格利用率，提高計(jì)算效率，例如對(duì)稱矩陣的分解以及三角方程組的計(jì)算。寄存器優(yōu)化o一個(gè)線程中計(jì)算輸出多個(gè)變量，用寄存器內(nèi)存替換共享內(nèi)存。o在Fermi上，如果

8、程序中存取操作占多數(shù)，則對(duì)于大于32bit的數(shù)據(jù)，以字節(jié)流的形式訪問(wèn)，因?yàn)閷?duì)于例如雙精度數(shù)據(jù)，這時(shí)只有一個(gè)warp調(diào)度器可以工作。7/21/2024大規(guī)模稀疏矩陣并行計(jì)算15大規(guī)模稀疏矩陣GPU計(jì)算程序優(yōu)化設(shè)計(jì)探索8/15/2023大大規(guī)模稀疏矩陣GPU計(jì)算程序優(yōu)化設(shè)計(jì)探索合并訪問(wèn)存取操作以half-warp（計(jì)算能力b)a=c;else a=0;可以替換為：a=(ab)*c;7/21/2024大規(guī)模稀疏矩陣并行計(jì)算17大規(guī)模稀疏矩陣GPU計(jì)算程序優(yōu)化設(shè)計(jì)探索8/15/2023大大規(guī)模稀疏矩陣GPU計(jì)算程序優(yōu)化設(shè)計(jì)探索指令按照half-warp（計(jì)算能力=1.3）或者warp對(duì)齊。例如：每個(gè)線

9、程計(jì)算輸出7個(gè)變量，每個(gè)變量的計(jì)算差別很大。這時(shí)可以讓block的第一個(gè)warp的所有線程計(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ì)降低效率。7/21/2024Footer Text18大規(guī)模稀疏矩陣GPU計(jì)算程序優(yōu)化設(shè)計(jì)探索8/15/2023F大規(guī)模稀疏矩陣GPU計(jì)算程序優(yōu)化設(shè)計(jì)探索對(duì)于矢量類型數(shù)據(jù)，使用SOA（Structure of Array）格式代替例如，f

10、loat4可使用xxxx yyyy zzzz wwww的存儲(chǔ)結(jié)構(gòu)代替，一般更有效。在Fermi硬件上，讀float4類型的數(shù)據(jù)，雖然顯存帶寬可以被充分利用，但是會(huì)有部分CUDA Core暫時(shí)閑置，并且必須等待兩次的存儲(chǔ)請(qǐng)求完成才開(kāi)始計(jì)算，而如果使用SOA，則在其后的各分量獨(dú)立的計(jì)算中可以更有效隱藏延遲。7/21/2024大規(guī)模稀疏矩陣并行計(jì)算19大規(guī)模稀疏矩陣GPU計(jì)算程序優(yōu)化設(shè)計(jì)探索8/15/2023大大規(guī)模稀疏矩陣GPU計(jì)算程序優(yōu)化設(shè)計(jì)探索如果按照顯式的warp模式進(jìn)行操作，則盡量將每個(gè)warp對(duì)應(yīng)操作的存儲(chǔ)器起始地址對(duì)齊。如果每個(gè)warp的活動(dòng)線程數(shù)小于75%左右時(shí)，則不建議使用。數(shù)據(jù)結(jié)構(gòu)應(yīng)該和網(wǎng)格布局相互適應(yīng)來(lái)有效利用存儲(chǔ)控制器的帶寬。例如矩陣的轉(zhuǎn)置。7/21/2024大規(guī)模稀疏矩陣并行計(jì)算20大規(guī)模稀疏矩陣GPU計(jì)算程序優(yōu)化設(shè)計(jì)探索8/15/2023大謝謝！7/21/202421大規(guī)模稀疏矩陣并行計(jì)算謝謝！8/15/202321大規(guī)模稀疏矩陣并行計(jì)算