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

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

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

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

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