【摘要】：針對GPU集群系統(tǒng),研究了分解近似逆(approximate inverse,AINV)和對稱逐次超松弛-近似逆(symmetric successive over relaxation approximate inverse,SSOR-AI)兩類近似逆預(yù)條件的并行算法。采用多級k-路圖劃分方法,通過子圖的內(nèi)點和邊界點識別方法以及稀疏矩陣的置換技術(shù),提出了將稀疏矩陣轉(zhuǎn)換為分塊箭形矩陣的并行方法。基于所形成的分塊箭形矩陣,結(jié)合塊內(nèi)稀疏矩陣近似逆串行、塊間并行的策略給出了近似逆預(yù)條件的并行方法,實現(xiàn)了AINV和SSOR-AI并行算法,解決了AINV預(yù)條件難以并行的問題�；贑PU與GPU協(xié)同計算、主機端頁鎖定內(nèi)存和設(shè)備端計算與通信重疊的優(yōu)化技術(shù),實現(xiàn)了并行近似逆預(yù)條件與共軛梯度(conjugate gradient,CG)算法相結(jié)合的線性方程組混合并行求解器。數(shù)值實驗表明,所提方法對AINV和SSOR-AI兩類近似逆預(yù)條件,在多GPU上獲得了很好的可擴展性和加速效果。
[Abstract]:For GPU cluster systems, parallel algorithms for decomposing approximate inverse (approximate inverse,AINV) and symmetric successive overrelaxation approximate inverse (symmetric successive over relaxation approximate inverse,SSOR-AI (symmetric successive over relaxation approximate inverse,SSOR-AI) are studied. A parallel method of converting sparse matrix into block quiver matrix is proposed by using the method of multi-level k-path graph partition, the method of identifying interior and boundary points of subgraph and the technique of replacing sparse matrix. Based on the block quiver matrix, the parallel method of approximate inverse precondition is given by combining the strategy of approximate inverse serial and inter-block parallelism of sparse matrix in block. The parallel algorithm of AINV and SSOR-AI is realized, and the problem that AINV precondition is difficult to parallel is solved. Based on the cooperative computation of CPU and GPU, the optimization technique of memory locking on the host side and the overlap of computing and communication on the device side, a hybrid parallel solver for linear equations is implemented, which combines the parallel approximate inverse precondition with the conjugate gradient (conjugate gradient,CG) algorithm. Numerical experiments show that the proposed method can achieve good scalability and acceleration on multiple GPU for two kinds of approximate inverse preconditioners: AINV and SSOR-AI.
【作者單位】： 中國科學(xué)院計算機網(wǎng)絡(luò)信息中心;中國科學(xué)院大學(xué);
【基金】：國家重點基礎(chǔ)研究發(fā)展計劃(973計劃)No.2011CB309702 數(shù)學(xué)工程與先進計算國家重點實驗室開放基金No.2014A03~~
【分類號】：TP338.6

【共引文獻】

相關(guān)期刊論文 前4條

1 趙寧;秦策;徐玉聰;;擬極小殘差法在GPU上的優(yōu)化研究[J];科學(xué)技術(shù)與工程;2014年07期

2 李佳佳;張秀霞;譚光明;陳明宇;;選擇稀疏矩陣乘法最優(yōu)存儲格式的研究[J];計算機研究與發(fā)展;2014年04期

3 陳堯;趙永華;趙慰;趙蓮;;GPU加速不完全Cholesky分解預(yù)條件共軛梯度法[J];計算機研究與發(fā)展;2015年04期

4 鄭漢垣;;GaBP算法優(yōu)化與實現(xiàn)[J];龍巖學(xué)院學(xué)報;2015年02期

相關(guān)博士學(xué)位論文 前8條

1 張芡;大規(guī)模稀疏線性系統(tǒng)的稀疏近似逆預(yù)處理技術(shù)[D];清華大學(xué);2013年

2 王艷廣;伽遼金多極邊界元法及其在聲學(xué)中的應(yīng)用[D];湖南大學(xué);2013年

3 姚路;圖分割算法及其在大規(guī)模數(shù)值并行計算中的應(yīng)用研究[D];國防科學(xué)技術(shù)大學(xué);2013年

4 張珂良;單GPU及GPU異構(gòu)集群的若干關(guān)鍵技術(shù)研究[D];復(fù)旦大學(xué);2013年

5 鄭漢垣;大規(guī)模稀疏線性方程組求解的并行GaBP算法研究[D];上海大學(xué);2014年

6 胡子翔;塑料注射成形模擬中方程組的高效求解方法[D];華中科技大學(xué);2014年

7 馮曉文;基于GPU的相似度計算關(guān)鍵技術(shù)研究[D];華中科技大學(xué);2014年

8 穆帥;針對不規(guī)則應(yīng)用的圖形處理器資源調(diào)度關(guān)鍵技術(shù)研究[D];清華大學(xué);2013年

【相似文獻】

相關(guān)期刊論文 前10條

1 楊晟院;肖映雄;舒適;鐘柳強;;高次有限元方程的一種并行預(yù)條件子[J];系統(tǒng)仿真學(xué)報;2008年22期

2 吳建平;王正華;李曉梅;;二維三溫能量方程組的預(yù)條件迭代軟件包研制——離散所得稀疏線性方程組的求解[J];計算機工程與應(yīng)用;2007年33期

3 沈海龍;邵新慧;張鐵;李長軍;;H-矩陣方程組的預(yù)條件迭代法[J];數(shù)值計算與計算機應(yīng)用;2009年04期

4 李磊,張玉,謝擁軍,梁昌洪;"鄰居單元"為基礎(chǔ)的預(yù)條件方法及其應(yīng)用[J];電子與信息學(xué)報;2005年03期

5 吳建平,王正華,李曉梅;塊三對角矩陣的并行局部塊分解預(yù)條件[J];計算機學(xué)報;2005年03期

6 張占龍;鄧軍;朱禎海;肖冬萍;李德文;胡強;何為;郭偉;;電場計算的快速多極子預(yù)條件高階邊界元法[J];重慶大學(xué)學(xué)報;2011年06期

7 吳建平,李曉梅;三維問題的局部塊分解預(yù)條件[J];計算物理;2003年01期

8 吳建平;張理論;馬懷發(fā);宋君強;張衛(wèi)民;;排序?qū)χ丿B區(qū)域分解型并行ILU的影響分析[J];計算機工程與應(yīng)用;2012年33期

