【摘要】：目前,大規(guī)模稀疏線性系統(tǒng)的求解是許多科學(xué)計(jì)算和工程技術(shù)的重要組成部分。在一些以直接法為基礎(chǔ)的稀疏線性系統(tǒng)求解任務(wù)中,稀疏線性三角系統(tǒng)的計(jì)算是求解大規(guī)模稀疏線性系統(tǒng)的核心環(huán)節(jié)。因此,快速求解稀疏線性三角系統(tǒng)成為了解決整個(gè)科學(xué)計(jì)算問(wèn)題的關(guān)鍵。近幾年,隨著科學(xué)計(jì)算任務(wù)的規(guī)模和復(fù)雜度不斷提高,稀疏線性三角系統(tǒng)的規(guī)模和復(fù)雜度也越來(lái)越大,導(dǎo)致所需處理的數(shù)據(jù)量驟增。然而,已有的求解方法均受限于稀疏線性三角系統(tǒng)求解的傳統(tǒng)觀點(diǎn),即某一個(gè)變量的求解必須等到其所有前驅(qū)變量求解完成之后才能開(kāi)始。這種方式不僅限制了求解時(shí)能夠達(dá)到的任務(wù)并行度,無(wú)法充分利用眾核處理器豐富的并行硬件資源。而且,線程間頻繁的數(shù)據(jù)傳遞使同步開(kāi)銷較大,甚至抵消了并行計(jì)算技術(shù)帶來(lái)的優(yōu)勢(shì)。針對(duì)現(xiàn)有方法存在的問(wèn)題,本文提出一種基于部分值相加的并行求解算法。該方法首先并行計(jì)算變量的部分值,然后把變量的所有部分值相加得到變量的最終值。由于變量計(jì)算時(shí)無(wú)需等待所有前驅(qū)變量完成計(jì)算,大大提高了求解并行度和計(jì)算速度。在本文工作中,基于CUDA計(jì)算平臺(tái)實(shí)現(xiàn)了并行求解算法。該算法把表示變量求解順序的關(guān)聯(lián)圖分解成多個(gè)子圖,每個(gè)線程計(jì)算子圖的一層,充分利用了GPU豐富的并行計(jì)算資源。其次,為了減少存儲(chǔ)器訪問(wèn)對(duì)算法性能的影響,充分利用了全局內(nèi)存容量大及共享內(nèi)存訪存延遲低的特點(diǎn),對(duì)本文提出的并行求解算法進(jìn)行了優(yōu)化。實(shí)驗(yàn)結(jié)果表明,與調(diào)用cuSPARSE庫(kù)的求解算法以及無(wú)同步并行求解算法的計(jì)算時(shí)間比較,本文并行算法的計(jì)算速度平均提高80%,最大提高99%。在保證計(jì)算精度的前提下,大大提高了稀疏線性三角系統(tǒng)的求解速度。
【圖文】：

圖 4-2 三種求解算法的計(jì)算時(shí)間比較圖 4-2 中的斷層柱狀圖顯示了三種算法的計(jì)算時(shí)間，并對(duì)其進(jìn)行了比較。通過(guò)上圖可以清晰、直觀的看出，本文算法的計(jì)算時(shí)間明顯小于其它兩種算法的計(jì)算時(shí)間，在保證計(jì)算精度的前提下，大大提高了稀疏線性三角系統(tǒng)的求解速度。這充分驗(yàn)證了基于部分值相加的并行求解算法具有高效性和優(yōu)越性。4.3.3.1 與調(diào)用庫(kù) cuSPARSE 方法比較，本文算法計(jì)算速度的提高進(jìn)一步證明本文并行算法的高效性，以調(diào)用 cuSPARSE 庫(kù)求解算法的計(jì)算時(shí)間為歸一化標(biāo)準(zhǔn)，用公式(4-1)計(jì)算本文并行算法計(jì)算速度提高的百分比。( )cusp addcuspT TT (4-1)式中，cuspT ——調(diào)用 cuSPARSE 庫(kù)求解方法的計(jì)算時(shí)間；addT ——本文算法的計(jì)算時(shí)間。經(jīng)過(guò)計(jì)算，本文并行算法計(jì)算速度提高的百分比如圖 4-3 所示。

