GPU并行的大規(guī)模稀疏近似逆預(yù)條件算法研究.pdf

1、稀疏近似逆預(yù)條件子應(yīng)用到迭代法中已證明其有效性。然而，獲得這些預(yù)條件子的計算復(fù)雜度往往較高，面對大規(guī)模問題時顯得力不從心，需要加速。近些年來，隨著高計算能力的圖形處理器(graphics processor unit,GPU)的興起，用于大規(guī)模問題的GPU加速的并行稀疏近似逆預(yù)條件子已引起廣泛的關(guān)注。因此，本文針對共軛梯度(conjugate gradient，CG)算法，基于對稱超松弛(symmetric successive ove

2、r-relaxation,SSOR)預(yù)條件子和一種近似逆(approximate inverse,AINV)算法，研究構(gòu)造GPU架構(gòu)下高效并行的稀疏近似逆預(yù)條件子。
　　本文所做的工作和貢獻(xiàn)如下：
　　1.由于SSOR預(yù)條件共軛梯度算法中預(yù)條件方程求解需要強(qiáng)串行的前推和回代，導(dǎo)致算法遷移到GPU平臺上并行效率不高。為此，基于諾依曼(Neumann)多項(xiàng)式分解技術(shù)，提出了一種GPU加速的SSOR稀疏近似逆預(yù)條件子(GSSORS

3、AI)。它不僅保持了原線性系統(tǒng)系數(shù)矩陣的稀疏和對稱正定特性，而且預(yù)條件方程求解僅需一次稀疏矩陣矢量乘運(yùn)算，避免了前推和回代過程。實(shí)驗(yàn)結(jié)果表明，在NVIDIA Tesla C2050 GPU上，對比使用Python在單個CPU上SSOR稀疏近似逆預(yù)條件子實(shí)現(xiàn)方法，GSSORSAI平均快將近100倍；應(yīng)用到并行的PCG算法中，相比無預(yù)條件的CG算法，平均提高了3倍的收斂速度。
　　2.由于SSOR稀疏近似逆預(yù)條件子需要對稱正定線性系統(tǒng)

4、的系數(shù)矩陣A滿足P(-D-1L)<1，所以接著針對一般性的對稱正定矩陣A，基于AINV算法，利用圖劃分技術(shù)對原始矩陣A做分塊，通過對子圖做內(nèi)點(diǎn)和邊界點(diǎn)的區(qū)分，以及稀疏矩陣的置換技術(shù)，將矩陣A的稀疏近似逆轉(zhuǎn)換成分塊箭型矩陣的稀疏近似逆。進(jìn)而，利用GPU的多支流處理器，改進(jìn)了稀疏矩陣乘ESC算法，實(shí)現(xiàn)了一種高效并行的稀疏AINV預(yù)條件子。實(shí)驗(yàn)證明，基于GPU的AINV稀疏預(yù)條件子高度并行，并且應(yīng)用到PCG（preconditioned co