9 梁莉;李月卉;;求解電磁場邊值問題有限元線性系統(tǒng)的新型預(yù)條件算法[J];電腦知識與技術(shù);2013年29期

10 吳建平,李曉梅;塊三對角矩陣局部塊分解及其在預(yù)條件中的應(yīng)用[J];計算機學(xué)報;2002年08期

相關(guān)會議論文 前10條

1 梅金順;劉洪;;預(yù)條件方程組及其應(yīng)用[A];中國科學(xué)院地質(zhì)與地球物理研究所二○○四學(xué)術(shù)論文匯編·第三卷(油氣·礦產(chǎn)·水資源)[C];2004年

2 劉喜武;劉洪;;實現(xiàn)稀疏反褶積的預(yù)條件雙共軛梯度法[A];中國科學(xué)院地質(zhì)與地球物理研究所二○○三學(xué)術(shù)論文匯編·第四卷(油氣資源)[C];2003年

3 柯濤;丁建軍;丁大志;樊振宏;陳如山;;特征譜雙步預(yù)條件結(jié)合多分辨預(yù)條件技術(shù)快速分析電磁散射問題[A];2007年全國微波毫米波會議論文集（上冊）[C];2007年

4 丁大志;王晨;張清榮;陳如山;;加速多層快速多極子的近區(qū)迭代預(yù)條件方法的應(yīng)用(英文)[A];2005'全國微波毫米波會議論文集（第一冊）[C];2006年

5 霍志周;熊登;張劍鋒;;預(yù)條件共軛梯度法在地震數(shù)據(jù)重建方法中的應(yīng)用[A];中國科學(xué)院地質(zhì)與地球物理研究所2013年度（第13屆）學(xué)術(shù)論文匯編——油氣資源研究室[C];2014年