圖 4-3 本文算法計(jì)算速度的提高由圖 4-3 中折線可知，以調(diào)用 cuSPARSE 庫(kù)求解方法的計(jì)算時(shí)間為標(biāo)準(zhǔn)，針對(duì)不同規(guī)模的稀疏性線性三角系統(tǒng)求解，本文算法的計(jì)算速度均有明顯的提高，最小的速度提高百分比為 56%，最大的速度提高百分比達(dá)到 99%，明顯加快了稀疏線性三角系統(tǒng)的求解速度。這是因?yàn)檎{(diào)用 cuSPARSE 庫(kù)的求解算法存在分析和求解兩個(gè)階段，其中，分析階段非常耗時(shí)，約占總求解時(shí)間的百分之八十，這嚴(yán)重阻礙了求解線性三角系統(tǒng)的速度。然而，基于部分值相加的并行算法不需要分析復(fù)雜的稀疏矩陣結(jié)構(gòu)，，變量的計(jì)算順序在求解時(shí)自然地執(zhí)行，完全消除預(yù)處理階段，從而大大減少了計(jì)算時(shí)間，提高了求解速度。4.3.3.2 與無(wú)同步求解算法比較，本文算法計(jì)算速度的提高以無(wú)同步算法的計(jì)算時(shí)間為歸一化標(biāo)準(zhǔn)，用公式(4-2)計(jì)算本文并行算法計(jì)算速度提高的百分比。( )unsy addT T (4-2)
【學(xué)位授予單位】：華北電力大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：TP332;TP301.6

【相似文獻(xiàn)】

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

1 陸益君;關(guān)于帶狀線性方程組的并行求解[J];數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用;1988年02期

2 王能超;陸益君;;并行求解三對(duì)角線性方程組的分段消元法[J];應(yīng)用數(shù)學(xué);1989年01期

3 王建一，張衛(wèi)，王殿富;有限元問(wèn)題的并行求解[J];哈爾濱工業(yè)大學(xué)學(xué)報(bào);1994年02期

4 郭福順，李蓮治，臧天儀;一種并行求解方法的研究及相關(guān)算法的分析[J];小型微型計(jì)算機(jī)系統(tǒng);1996年04期

5 徐曉飛;曹祥玉;姚旭;陳盼;;一種基于Doolittle LU分解的線性方程組并行求解方法[J];電子與信息學(xué)報(bào);2010年08期

6 侯英,李曉梅,馬欣明;工作站網(wǎng)絡(luò)下三對(duì)角方程組并行求解[J];計(jì)算機(jī)工程與設(shè)計(jì);1998年01期

7 韓莉，車曉輪，胡義;一類稀疏線性方程組的并行求解方法[J];吉林化工學(xué)院學(xué)報(bào);1996年04期

8 徐國(guó)市;魯發(fā)凱;許卓群;余華山;丁文魁;;一種面向生物基因組可變剪接問(wèn)題的網(wǎng)絡(luò)并行求解方案[J];計(jì)算機(jī)研究與發(fā)展;2007年10期

9 李炳坤;;Transputer上正定方程組并行求解算法[J];計(jì)算機(jī)工程與應(yīng)用;1990年Z1期

10 張紹新;并行求解高維無(wú)約束最優(yōu)化問(wèn)題的一種有效方法[J];計(jì)算機(jī)工程與科學(xué);1984年04期

相關(guān)會(huì)議論文 前8條

1 張衡;鄭漢垣;張武;;二維雙曲型方程初邊值問(wèn)題的塊三對(duì)角可擴(kuò)展并行求解算法[A];2009年全國(guó)開(kāi)放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集(下冊(cè))[C];2009年

2 高旭東;殷保群;唐昊;周亞平;奚宏生;;一類連續(xù)時(shí)間Markov控制過(guò)程最優(yōu)平穩(wěn)控制策略的并行求解算法[A];第二十一屆中國(guó)控制會(huì)議論文集[C];2002年

3 王本龍;D.C.Causon;劉樺;;不可壓縮SPH數(shù)學(xué)模型的并行求解[A];第二十一屆全國(guó)水動(dòng)力學(xué)研討會(huì)暨第八屆全國(guó)水動(dòng)力學(xué)學(xué)術(shù)會(huì)議暨兩岸船舶與海洋工程水動(dòng)力學(xué)研討會(huì)文集[C];2008年

4 李文波;孫樂(lè);;一種LDA模型的高效并行求解算法[A];第六屆全國(guó)信息檢索學(xué)術(shù)會(huì)議論文集[C];2010年

5 孟嘉樂(lè);唐惠慶;郭占成;;多流體高爐數(shù)學(xué)模型及并行求解[A];2012年全國(guó)冶金物理化學(xué)學(xué)術(shù)會(huì)議專輯（上冊(cè)）[C];2012年

6 曹琰;王清賢;魏強(qiáng);尹中旭;;基于相容和搜索結(jié)合的并行約束求解方法[A];2013年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（第五分冊(cè)）[C];2013年

7 任鴻頻;胡月圓;;多學(xué)科優(yōu)化設(shè)計(jì)與分析CAE軟件二次開(kāi)發(fā)及應(yīng)用[A];結(jié)構(gòu)及多學(xué)科優(yōu)化工程應(yīng)用與理論研討會(huì)’2009（CSMO-2009）論文集[C];2009年

8 宋庭新;李慧;;面向服務(wù)的有限元并行計(jì)算網(wǎng)格系統(tǒng)設(shè)計(jì)[A];湖北省機(jī)械工程學(xué)會(huì)設(shè)計(jì)與傳動(dòng)學(xué)會(huì)、武漢機(jī)械設(shè)計(jì)與傳動(dòng)學(xué)會(huì)2008年學(xué)術(shù)年會(huì)論文集（2）[C];2008年

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

1 仲妍;大型稀疏線性方程組并行求解及預(yù)處理技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2010年

2 吳東陽(yáng);三維渦流場(chǎng)單元級(jí)別并行算法研究及應(yīng)用[D];沈陽(yáng)工業(yè)大學(xué);2017年

3 陽(yáng)王東;CPU+GPU異構(gòu)平臺(tái)上稀疏線性系統(tǒng)快速并行求解算法研究[D];湖南大學(xué);2017年

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

1 宋麗翠;大規(guī)模稀疏線性系統(tǒng)的并行求解方法研究[D];華北電力大學(xué);2019年

2 朱成;五對(duì)角線性方程組的并行求解算法的研究[D];湖南大學(xué);2016年

3 苗樹(shù)明;NS方程在GPU上的并行實(shí)現(xiàn)[D];上海交通大學(xué);2011年

4 劉鳳;核外并行求解線性方程組的設(shè)計(jì)與實(shí)現(xiàn)[D];遼寧師范大學(xué);2011年

5 許合偉;用多色SSOR-PCG并行求解有限元方程組[D];長(zhǎng)江科學(xué)院;2012年

6 洪文杰;基于云平臺(tái)的矩陣計(jì)算及其在血流動(dòng)力學(xué)仿真中的應(yīng)用[D];浙江工業(yè)大學(xué);2015年

7 李明磊;復(fù)雜目標(biāo)電磁散射分析中的參數(shù)化建模及并行求解[D];西安電子科技大學(xué);2011年

8 仇江濤;基于多線程并行求解的客流分析方法研發(fā)[D];中國(guó)海洋大學(xué);2006年

9 李曉蕊;求解大規(guī)模支持向量機(jī)問(wèn)題的并行算法研究[D];山東科技大學(xué);2011年

10 邢芳;基于集群系統(tǒng)并行求解線性方程組的設(shè)計(jì)與實(shí)現(xiàn)[D];遼寧師范大學(xué);2010年

本文編號(hào)：2625446