Accelerating graph pattern mining algorithms on modern graphics processing units

Graphical processing units (GPUs) have been widely used as a general-purpose processing unit. More recently, there has been fast growing interest in accelerating graph pattern mining tasks on GPUs. At the core of graph pattern mining, graph pattern matching (GPM) is a fundamental operation that aims to find patterns of interest in large data graphs. GPM is typically performed by traversing search trees starting at each vertex in the graph and looking for neighborhood subgraph patterns of interest. A search tree in GPM has a depth equal to the number of vertices in the pattern graph. Each path from the root of a search tree to one of the leaves defines a potential mapping from the pattern graph vertices to a group of neighboring vertices in the data graph. Patterns can be of different sizes and shapes, such as triangles, cliques, wheels, cycles, etc. The larger the pattern size is, the deeper the search tree is. Searching for patterns in graphs is known to be hard due to the exponential growth of intermediate results and the number of instances of patterns. Therefore, execution time and memory requirements grow exponentially with the pattern size. State-of-the-art GPU solutions for GPM traverse the search trees using the Breath-First Search (BFS) approach that exhibits high degrees of parallelism at the cost of high memory requirement, and presents a great challenge for processing large graphs and patterns since the memory capacity of GPUs is significantly smaller than that of CPUs. This work presents novel techniques to implement GPM tree traversal efficiently on GPUs. The tree traversal presented herein uses a hybrid breadth-first and depth-first approach where the top level(s) of the search trees are traversed in a fully parallel, breadth-first manner while each subtree is traversed in a more space-efficient, depth-first manner. The depth-first traversal of subtrees requires less memory but presents more challenges for parallel execution. The techniques presented in this work overcome the less parallel nature of depth-first traversal by exploring vertex-centric and edge-centric parallelization schemes, using multi-level hierarchical organization of threads, improving to the set intersection operation that is fundamental to graph pattern mining algorithms, improving fine-grain parallelism using sub-warp partitioning, and replacing the depth-first recursive traversal with an iterative traversal based on an explicitly-managed shared stack. Moreover, various optimizations are applied to reduce memory consumption and improve data structure reuse. The effectiveness of the proposed techniques is demonstrated using four fundamental graph pattern mining algorithms: (a) subgraph matching for exact GPM for arbitrary patterns, (b) k-clique counting, (c) maximal clique enumeration, and (d) triangle counting. The detailed evaluation results show that the proposed GPU solutions substantially improve performance compared to existing state-of-the-art CPU and GPU solutions. The implementations presented in this thesis can efficiently process the graphs that previously cannot be processed by the state-of-the-art GPU solutions due to their excessive memory requirement. Detailed evaluations of the trade-offs involved in the choice of parallelization scheme, and the incremental speedup of each optimization to provide an in-depth understanding of the optimization space, are provided. The insights from the proposed optimization flow in this work can be useful for optimizing graph mining solutions on GPUs.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• AlMasri, Mohammad Abed Alnaser

Contributors dc:contributor

• Hwu, Wen-mei
• Chen, Deming
• Xiong, Jinjun
• Nagu, Rakesh
• Patel, Sanjay

• GPU
• CUDA
• Graph
• Graph Pattern Mining
• Graph Pattern Matching
• Clique
• Maximal Clique
• Triangle Counting
• Subgraph Matching
• Graph Analysis

Statement dc:rights

• Copyright 2022 Mohammad Almasri

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/115439

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F115439