6 姜兆能;陳如山;陳華;樊振宏;丁大志;;多分辨預(yù)條件結(jié)合混合形式快速多極子算法分析低頻散射問題[A];2009年全國微波毫米波會議論文集（下冊）[C];2009年

7 肖映雄;陳鵬;舒適;;兩類網(wǎng)格結(jié)構(gòu)模型的預(yù)處理方法[A];中國計算力學(xué)大會'2010（CCCM2010）暨第八屆南方計算力學(xué)學(xué)術(shù)會議（SCCM8）論文集[C];2010年

8 董健;柴舜連;毛鈞杰;;預(yù)條件技術(shù)和迭代算法在高效實現(xiàn)MLFMA中的對比研究[A];2005'全國微波毫米波會議論文集（第三冊）[C];2006年

9 趙延文;張雪峰;陸田;楊穎怡;;矩陣預(yù)條件技術(shù)在時域積分方程MOT算法中的應(yīng)用[A];2009年全國天線年會論文集（上）[C];2009年

10 闕肖峰;聶在平;;一類基于MLFMA的分組稀疏近似逆預(yù)條件技術(shù)[A];2009年全國天線年會論文集（上）[C];2009年

相關(guān)博士學(xué)位論文 前10條

1 李正光;結(jié)構(gòu)布局修改靜力重分析的預(yù)條件共軛梯度法[D];吉林大學(xué);2004年

2 張勇;線性方程組預(yù)條件技術(shù)及在二維三溫問題中的應(yīng)用和實現(xiàn)[D];電子科技大學(xué);2008年

3 任志剛;預(yù)條件算法及在電磁場數(shù)值模擬中的應(yīng)用[D];電子科技大學(xué);2010年

4 李月卉;電磁場數(shù)值求解中迭代方法與預(yù)條件技術(shù)研究[D];電子科技大學(xué);2011年

5 張振宇;數(shù)值線性代數(shù)中的若干問題[D];復(fù)旦大學(xué);2003年

6 沈海龍;線性代數(shù)系統(tǒng)迭代解法與預(yù)條件方法研究[D];東北大學(xué);2013年

7 王瑞瑞;求解某些特殊稀疏線性系統(tǒng)的數(shù)值解法[D];廈門大學(xué);2009年

8 程光輝;大型稀疏線性代數(shù)系統(tǒng)迭代解法研究[D];電子科技大學(xué);2008年

9 劉春梅;幾種求解H（curl）與H（grad）型偏微分方程有限元離散系統(tǒng)的多水平快速算法[D];湘潭大學(xué);2012年

10 陳明;并行多層快速多極子算法加速技術(shù)的研究[D];南京理工大學(xué);2012年

相關(guān)碩士學(xué)位論文 前10條

1 劉金妮;近似逆預(yù)條件子的研究[D];電子科技大學(xué);2009年

2 譚林;兩類典型微分方程離散化系統(tǒng)的預(yù)條件子研究[D];湘潭大學(xué);2006年

3 趙海燕;線性系統(tǒng)的預(yù)條件解法[D];揚州大學(xué);2008年

4 徐錦秋;解一類微分方程的預(yù)條件方法的收斂性[D];揚州大學(xué);2009年

5 江躍勇;塊三對角矩陣的不完全分解預(yù)條件方法[D];電子科技大學(xué);2007年

6 徐森林;求解二階混合有限體元離散系統(tǒng)的高效預(yù)條件子[D];湘潭大學(xué);2011年

7 韋亮;確定加權(quán)多分裂預(yù)條件子的三個極小化模型[D];太原理工大學(xué);2012年

8 李進陽;復(fù)雜目標電磁建模及預(yù)條件加速技術(shù)研究[D];南京理工大學(xué);2013年

9 周少博;大型線性方程組不完全分解預(yù)條件方法的研究[D];電子科技大學(xué);2008年

10 王衛(wèi)芳;線性方程組的預(yù)條件迭代解法及其比較性定理[D];陜西師范大學(xué);2008年

，

本文編號：2386454