面向異構(gòu)體系結(jié)構(gòu)的稀疏矩陣算法研究.pdf

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

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

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

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

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

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