基于众核平台子图匹配算法研究

《基于众核平台子图匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于众核平台子图匹配算法研究王峰2016年1月中图分类号：TP391UDC分类号：004.9基于众核平台子图匹配算法研究作者姓名王峰学院名称计算机学院指导教师祝烈煌教授答辩委员会主席周永彬申请学位工学硕士学科专业计算机科学与技术学位授予单位北京理工大学论文答辩日期2016年1月7日ResearchofMany-core-basedSubgraphMatchingAlgorithmCandidateName：WangFengSchoolorDepartment:SchoolofComputerScienceF

2、acultyMentor:Prof.ZhuLieHuangChair,ThesisCommittee：ZhouYongbinDegreeApplied:MasterofScienceMajor：ComputerScience&TechnologyDegreeby:BeijingInstituteofTechnologythTheDateofDefense：7,January,2016研究成果声明本人郑重声明：所提交的学位论文是我本人在指导教师的指导下进行的研究工作获得的研究成果。尽我所知，文中除特别标注和致

3、谢的地方外，学位论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京理工大学或其它教育机构的学位或证书所使用过的材料。与我一同工作的合作者对此研究工作所做的任何贡献均已在学位论文中作了明确的说明并表示了谢意。特此申明。签名：日期：摘要在大数据时代，信息的数量和复杂性呈几何式增长，因此信息的表示也变得愈加复杂。图作为一种常用的建模模型，提供了一个很自然的数据结构，可以对自然科学和社会科学中许多领域的问题进行恰当的描述和建模。因此图在大数据时代中发挥着不可替代的作用。在大规模图中，能够高效地对数据进

4、行挖掘，检索出所需要的部分对于信息的处理有非常重要的意义。但传统的CPU硬件平台很难提供高效的计算速率。在高性能计算领域，GPU众核设备由于具有线程多，并行度高的特点，成为主流众核计算平台。为此，本文通过GPU众核平台，实现高效率的子图匹配算法。算法首先通过GPU在大图中搜索出与查询图的中心节点具有相同性质的节点，然后在以这些节点为中心，查询图的半径长度为半径，使用众核的最短路径算法，在大图上截取待匹配子图。然后再使用众核对所获得待匹配子图与查询图进行匹配操作。本算法的主要工作如下：（1）在截取子图的过程中

5、，针对大规模图的最短路径（SSSP）问题，本文提出了把节点度值统一化的数据预处理操作，图数据经过预处理，GPU中每个线程的任务量相同从而减少了计算资源的浪费。图数据经过度值统一化操作后，又经过一次转置操作，提升了线程读取内存地址凝聚性，从而提高了SSSP的计算速率。（2）我们提出了数据块迭代的计算方法，来替代传统方法中通过原子操作对全局变量的进行读写操作以避免“写后写”错误，数据块迭代计算的方法既保证了结果正确性，又能提升计算速率。（3）在子图匹配过程中，我们采用通过邻居连接信息进行节点匹配判定的VF2算法

6、，使用众核设备并行对多个待匹配节点对使用VF2算法，实现子图匹配过程的加速。关键词：GPU；最短路径问题；统一度；子图匹配；VF2算法。IAbstractInthetimeofbigdata,thescaleandcomplexityofinformationareinexponentialgrowth.Therepresentationofinformationisbecomingmorecomplex.Graphprovidesanaturaldatastructure,asacommonmodel.S

7、o,graphplaysanirreplaceableroleinthetimeofbigdata.Inlargescalegraph,itisimportanttocarryoutdataminingandretrievetherequiredinformation.ItisdifficultfortraditionCPUhardwareplatformtoprovideefficientcomputingspeed.Intheareaofhighperformancecompute,GPUisacomm

8、onmany-coreplatformforitshighparallelismandmultiplethreads.Inthispaper,weimplementahighefficiencysubgraphmatchingalgorithmforlargescalegraphwiththeGPUplatform.Thealgorithmfirstfindsthevertexinthelargegraphwit