Design And Implementation Of Parallel Graph Processing Framework On GPUs

Graph is a powerful data structure, which can express the complex relations among things in the real world, for example, the road connections among cities, the references among web pages and the social relationship among people. Recent years witness the increasing adoption of GPGPU (general purpose computation on Graphic Processing Unit) in many applications. GPU can offer massively parallel threads, which are well-suited for the graph data, which claim to contain rich data concurrency. However, im-plementing an efficient graph application on GPU still faces formidable challenges, including the conflict between serialization and work complexity, the conflict between regularity and heterogeneity, and the complexity of GPU programming itself. This the-sis proposes a lightweight graph processing framework on GPU. The contributions this thesis achieved include:(1) Design and implement Olive, a GPU parallel graph programming framework. Olive offers a single data type vertexSubset (indicating a subset of vertices in the graph) and two sets of functions:(a) edgeFilter and edgeMap are used to conduct computation along edges.(b) vertexFilter and vertexMap are used to perform vertex-wise compu-tation. Programming with Olive is just invoking those two functions over a series of vertexSubsets. And all the underlying details are hidden behind. So the users focus only on the definition of computation and could know nothing about the GPU programming. The vertexSubset has two physical representations:a compact representation based on queue and a loose one based on boolean array. The work amount of edgeFilter can be can minimized if using compact vertexSubset as the input. And the parallelism can be improved by using loosely represented vertexSubset as the output. To validate the utility and the effectiveness of Olive, three commonly used graph algorithms (BFS, PageRank and Bellman-ford SSSP) are implemented by it. And the system performance is evalu-ated though experiments. The result shows that the speedup against serial version can achieve up to20x.(2) Study the link between the irregularity of graph and the efficiency of GPU SIMD. In edge computation(edgeFilter and edgeMap), the heterogeneity of input data will have great impact on the performance. To understand the implication, this thesis analyzes fifteen datasets from different application domains and models the relation between graph topology and SIMD utilization (of BFS as example). Due to the hetero-geneity of graph data structures in the real world, Olive adopts group mapping strategy and allows users to adjust the group size to find the optimal configuration. The experi-ments indicate that the strategy can improve the efficiency remarkably.