论文部分内容阅读
图(graph)作为最基本的数据结构之一,在生物信息学、化学数据分析、社交网络研究以及程序bug检测等众多应用领域被用于构建和表示对象之间的复杂关系。随着这些应用领域的不断发展,图数据挖掘作为这些应用领域的关键基础工具,重要性日益凸显,涉及领域和内涵不断扩展。由于这些领域应用图数据规模的不断增长,而且大多数图处理算法具有很高的计算复杂度,因此大规模的图数据挖掘急需高性能计算研究的支持。近些年来,相对通用CPU计算平台GPU异构计算平台由于在计算能力、访存带宽、性能功耗比方面的明显优势,逐渐被广泛的应用于众多通用计算领域,也为高效的处理大规模图数据提供了机遇。本文针对大规模图数据挖掘领域的几类重要问题,其中包括:图遍历、图分析、图同构与图挖掘,研究了其典型算法在GPU平台上的细粒度并行问题,提出了相应的基于GPU的并行算法,集中解决了基于GPU的细粒度并行算法设计中面临的若干技术难点,达到了提高大规模图数据挖掘性能的目的。本文取得的重要研究成果如下:1.基于GPU的大规模图遍历研究本文提出了基于优化的顶点前沿队列的GPU广度优先搜索算法,解决了已有基于顶点前沿队列的并行广度优先搜索算法在每层迭代内两个阶段中遇到的性能瓶颈。主要包括:针对已有算法邻居收集过程中采用的prefix-sum和warp-centric任务调度方法在GPU Warp内出现负载不均衡问题,提出了基于虚拟队列的任务调度方法更好的缓解邻居收集过程中的负载不均衡问题;其次针对已有的边前沿队列局部去重方法的不足,提出了一种新的全局去重方法,完全剔除边前沿队列的重复顶点,另一方面针对无尺度图的广度优先遍历中某几次迭代中边前沿队列冗余顶点多的问题,提出了一种正向和逆向混合的遍历方法,有效的减少了对冗余顶点的遍历。实验结果表明,本文提出的算法相对目前性能最好的GPU广度优先搜索算法Merrill算法,在基于Nvidia K40c GPU的异构计算平台上最高获得了3.2倍的性能加速比。2.基于GPU的大规模图分析研究本文提出了一种基于GPU的图中介中心度计算算法。针对中介中心度计算过程中的最短路径计算阶段和相关度累加阶段,首先结合前一章提出的基于虚拟队列的任务调度方法和全局去重方法给出一种基于前沿队列的方法,有效的解决了已有的基于前沿队列方法中遇到的负载不均衡问题,同时消除了其对原子操作的使用。此外,提出一种基于收集的最短路径数目计算方法,消除了最短路径数目统计中的数据竞争。其次,提出一种改进的基于顶点并行的方法,解决了已有基于顶点并行方法负载不均衡问题。最后,提出一种混合方法,有效的整合了前面两种算法各自的优势。实验结果表明,本文提出的算法相对目前性能最好的GPU中介中心度计算算法Mc-Sampling算法,在基于Nvidia K40c GPU的异构计算平台上获得了1.2-1.9倍的性能加速比。同时,该算法还具有良好的可扩展性。3.基于GPU的大规模子图同构查询研究本文首次提出了一种基于图遍历的GPU子图同构算法,该算法使用区域遍历方法确定匹配顺序,主要由GPU区域遍历和GPU子图匹配两部分组成。工作主要包括:首先,针对区域遍历过程,基于深度优先遍历过程中形成的部分子树映射树中不同分支上顶点(部分子树映射)之间的独立性和不同分支控制流的相似性,给出了一种递归计算模式的数据集细粒度并行方法,提出了一种细粒度的数据级并行的区域遍历算法,同时给出了一种高效的面向并行区域遍历的用于存储候选顶点集合的数据结构。其次,针对子图匹配过程,利用子图匹配迭代中不同的部分子图映射的独立性,提出了一种基于候选顶点扩展的GPU子图匹配算法。最后,针对图的不规则性带来的区域遍历和子图匹配过程中负载不均衡问题,提出了两种负载均衡的任务分配策略。研究结果表明,相比目前性能最好的CPU子图同构算法TurboISO算法,在基于Nvidia K40c GPU的异构计算平台上,本文提出的GPU算法获得了1.4-2.6倍的加速比。4.基于CPU/GPU异构平台的频繁子图挖掘研究本文提出了一种基于CPU/GPU异构平台的gSpan频繁子图挖掘算法,有效的挖掘了gSpan算法的粗粒度和细粒度并行性。工作主要包括:首先,针对模式图扩展,提出一种基于虚拟队列的并行子图映射扩展算法,解决了已有并行子图映射扩展的负载不均衡问题。其次,针对扩展边的支持度计算,提出两种相比已有方法时间复杂度更低的并行支持度计算算法,基于数据图收集的方法和基于扩展边排序的方法,分别用于处理两种不同类型图数据集的支持度计算。然后,针对最小DFS编码验证可并行性低的问题,提出了一种基于CPU的粗粒度并行的最小DFS编码验证算法,此外给出一种负载均衡的流水线协同计算方式,有效隐藏了CPU/GPU间通信开销。最后,针对子图映射的生长,给出一种并行子图映生长算法。相比经典的gSpan算法和已有的基于GPU的gSpan算法,在基于Intel E5-2670 CPU和Nvidia K40c GPU的异构计算平台上,本文提出的基于GPU的频繁子图挖掘算法最高分别获得了17倍和3.7倍的性能加速比。