面向異構體系結構的稀疏矩陣算法研究.pdf

1、面向異構體系結構的稀疏矩陣算法已經成為高性能計算領域的關鍵問題之一。稀疏矩陣算法是自然科學和社會科學中許多領域進行數(shù)值模擬計算時的關鍵技術和性能瓶頸，為了提高稀疏矩陣算法的計算性能，需要提高相應算法在特定平臺上的計算效率。然而，一方面，稀疏矩陣算法的計算與訪存行為與矩陣的稀疏結構相關，是典型的不規(guī)則類算法，很難發(fā)掘時間與空間的局部性；另一方面，隨著包含算法加速器的異構并行體系結構成為高性能計算機體系結構的主流，并行程序執(zhí)行效率的影響因素

2、日益復雜多樣，傳統(tǒng)的面向具體平臺的程序并行與優(yōu)化方法已經無法滿足高效率并行程序的開發(fā)需求。本研究主要內容包括：
　?、盘岢隽嗣嫦駽PU-GPU異構平臺的搜索方向優(yōu)化的寬度優(yōu)先搜索算法。實現(xiàn)了基于GPU的自底向上的寬度優(yōu)先搜索算法，提高了GPU線程訪存的連續(xù)性并降低了線程間負載的不均衡，并進一步實現(xiàn)了CPU-GPU協(xié)同的自底向上的寬度優(yōu)先搜索算法，充分利用了CPU-GPU異構并行計算平臺上所有的計算資源，并有效提高了寬度優(yōu)先搜索算法

3、對大規(guī)模節(jié)點前沿的處理速度。在此基礎上，設計了面向CPU-GPU異構體系結構的優(yōu)化搜索方向的寬度優(yōu)先搜索算法，通過結合基于多核CPU的自頂向下的串行寬度優(yōu)先搜索算法、自頂向下的并行寬度優(yōu)先搜索算法以及CPU-GPU協(xié)同的自底向上的寬度優(yōu)先搜索算法，提高了寬度優(yōu)先搜索算法對不同規(guī)模節(jié)點前沿的適應性。
　　⑵提出了面向CPU-GPU異構平臺的稀疏矩陣向量乘算法。提出了基于索引信息壓縮的稀疏矩陣分塊存儲數(shù)據(jù)結構，通過合并位置相近的同行非

4、零元，減少了矩陣非零元素對應的索引信息的數(shù)據(jù)量，從而一方面提高了稀疏矩陣訪存的規(guī)則性和局部性，另一方面控制了填零元所引入的額外的計算和訪存開銷，并通過采用二級混合存儲數(shù)據(jù)結構提高了對于矩陣不同稀疏結構的適應性。在此基礎上，實現(xiàn)了基于計算訪存量的負載均衡算法，分別設計了針對多核CPU和GPU的優(yōu)化的SpMV算法，有效的提高了稀疏矩陣向量乘算法的計算效率，并進一步實現(xiàn)了CPU-GPU協(xié)同的稀疏矩陣向量乘算法，充分發(fā)掘了異構體系結構計算平臺的

5、計算能力。
　?、翘岢隽嗣嫦虍悩嬈脚_的基于超節(jié)點數(shù)據(jù)結構的稀疏矩陣分解算法。以稀疏矩陣Cholesky分解算法為研究對象，在數(shù)據(jù)組織方面，改進了稀疏矩陣超節(jié)點數(shù)據(jù)結構，通過超節(jié)點合并和分塊控制計算粒度；在計算調度方面，將分解過程映射為一系列的數(shù)據(jù)塊任務，并設計了相應的任務生成與調度算法，在滿足數(shù)據(jù)依賴性的前提下提高任務的并行性，從而顯著提高了稀疏矩陣Cholesky分解算法在GPU上的實現(xiàn)效率。通過將控制任務和計算任務分別映射到C

6、PU和GPU上，有效提高了CPU-GPU異構平臺上稀疏矩陣分解算法的計算性能。
　?、忍岢隽嗣嫦駽PU-GPU異構平臺的稀疏三角方程組求解算法。提出了面向稀疏結構的分塊處理策略，根據(jù)稀疏三角矩陣非零元密度的不同將計算過程分解，并設計了基于分塊數(shù)據(jù)結構的稀疏三角方程組求解算法。在此基礎上，設計了面向負載均衡的線程映射算法，并針對GPU設計了基于線程warp的計算組織策略，降低了GPU線程的控制分支所造成的性能損失，并進一步實現(xiàn)了CP