【摘要】：深度優(yōu)先搜索算法在GPU集群中大型圖上的簡單執(zhí)行,會導(dǎo)致線程間的負(fù)載不平衡和無法合并內(nèi)存訪問的情況,這使得算法的性能較低。為了明顯提高算法在單個GPU和多個GPU環(huán)境下的性能,在處理數(shù)據(jù)之前通過采取一系列有效的操作來進(jìn)行重新編排。提出了構(gòu)造線程和數(shù)據(jù)之間映射的新技術(shù),通過利用前綴求和及二分查找操作來達(dá)到完美的負(fù)載平衡。為了降低通信開銷,對DFS各分支中需要進(jìn)行交換的邊集執(zhí)行修剪操作。實驗結(jié)果表明,算法在單個GPU上可以盡可能地實現(xiàn)最佳的并行性,在多GPU環(huán)境下可以最小化通信開銷。在一個GPU集群中,它可以對含有數(shù)十億節(jié)點的圖有效地執(zhí)行分布式DFS。
[Abstract]:The simple execution of the depth-first search algorithm on a large graph in a GPU cluster will lead to the imbalance of the load between threads and the inability to merge memory access, which makes the performance of the algorithm low. In order to improve the performance of the algorithm in a single GPU and multiple GPU environments, a series of effective operations are taken to rearrange the data before processing. A new technique is proposed to construct the mapping between threads and data, which can achieve perfect load balance by using prefix summation and binary lookup operations. In order to reduce communication overhead, pruning operations are performed on edge sets that need to be exchanged in each branch of DFS. Experimental results show that the algorithm can achieve the best parallelism on a single GPU and minimize the communication overhead in a multi-GPU environment. In a GPU cluster, it can effectively execute distributed DFS. on a graph with billions of nodes
【作者單位】： 衡陽師范學(xué)院計算機(jī)科學(xué)系;湖南大學(xué)信息科學(xué)與工程學(xué)院;
【基金】：國家自然科學(xué)基金項目(61370095,61370098,61070057,90715029) 湖南省教育廳科學(xué)研究一般項目(13C074) 衡陽市科技局科技發(fā)展計劃項目(2011KJ22)資助
【分類號】：TP338.6

【參考文獻(xiàn)】

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

1 盧風(fēng)順;宋君強;銀�？�;張理論;;CPU/GPU協(xié)同并行計算研究綜述[J];計算機(jī)科學(xué);2011年03期

2 李文超;嚴(yán)洪森;;一種基于PFSP性質(zhì)的深度優(yōu)先搜索算法[J];控制與決策;2009年08期

3 王海峰;陳慶奎;;圖形處理器通用計算關(guān)鍵技術(shù)研究綜述[J];計算機(jī)學(xué)報;2013年04期

4 吳鴻偉;湯偉賓;李曉潮;郭東輝;;GPU編程原理及其在網(wǎng)絡(luò)安全領(lǐng)域的應(yīng)用算法分析[J];計算機(jī)科學(xué);2012年S3期

【共引文獻(xiàn)】

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

1 王加亮;秦勃;劉健健;劉妮;;基于MapReduce的交互可視化平臺[J];電信科學(xué);2012年09期

2 楊芳菊;;基于CPU/GPU異構(gòu)平臺并行優(yōu)化的研究[J];電腦編程技巧與維護(hù);2012年18期

3 劉軍志;朱阿興;秦承志;陳臘嬌;吳輝;江凈超;;分布式水文模型的并行計算研究進(jìn)展[J];地理科學(xué)進(jìn)展;2013年04期

4 鄒航;王華秋;黃勇;;基于GPU加速的彩虹表分析MD5哈希密碼[J];重慶理工大學(xué)學(xué)報(自然科學(xué));2013年07期

5 方留楊;王密;李德仁;;CPU和GPU協(xié)同處理的光學(xué)衛(wèi)星遙感影像正射校正方法[J];測繪學(xué)報;2013年05期

