【摘要】：近年來,隨著現(xiàn)場可編程門陣列(FPGA)在計(jì)算、存儲(chǔ)和邏輯等資源方面的急劇增長,基于FPGA的可重構(gòu)計(jì)算成為高性能計(jì)算領(lǐng)域的一個(gè)重要分支,越來越凸顯其重要的研究和應(yīng)用價(jià)值。圖計(jì)算是大數(shù)據(jù)分析領(lǐng)域的一種關(guān)鍵應(yīng)用,在大數(shù)據(jù)分析方面具有重要作用,FPGA定制計(jì)算在加速圖計(jì)算方面具有巨大的潛力。然而,現(xiàn)有FPGA圖計(jì)算存在并行算法設(shè)計(jì)、并行度開發(fā)和支持圖計(jì)算規(guī)模有限等挑戰(zhàn)。為應(yīng)對(duì)這些挑戰(zhàn),本文對(duì)大規(guī)模圖計(jì)算的FPGA實(shí)現(xiàn)技術(shù)進(jìn)行了深入研究,本文的主要工作和創(chuàng)新點(diǎn)如下:(1)提出了面向大規(guī)模圖最短路徑計(jì)算的FPGA并行算法和硬件實(shí)現(xiàn)結(jié)構(gòu)。針對(duì)現(xiàn)有單源路徑問題的FPGA實(shí)現(xiàn)采用片內(nèi)存儲(chǔ)資源來保存圖數(shù)據(jù)和計(jì)算結(jié)果,難以高效處理大規(guī)模圖數(shù)據(jù)處理的問題,提出了基于Eager Dijkstra算法變種的FPGA并行單源最短路徑算法,每次迭代從優(yōu)先隊(duì)列移除多個(gè)元素進(jìn)行并行處理,開發(fā)了并行性。為了實(shí)現(xiàn)大規(guī)模優(yōu)先隊(duì)列的處理,提出了基于片外存儲(chǔ)的大規(guī)模優(yōu)先隊(duì)列實(shí)現(xiàn)方法,利用片外DRAM存儲(chǔ)器保存溢出隊(duì)列元素,并設(shè)計(jì)合理策略將片外元素重新放回片內(nèi),從而保證了大規(guī)模優(yōu)先隊(duì)列處理的正確性。選取真實(shí)的公路網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行測試,實(shí)驗(yàn)結(jié)果表明基于FPGA的并行單源最短路徑算法和通用微處理器上的軟件實(shí)現(xiàn)相比可以獲得5倍的加速效果,并且功耗僅為通用微處理器的1/4。(2)提出了面向大規(guī)模圖最小生成樹計(jì)算的FPGA并行算法和硬件實(shí)現(xiàn)結(jié)構(gòu)。針對(duì)現(xiàn)有最小生成樹計(jì)算的FPGA實(shí)現(xiàn)并行度開發(fā)不夠和不能處理大規(guī)模圖的問題,提出了一種基于Prim算法的FPGA最小生成樹并行算法。該算法選取多個(gè)起始結(jié)點(diǎn)并行執(zhí)行Prim算法生成多個(gè)子樹,當(dāng)檢測到子樹間沖突時(shí),停止當(dāng)前子樹生成,選擇其它的未訪問結(jié)點(diǎn)繼續(xù)生成新的子樹,當(dāng)所有結(jié)點(diǎn)都被訪問時(shí),對(duì)所有的子樹進(jìn)行合并。對(duì)于單個(gè)子樹的Prim計(jì)算,提出了基于線性陣列優(yōu)先隊(duì)列的實(shí)現(xiàn)方法,當(dāng)優(yōu)先隊(duì)列溢出時(shí),采用DRAM存儲(chǔ)溢出隊(duì)列元素,實(shí)現(xiàn)了大規(guī)模子樹生成。選取隨機(jī)生成圖進(jìn)行測試,實(shí)驗(yàn)結(jié)果表明基于FPGA的并行最小生成樹算法和通用微處理器上的軟件實(shí)現(xiàn)相比可以獲得2.58倍到6.88倍的加速比。(3)提出了面向大規(guī)模圖寬度優(yōu)先搜索(BFS)的FPGA消息傳遞并行算法和硬件實(shí)現(xiàn)結(jié)構(gòu)。針對(duì)大規(guī)模并行寬度優(yōu)先搜索通信延遲大的問題,首次提出了一種新穎的基于二維消息傳遞陣列結(jié)構(gòu)的并行寬度優(yōu)先搜索算法,利用片上存儲(chǔ)減少了處理單元之間的通信延遲。與相關(guān)工作相比,該結(jié)構(gòu)顯著減少了片上存儲(chǔ)資源的消耗,并且具備良好的可擴(kuò)展性,能夠映射到多FPGA系統(tǒng)。此外,提出了一種基于片上位圖存儲(chǔ)的分布式隊(duì)列實(shí)現(xiàn)方法,該方法避免了為判斷頂點(diǎn)是否為當(dāng)前層待搜索頂點(diǎn)而引入的片外訪存開銷。使用不同類型的圖進(jìn)行了測試,并與相關(guān)工作進(jìn)行了比較。由于隨機(jī)訪存的延遲較大,單片F(xiàn)PGA上的BFS算法實(shí)測性能低于相關(guān)工作的性能。盡管如此,本文提出的FPGA并行BFS算法和硬件結(jié)構(gòu)在理論上能夠擴(kuò)展到任意數(shù)量FPGA構(gòu)成的計(jì)算系統(tǒng)。(4)提出了面向大規(guī)模圖匹配的FPGA并行算法和硬件實(shí)現(xiàn)結(jié)構(gòu)。針對(duì)現(xiàn)有二部圖圖匹配計(jì)算的FPGA實(shí)現(xiàn)基于片上存儲(chǔ)保存圖數(shù)據(jù),無法高效處理大規(guī)模圖匹配的問題,提出了一種二部圖圖匹配的并行算法,該算法每次對(duì)未指派的多個(gè)結(jié)點(diǎn)進(jìn)行并行處理,提高了并行性,在此基礎(chǔ)上提出了一種基于片外存儲(chǔ)的二部圖匹配并行計(jì)算體系結(jié)構(gòu),與相關(guān)FPGA實(shí)現(xiàn)相比,該結(jié)構(gòu)可以處理更大規(guī)模的圖匹配。選取隨機(jī)生成圖進(jìn)行了測試,實(shí)驗(yàn)結(jié)果表明,FPGA實(shí)現(xiàn)優(yōu)于通用處理器的實(shí)現(xiàn)。
[Abstract]:......
【學(xué)位授予單位】：國防科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：TN791

