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

【相似文獻】

相關期刊論文 前10條

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

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

3 陳國良;孫廣中;徐云;呂敏;;并行算法研究方法學[J];計算機學報;2008年09期

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

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

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

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

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

9 李曉梅;《可擴展并行算法的設計與分析》簡介[J];裝備指揮技術學院學報;2003年02期

10 吳磊,蘆東昕,方馬;并行算法中的指針轉移技術分析[J];計算機工程;2003年22期

相關會議論文 前10條

1 姚向東;;并行算法到并行結構的映射[A];中國工程物理研究院科技年報（2001）[C];2001年

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

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

4 焦龍;郭亞紅;紀守領;李金寶;;基于多核計算機的分子動力學并行算法的實現(xiàn)[A];黑龍江省計算機學會2009年學術交流年會論文集[C];2010年

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

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

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

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

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

10 侯有政;張方;;基于CUDA的動載荷頻域識別的并行算法研究[A];第十屆全國振動理論及應用學術會議論文集（2011）上冊[C];2011年

相關重要報紙文章 前4條

1 ;并行算法研究進展[N];中國計算機報;2004年

2 新華社記者 奚啟新 本報通訊員 李汛 記者 喻國英;精彩人生[N];光明日報;2005年

3 新華社記者　奚啟新　本報記者　廖文根;三次選擇　無怨無悔[N];人民日報;2005年

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

相關博士學位論文 前10條

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

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

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

4 雷國慶;基于FPGA的圖計算并行算法和體系結構研究[D];國防科學技術大學;2015年

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

6 杜云飛;容錯并行算法的研究與分析[D];國防科學技術大學;2008年

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

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

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

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

相關碩士學位論文 前10條

1 陳權;基于分布式集群的多攝像頭的目標檢測和跟蹤的并行算法[D];南京理工大學;2015年

2 馬煥煥;一類近場動力學問題的并行算法[D];山東大學;2015年

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

4 張源;新一代視頻編碼技術的并行算法設計與實現(xiàn)[D];大連理工大學;2015年

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

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

7 馮杰;基于MIC架構的遙感圖像增強類算法并行化研究[D];電子科技大學;2015年

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

9 周蘭花;基于異構計算的電磁仿真并行算法研究[D];湖南大學;2016年

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

，

本文編號：2287001