基于GPU平臺(tái)的KLU并行算法的研究-對(duì)角線塊的LU分解.pdf

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

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

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