大規(guī)模稀疏矩陣并行計算課件

大規(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矩陣性質(zhì)對求解的影響性質(zhì)影響7/21/2024大規(guī)模稀疏矩陣并行計算3非零元的分布o帶狀分布o按塊分布o正定性對稱性矩陣的存儲方式求解方法的選擇求解速度矩陣性質(zhì)對求解的影響性質(zhì)影響8/15/2023大規(guī)模稀疏矩陣直接法矩陣圖重排：一般分為兩大類，帶寬縮減算法（也常稱為外形縮減）和區(qū)域分解算法，應用較多的帶寬縮減算法CM，RCM，GPS，Rosen算法。一般建議多重方法結(jié)合使用：全局方法的全局平衡性、局部方法的局部最優(yōu)特性。符號分解：確定非零元結(jié)構(gòu)以及相應的消元索引，以便在實際數(shù)值分解前確定所需存儲資源大小，避免數(shù)值分解中動態(tài)分配存儲空間和復雜的索引策略。構(gòu)建消去樹(elimination tree)：確定分解節(jié)點之間的分解依賴，即確定分解的順序并構(gòu)成并行分解的層次結(jié)構(gòu)。7/21/2024大規(guī)模稀疏矩陣并行計算4直接法8/15/2023大規(guī)模稀疏矩陣并行計算4直接法數(shù)值分解：利用符號分解得到的非零元結(jié)構(gòu)和索引沿消去樹路徑進行分解?；卮蠼猓喊ㄇ跋颍╢orward）和后向（backward）回代，可先構(gòu)建消去依賴樹或頂點著色技術實現(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-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é)合）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大規(guī)模稀疏矩陣并行計算10代數(shù)多重網(wǎng)格法8/15/2023大規(guī)模稀疏矩陣并行計算10代數(shù)多重網(wǎng)格法方法選擇對于非結(jié)構(gòu)化網(wǎng)格形成的矩陣，SGS，SSOR方法不易并行，即使使用頂點著色技術，因其粗粒度的并行更適合于傳統(tǒng)的多核處理器，并不非常適合GPU這樣的細粒度并行的架構(gòu)。Jacobi方法不具有低通濾波性，因此推薦使用damp-Jacobi和PCG方法作為迭代子，其中damp-Jacobi方法的權(quán)值一般取為2/3。在最粗網(wǎng)格上的計算推薦使用直接解法。通常對于二階橢圓邊值問題，幾何多重網(wǎng)格法具有更好的計算效率以及收斂速度。7/21/2024大規(guī)模稀疏矩陣并行計算11代數(shù)多重網(wǎng)格法方法選擇8/15/2023大規(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)格不適用于所有問題。需要高質(zhì)量的網(wǎng)格劃分。不便于編寫通用的程序。重點要解決的問題：網(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)化設計探索內(nèi)核執(zhí)行的優(yōu)化o在大循環(huán)中具有大量入口參數(shù)的內(nèi)核，其不變的參數(shù)在循環(huán)開始前放入常量內(nèi)存。避免多余的內(nèi)存操作o合理的網(wǎng)格布局。o有時將一個大grid拆分成多個階段小的grid將有助于提高網(wǎng)格利用率，提高計算效率，例如對稱矩陣的分解以及三角方程組的計算。寄存器優(yōu)化o一個線程中計算輸出多個變量，用寄存器內(nèi)存替換共享內(nèi)存。o在Fermi上，如果程序中存取操作占多數(shù)，則對于大于32bit的數(shù)據(jù)，以字節(jié)流的形式訪問，因為對于例如雙精度數(shù)據(jù)，這時只有一個warp調(diào)度器可以工作。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對齊。例如：每個線程計算輸出7個變量，每個變量的計算差別很大。這時可以讓block的第一個warp的所有線程計算第一個變量，第二個warp計算第二個變量，可以利用函數(shù)指針（在計算能力=1.3的硬件上可以使用對齊到warp邊界的控制語句，這時并不會在warp內(nèi)造成路徑分支（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）格式代替例如，float4可使用xxxx yyyy zzzz wwww的存儲結(jié)構(gòu)代替，一般更有效。在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ù)結(jié)構(gòu)應該和網(wǎng)格布局相互適應來有效利用存儲控制器的帶寬。例如矩陣的轉(zhuǎn)置。7/21/2024大規(guī)模稀疏矩陣并行計算20大規(guī)模稀疏矩陣GPU計算程序優(yōu)化設計探索8/15/2023大謝謝！7/21/202421大規(guī)模稀疏矩陣并行計算謝謝！8/15/202321大規(guī)模稀疏矩陣并行計算