gpu加速技术在图论算法中的应用

《gpu加速技术在图论算法中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、论文题目GPU加速技术在图论算法中的应用学科专业计算机应用技术学号201021060326作者姓名王一同指导教师文军副教授分类号密级注1UDC学位论文GPU加速技术在图论算法中的应用（题名和副题名）王一同（作者姓名）指导教师文军副教授电子科技大学成都（姓名、职称、单位名称）申请学位级别硕士学科专业计算机应用技术提交论文日期2014.04.30论文答辩日期2014.05.20学位授予单位和日期电子科技大学2014年6月日答辩委员会主席评阅人注1：注明《国际十进分类法UDC》的类号。APPLICATIONOFGPUACCELERATI

2、ON TECHNOLOGYINGRAPHALGORITHMSAMasterThesisSubmittedtoUniversityofElectronicScienceandTechnologyofChinaMajor:ComputerApplicationTechnologyAuthor:WangYitongAdvisor:WenJunSchool:SchoolofComputerScience&Engineering独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注

3、和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。作者签名：日期：年月日论文使用授权本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后应

4、遵守此规定）作者签名：导师签名：日期：年月摘要摘要图数据是许多计算、科学和工程领域中经常采用的数据结构，图操作则是构建这些领域中许多应用的基石。一直以来，设计高效的图算法就是数学与计算机科学的重要研究内容。随着算法理论的成熟，研究人员意识到传统的串行图算法几乎已达到理论上的时间复杂度极限，它们在生物基因工程、Web网络分析、地理信息系统等新兴应用产生的海量数据前遭遇到性能瓶颈。开发并行的图算法势在必行。然而，大多数研究集中在以CPU为处理部件的传统并行架构上，受到处理器核心数限制和通信代价方面的挑战。现代图形处理器（Graphic

5、ProcessingUnits，GPUs）具有运算核心数量多、运算能力强、高带宽的架构优势。近年来，利用GPU进行通用计算（GeneralPurposeComputationonGPU，GPGPU）成为高性能计算领域新的趋势。目前，GPGPU领域的图算法研究还处于起步阶段，图算法具有的不规则访存性增加了设计的难度。除此之外，也不是所有的图算法都能够被有效地并行，比如深度优先搜索本质上就是串行的。本文研究和归纳了在CPU和GPU上设计实现并行图算法的研究现状，分析了GPU上图的数据表示，开发了基于统一计算设备架构（ComputeUn

6、ifiedDeviceArchitecture，CUDA）的并行算法以用于求解强连通分量（SCC）、最小生成树（MST）以及每对顶点间的最短路径（APSP）等三种图问题。首先，本文实现了基于CUDA的计算SCC的FB算法，在算法中引入了枝剪过程，并考虑到了线程分歧的影响；接下来，设计了一种Kruskal算法和Boruvka算法相结合的混合MST算法，它使用基于CUDA的基数排序与前缀和Scan原语来划分子图、构造子图结构以及过滤边，并用Boruvka算法的CUDA实现来求解子图的最小生成树森林；然后，受到基于CUDA的单源最短路径

7、（SSSP）算法的启发，开发了一种利用SSSP求解APSP的并行方案，该方案一次求解多个源顶点的SSSP问题，能有效地利用GPU片上的共享内存。最后，本文以实验作为手段，测试了算法在不同规模的三种合成图Random、RMAT、SSCA#2上的性能，数据表明，这些基于CUDA的算法确实取得了一定的加速比。关键词：CUDA，强连通分量，最小生成树，每对顶点间最短路径IABSTRACTABSTRACTGraphsarepopulardatarepresentationsinmanycomputing,scientificandengin

8、eeringareas,graphoperationsarebuildingblockstomanyapplications.Designingefficientgraphalgorithmshasbeenanimportantresearchco