【作者】 王峰；

【导师】 祝烈煌；

【作者基本信息】 北京理工大学 ， 计算机科学与技术， 2016， 硕士

【摘要】 在大数据时代,信息的数量和复杂性呈几何式增长,因此信息的表示也变得愈加复杂。图作为一种常用的建模模型,提供了一个很自然的数据结构,可以对自然科学和社会科学中许多领域的问题进行恰当的描述和建模。因此图在大数据时代中发挥着不可替代的作用。在大规模图中,能够高效地对数据进行挖掘,检索出所需要的部分对于信息的处理有非常重要的意义。但传统的CPU硬件平台很难提供高效的计算速率。在高性能计算领域,GPU众核设备由于具有线程多,并行度高的特点,成为主流众核计算平台。为此,本文通过GPU众核平台,实现高效率的子图匹配算法。算法首先通过GPU在大图中搜索出与查询图的中心节点具有相同性质的节点,然后在以这些节点为中心,查询图的半径长度为半径,使用众核的最短路径算法,在大图上截取待匹配子图。然后再使用众核对所获得待匹配子图与查询图进行匹配操作。本算法的主要工作如下:(1)在截取子图的过程中,针对大规模图的最短路径(SSSP)问题,本文提出了把节点度值统一化的数据预处理操作,图数据经过预处理,GPU中每个线程的任务量相同从而减少了计算资源的浪费。图数据经过度值统一化操作后,又经过一次转置操作,提升了线程读取内存地址凝聚性,从而提高了SSSP的计算速率。(2)我们提出了数据块迭代的计算方法,来替代传统方法中通过原子操作对全局变量的进行读写操作以避免“写后写”错误,数据块迭代计算的方法既保证了结果正确性,又能提升计算速率。(3)在子图匹配过程中,我们采用通过邻居连接信息进行节点匹配判定的VF2算法,使用众核设备并行对多个待匹配节点对使用VF2算法,实现子图匹配过程的加速。更多还原

【Abstract】 In the time of big data, the scale and complexity of information are in exponential growth. The representation of information is becoming more complex. Graph provides a natural data structure, as a common model. So, graph plays an irreplaceable role in the time of big data. In large scale graph, it is important to carry out data mining and retrieve the required information. It is difficult for tradition CPU hardware platform to provide efficient computing speed. In the area of high performance compute, GPU is a common many-core platform for its high parallelism and multiple threads. In this paper, we implement a high efficiency subgraph matching algorithm for large scale graph with the GPU platform. The algorithm first finds the vertex in the large graph with the same properties as the central vertex of the query graph by GPU. And then we taking these found vertices center vertex, intercept subgraphs in the large graph by the algorithm of single source shortest path. Last we try to match the intercepted graphs to the query graph and confirm which one can be matched properly. The main work accomplished in this paper is as the following:(1)In the process of intercepting subgraphs, we propose a “unidegree” data preprocess. After the preprocess, data will be of better locality and threads’ work will be balanced. Another preprocess is the data transfer, the transmission delay time will be reduced by which.(2)In the parallel GPU program, atomic operation is used to avoid write and read error. However, the atomic operations down the compute speed. So we propose to use “data block iteration” instead of atomic operation. Data block iteration not only guarantees the accuracy but also improves the compute speed.(3)In the process of subgraph matching, we not taking too much pre-calculate, just make full use of the GPU’s many-core, match each pair vertex by VF2 algorithm concurrently to speed up the process of match.更多还原