基于GPU平臺(tái)的KLU并行算法的研究與實(shí)現(xiàn)-預(yù)處理及回代求解.pdf

1、在大型電路模擬中,Ax=b形式的線性方程組的求解是影響電路模擬效率的關(guān)鍵問題。為了解決這一問題,目前已經(jīng)存在許多針對大型電路模擬矩陣的求解器,例如sparce1.3、superLU、KLU等。實(shí)驗(yàn)表明,與其他算法相比,KLU算法效率更高、更適合于處理大型電路模擬矩陣。
　　 KLU(Clark Kent LU),是由Clark Kent專門針對大型電路模擬矩陣設(shè)計(jì)的一種新型的稀疏矩陣求解算法。KLU算法共分為四個(gè)階段:預(yù)處理階段

2、、分解階段、再分解階段、求解階段。
　　 本文重點(diǎn)在GPU平臺(tái)上,對KLU算法中的預(yù)處理階段(btf_strongcomp算法、)和求解階段(klu solve算法)進(jìn)行并行性研究與實(shí)現(xiàn)。在預(yù)處理階段,利用btf算法將矩陣轉(zhuǎn)化為上三角塊的形式。btf算法包括兩個(gè)部分:btf_maxtrans算法和btf-strongcomp算法。對btf_strongcomp算法在GPU平臺(tái)上的可并行性作了詳細(xì)的研究與探討,提出了幾種可并行的方

3、案:深度優(yōu)先搜索算法、可達(dá)矩陣算法、zdec算法的并行,并對DCSC算法在GPU平臺(tái)上的可并行性作了研究。研究結(jié)果表明,在GPU平臺(tái)上實(shí)現(xiàn)btf_strongcomp算法的并行,會(huì)導(dǎo)致算法性能下降,進(jìn)而降低KLU算法的整體效率。但是對于某些矩陣而言,在使用zdec算法將矩陣轉(zhuǎn)化為上三角塊的形式后,可以提高KLU算法的整體效率。
　　 求解階段可分為兩部分:順序消元和回代求解。由于在順序消元的過程中存在很強(qiáng)的依賴性,本文只對klu

4、_solve算法的回代求解部分在GPU平臺(tái)上實(shí)現(xiàn)了并行。對于大部分矩陣而言,并行實(shí)現(xiàn)的klu_solve算法在Nvidia GeforceGTX275平臺(tái)上的運(yùn)行時(shí)間,是串行klu_solve算法在Intel Pentium D2.80GHzCPU平臺(tái)上運(yùn)行時(shí)間的10倍以上。
　　 本文通過分析電路模擬矩陣和GPU平臺(tái)的特點(diǎn),并將KLU算法中的btf_strongcomp算法和klu_solve算法在GPU平臺(tái)上實(shí)現(xiàn)了并行。實(shí)驗(yàn)