Parallel Graph Processing on GPUs

Abstract:

Graph is a useful data representation and has been used in various fields. Despite its great importance, graph processing is faced with difficult challenges: first, many graph algorithms are computation-intensive by nature; second, modern graphs are usually large and evolve rapidly. These make it difficult to achieve scalable and efficient graph processing. Recent advances in graphics processing units (GPUs), which can provide massive parallelism to accelerate computation, have brought new opportunities for graph processing. Therefore, in this thesis, we aim to design efficient solutions to accelerate graph processing on GPUs.

First, we study the parallel design of subgraph enumeration and propose a scheme that can reuse the results of set intersection operations to avoid repeated computation. Our scheme consists of two phases. In the first phase, we generate an execution plan that determines the opportunities of reusing available results. In the second phase, the plan is executed by our newly designed reusable parallel search strategy, which can efficiently maintain and retrieve the results of set intersection operations.

Even though our scheme can effectively improve the performance of subgraph enumeration, it can only search small graphs that fit into the GPU memory. Therefore, in the second work of this thesis, we design a novel framework that can scale to large graphs. The key idea of our framework is to treat all matched subgraphs of a given pattern, i.e., instances, into two categories, namely those within each partition of the graph and those across different partitions, and perform the searches for them separately. To accelerate the enumeration for the second category, we also introduce a shared execution approach to reduce the redundant subgraph searches.

Finally, in our third work of this thesis, we study personalized PageRank (PPR) on dynamic graphs and propose a parallel approach for dynamic PPR computation. Different from existing sequential approaches that perform computation on each single graph update, our approach can ingest the graph updates in a batch to reduce the synchronization cost among every single update and enable more parallelism for the iterative execution routine. To speed up the parallel processing, we also devise optimization techniques to accelerate the convergence and reduce synchronization overheads.