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