6 劉藝;陳明生;吳先良;齊琦;;應(yīng)用GPU加速結(jié)合壓縮傳感技術(shù)解寬角度電磁散射問題[J];合肥師范學(xué)院學(xué)報;2013年06期

7 楊清山;劉X;熊飛;鐘立俊;邴丕浩;;基于GPU的并行區(qū)域場強計算[J];電子信息對抗技術(shù);2013年06期

8 李杰;陳慶奎;;基于藍(lán)牙4.0的GPU集群功耗測量系統(tǒng)設(shè)計[J];電子測量與儀器學(xué)報;2014年03期

9 方留楊;王密;李德仁;潘俊;;負(fù)載分配的CPU/GPU高分辨率衛(wèi)星影像調(diào)制傳遞補償方法[J];測繪學(xué)報;2014年06期

10 洪亮;周松濤;羅伊;石婷婷;胡飛;;海量遙感數(shù)據(jù)的GPU通用加速計算技術(shù)[J];地理空間信息;2014年03期

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

1 ;Research on DSP-GPU Heterogeneous Computing System[A];Information Technology and Computer Science—Proceedings of 2012 National Conference on Information Technology and Computer Science[C];2012年

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

1 曹聞;時空數(shù)據(jù)模型及其應(yīng)用研究[D];解放軍信息工程大學(xué);2011年

2 江涵;大規(guī)模電力系統(tǒng)暫態(tài)穩(wěn)定并行計算研究[D];浙江大學(xué);2012年

3 周勇;基于并行計算的數(shù)據(jù)流處理方法研究[D];大連理工大學(xué);2013年

4 韓宇韜;數(shù)字正射影像鑲嵌中色彩一致性處理的若干問題研究[D];武漢大學(xué);2014年

5 劉壽生;虛擬現(xiàn)實仿真平臺異構(gòu)并行計算關(guān)鍵技術(shù)研究[D];中國海洋大學(xué);2014年

6 楊蒙召;人體面部真實感快速渲染方法研究[D];哈爾濱工業(yè)大學(xué);2014年

7 崔樹林;基于GPU的并行矢量數(shù)據(jù)分析與索引技術(shù)研究[D];中國科學(xué)院研究生院（東北地理與農(nóng)業(yè)生態(tài)研究所）;2014年

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

1 楊博;深穿透粒子輸運蒙特卡羅模擬的CPU/GPU協(xié)同算法研究[D];國防科學(xué)技術(shù)大學(xué);2011年

2 石志才;異構(gòu)平臺上協(xié)同計算的相關(guān)研究[D];國防科學(xué)技術(shù)大學(xué);2011年

3 王翔;球諧函數(shù)展開快速算法及其并行算法研究[D];國防科學(xué)技術(shù)大學(xué);2011年

4 呂東川;基于并行計算的腦電信號分析方法研究[D];燕山大學(xué);2012年

5 栗超;一種三維可視化系統(tǒng)的優(yōu)化策略[D];燕山大學(xué);2012年

6 刁興光;獨立成分算法在GPU上的實現(xiàn)[D];大連理工大學(xué);2012年

7 趙琳琳;非均勻地層隨鉆電磁波測井電磁響應(yīng)的研究[D];山東大學(xué);2012年

8 李國棟;基于異構(gòu)計算平臺的列數(shù)據(jù)庫并行查詢技術(shù)研究與實現(xiàn)[D];華南理工大學(xué);2012年

9 沈玉琳;通用GPU計算技術(shù)在高性能計算平臺上的應(yīng)用研究[D];蘭州大學(xué);2012年

10 周智強;基于圖像融合和模糊聚類的SAR圖像變化檢測[D];西安電子科技大學(xué);2012年

【二級參考文獻(xiàn)】

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

1 越民義,韓繼業(yè);n個零件在m臺機(jī)床上的加工順序問題(Ⅰ)[J];中國科學(xué);1975年05期

2 ;Multi-scale HPC system for multi-scale discrete simulation—Development and application of a supercomputer with 1 Petaflops peak performance in single precision[J];Particuology;2009年04期