【相似文獻(xiàn)】

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

1 科卞;并行算法及其在電子系統(tǒng)中的應(yīng)用[J];電子科技大學(xué)學(xué)報(bào);2002年02期

2 徐云;孫廣中;鄭啟龍;吳俊敏;陳國良;;“并行算法”課程的教學(xué)與探討[J];教育與現(xiàn)代化;2008年04期

3 陳國良;孫廣中;徐云;呂敏;;并行算法研究方法學(xué)[J];計(jì)算機(jī)學(xué)報(bào);2008年09期

4 羅貴章;陳忠偉;;并行算法綜述[J];計(jì)算機(jī)光盤軟件與應(yīng)用;2013年15期

5 謝鐵柱;吳功廣;;多項(xiàng)式幾種并行算法的比較與優(yōu)化[J];計(jì)算機(jī)工程與科學(xué);1981年01期

6 李曉梅 ,胡慶豐;并行算法的發(fā)展與展望[J];計(jì)算機(jī)工程與科學(xué);1991年03期

7 童麗,王正明,曾泳泓;自變量選擇及其并行算法[J];數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用;2001年03期

8 陳國良;昔日王榭堂前燕,飛入尋常百姓家淺談并行算法[J];新電腦;2002年12期

9 李曉梅;《可擴(kuò)展并行算法的設(shè)計(jì)與分析》簡介[J];裝備指揮技術(shù)學(xué)院學(xué)報(bào);2003年02期

10 吳磊,蘆東昕,方馬;并行算法中的指針轉(zhuǎn)移技術(shù)分析[J];計(jì)算機(jī)工程;2003年22期

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

1 姚向東;;并行算法到并行結(jié)構(gòu)的映射[A];中國工程物理研究院科技年報(bào)（2001）[C];2001年

2 高華;苗世光;;城市小區(qū)尺度模式并行算法研究[A];中國氣象學(xué)會(huì)2006年年會(huì)“中尺度天氣動(dòng)力學(xué)、數(shù)值模擬和預(yù)測”分會(huì)場論文集[C];2006年

3 王志成;吳頌平;;多塊結(jié)構(gòu)網(wǎng)格并行算法研究[A];北京力學(xué)會(huì)第20屆學(xué)術(shù)年會(huì)論文集[C];2014年

4 焦龍;郭亞紅;紀(jì)守領(lǐng);李金寶;;基于多核計(jì)算機(jī)的分子動(dòng)力學(xué)并行算法的實(shí)現(xiàn)[A];黑龍江省計(jì)算機(jī)學(xué)會(huì)2009年學(xué)術(shù)交流年會(huì)論文集[C];2010年

5 張衡;張武;;三維拋物型初邊值問題的塊三對(duì)角可擴(kuò)展并行算法[A];2007年全國開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集(上冊(cè))[C];2007年

