基于GPU平臺的KLU并行算法的研究-對角線塊的LU分解.pdf

1、隨著電子科學(xué)技術(shù)的發(fā)展,為設(shè)計高質(zhì)量的電路,電路模擬必不可少。在電路模擬的過程中要涉及到稀疏線性方程組的求解。而隨著電路矩陣規(guī)模的不斷增大,對電路矩陣的求解已經(jīng)成為電路模擬過程的一個瓶頸。針對電路模擬過程中產(chǎn)生的電路矩陣的特點,通常均采用直接法來進行此類線性方程組的求解。目前常用的求解器有sparsel-3、superLU、KLU,其中以Timothy Davis教授開發(fā)的KLU最為有效率。
　　 KLU主要由預(yù)處理,首次LU分

2、解,再分解和回代求解這幾個部分組成。再分解部分是算法的重要組成部分。在一次電路模擬過程中,就是通過多次調(diào)用該部分來完成對稀疏矩陣的數(shù)值LU分解。因此,本文主要對這部分的算法進行了并行研究和探索,并提出了基于GPU平臺的可行的并行算法。
　　 KLU算法在LU分解過程中,采用的算法是基于高斯消去法的Gilbert-Peierls算法。我們通過研究串行算法和程序提出了兩種不同的并行設(shè)想,并在GPU平臺上設(shè)計和實現(xiàn)了四種不同的并行算法

3、P_Llen算法、P_Ulen算法、P_nk算法和P_stream算法。我們在實驗平臺Ⅰ上對這四種并行算法進行了性能測試和分析,通過分析我們發(fā)現(xiàn)P_stream算法較前三種并行算法在性能上有較大的優(yōu)勢,但由于該并行算法受限于實驗平臺Ⅰ中GPU顯存的限制,導(dǎo)致并行度較低,性能較串行算法有所下降。為提高P_stream算法的并行度,我們在GPU顯存容量更大的實驗平臺Ⅱ上對其進行了性能的測試和分析。通過分析,我們發(fā)現(xiàn)隨著并行度的提高,P_st