3 吳恩華,柳有權(quán);基于圖形處理器(GPU)的通用計算[J];計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報;2004年05期

4 韓博;周秉鋒;;GPGPU性能模型及應(yīng)用實例分析[J];計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報;2009年09期

5 伍楠;文梅;何義;荀長慶;任巨;柴俊;張春元;;一種流處理器體系結(jié)構(gòu)MASA及其在流體力學(xué)計算中的評測[J];計算機(jī)學(xué)報;2008年01期

6 周國亮;陳紅;李翠平;王珊;鄭濤;;基于圖形處理器的并行方體計算[J];計算機(jī)學(xué)報;2010年10期

7 越民義,韓繼業(yè);同順序m×n排序問題的一個新方法[J];科學(xué)通報;1979年18期

8 金鋒;宋士吉;吳澄;;一類基于FSP問題Block性質(zhì)的快速TS算法[J];控制與決策;2007年03期

9 李建明;遲忠先;萬單領(lǐng);;一種基于GPU加速細(xì)粒度并行遺傳算法的實現(xiàn)方法[J];控制與決策;2008年06期

10 李建明;胡祥培;龐占龍;錢昆明;;一種基于GPU加速的細(xì)粒度并行蟻群算法[J];控制與決策;2009年08期

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

1 吳強;GPU加速高速粒子碰撞模擬[D];國防科學(xué)技術(shù)大學(xué);2009年

2 方旭東;面向大規(guī)�？茖W(xué)計算的CPU-GPU異構(gòu)并行技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2009年

【相似文獻(xiàn)】

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

1 龔建華;;深度優(yōu)先搜索算法及其改進(jìn)[J];現(xiàn)代電子技術(shù);2007年22期

2 張選平,杭省策;利用深度優(yōu)先搜索方法求解作業(yè)排序[J];系統(tǒng)工程與電子技術(shù);1998年08期

3 虞成誠;鐘聲;胡紹華;;基于深度優(yōu)先搜索的一般圖匹配算法[J];計算機(jī)工程與科學(xué);2008年12期

4 袁和金;張艷寧;周濤;;基于矢量量化和深度優(yōu)先搜索的軌跡分布模式學(xué)習(xí)算法[J];計算機(jī)應(yīng)用;2007年05期

5 蔡樂才;朱顥東;;基于AI問題的一種“最優(yōu)”解方法及實現(xiàn)[J];四川理工學(xué)院學(xué)報(自然科學(xué)版);2008年05期

6 劉中華;張穎超;;深度優(yōu)先搜索的非遞歸算法[J];科技信息;2010年25期

7 蘇兆鋒;求解連通圖關(guān)節(jié)點的一種新的思考方法[J];微機(jī)發(fā)展;2002年04期

8 梅義;丘東元;張波;;基于深度優(yōu)先搜索的潛在電路計算機(jī)輔助分析法[J];中國電機(jī)工程學(xué)報;2008年24期

9 姚佳;譚學(xué)琴;;利用深度優(yōu)先搜索實現(xiàn)無線頻率規(guī)劃[J];電腦編程技巧與維護(hù);2014年08期

10 劉萍;馮桂蓮;;圖的深度優(yōu)先搜索遍歷算法分析及其應(yīng)用[J];青海師范大學(xué)學(xué)報(自然科學(xué)版);2007年03期

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

1 張洪波;楊海峰;王進(jìn)杰;;CAPP和PCCAD中工藝樹的規(guī)劃與建立[A];制造業(yè)與未來中國——2002年中國機(jī)械工程學(xué)會年會論文集[C];2002年

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

1 鄭丹;流體網(wǎng)絡(luò)中單向回路問題的研究[D];遼寧工程技術(shù)大學(xué);2004年

2 石佳玉;基于時延特性的網(wǎng)絡(luò)拓?fù)渫茢嗉夹g(shù)研究[D];蘭州交通大學(xué);2014年

，

本文編號：2269462