6 王雷章;張愛武;劉曉萌;;三維建模中平面分割并行算法的設(shè)計(jì)與實(shí)現(xiàn)[A];中國系統(tǒng)仿真學(xué)會(huì)第五次全國會(huì)員代表大會(huì)暨2006年全國學(xué)術(shù)年會(huì)論文集[C];2006年

7 毛韶陽;李肯立;;一種基因數(shù)據(jù)的聚類并行算法研究[A];2007年全國開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集(上冊(cè))[C];2007年

8 左墨;藺小林;;電力系統(tǒng)暫態(tài)穩(wěn)定并行算法的進(jìn)展[A];第二屆中國水利水電巖土力學(xué)與工程學(xué)術(shù)討論會(huì)論文集（二）[C];2008年

9 樊洪明;李先庭;趙彬;任鴻澤;;有限元分布式并行算法研究[A];全國暖通空調(diào)制冷2002年學(xué)術(shù)年會(huì)論文集[C];2002年

10 侯有政;張方;;基于CUDA的動(dòng)載荷頻域識(shí)別的并行算法研究[A];第十屆全國振動(dòng)理論及應(yīng)用學(xué)術(shù)會(huì)議論文集（2011）上冊(cè)[C];2011年

相關(guān)重要報(bào)紙文章 前4條

1 ;并行算法研究進(jìn)展[N];中國計(jì)算機(jī)報(bào);2004年

2 新華社記者 奚啟新 本報(bào)通訊員 李汛 記者 喻國英;精彩人生[N];光明日?qǐng)?bào);2005年

3 新華社記者　奚啟新　本報(bào)記者　廖文根;三次選擇　無怨無悔[N];人民日?qǐng)?bào);2005年

4 清華大學(xué)計(jì)算機(jī)系 薛巍;電網(wǎng)仿真考驗(yàn)高性能計(jì)算[N];計(jì)算機(jī)世界;2006年

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

1 任立波;稠密顆粒兩相流的CFD-DEM耦合并行算法及數(shù)值模擬[D];山東大學(xué);2015年

2 李雪寶;太陽望遠(yuǎn)鏡海量數(shù)據(jù)并行處理技術(shù)研究[D];中國科學(xué)院研究生院(云南天文臺(tái));2015年

3 馬欣榮;微分動(dòng)力學(xué)方程的快速與并行算法研究[D];西安電子科技大學(xué);2015年

4 雷國慶;基于FPGA的圖計(jì)算并行算法和體系結(jié)構(gòu)研究[D];國防科學(xué)技術(shù)大學(xué);2015年

5 張艷;分布并行算法設(shè)計(jì)、分析與實(shí)現(xiàn)[D];電子科技大學(xué);2001年

6 杜云飛;容錯(cuò)并行算法的研究與分析[D];國防科學(xué)技術(shù)大學(xué);2008年

7 潘斌;幾何定理機(jī)器證明并行算法研究[D];中國科學(xué)院研究生院（成都計(jì)算機(jī)應(yīng)用研究所）;2006年

8 駱志剛;典型結(jié)構(gòu)大型線性方程組的分布式并行算法研究[D];中國人民解放軍國防科學(xué)技術(shù)大學(xué);2000年

9 何霞輝;基于非穩(wěn)態(tài)不可壓縮流的可擴(kuò)張并行算法研究[D];湖南大學(xué);2013年

10 戚晶晶;熱物性反問題高效并行算法研究[D];武漢理工大學(xué);2013年

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

1 陳權(quán);基于分布式集群的多攝像頭的目標(biāo)檢測和跟蹤的并行算法[D];南京理工大學(xué);2015年

2 馬煥煥;一類近場動(dòng)力學(xué)問題的并行算法[D];山東大學(xué);2015年

3 朱曉丹;一種神經(jīng)動(dòng)力學(xué)優(yōu)化系統(tǒng)的并行算法設(shè)計(jì)[D];大連理工大學(xué);2015年

4 張?jiān)?新一代視頻編碼技術(shù)的并行算法設(shè)計(jì)與實(shí)現(xiàn)[D];大連理工大學(xué);2015年

5 董蕾;基于GPU的圖像壓縮感知算法并行化研究[D];電子科技大學(xué);2015年

6 蔣昭炎;基于圖像的大場景三維重建并行算法研究[D];東北大學(xué);2013年

7 馮杰;基于MIC架構(gòu)的遙感圖像增強(qiáng)類算法并行化研究[D];電子科技大學(xué);2015年

8 鄭全剛;并行生物序列算法設(shè)計(jì)與優(yōu)化[D];山東大學(xué);2016年

9 周蘭花;基于異構(gòu)計(jì)算的電磁仿真并行算法研究[D];湖南大學(xué);2016年

10 李劍威;共形組合激發(fā)參數(shù)并行算法研究[D];西南石油大學(xué);2016年

，

本文編號(hào)：2287001