Efficient Processing of Large Irregular Graphs on GPUs and Multicores

Graph analytics is fundamental in unlocking key insights by mining large volumes of highly connected data. However, comparing to many other data analytics, it is difficult to perform graph analytics efficiently on modern computers due to three reasons. First, the structures of graphs are often highly irregular. For example, a small portion of vertices may own a large number of neighbors while most vertices have very few neighbors. The structure irregularity leads to computation irregularity, resulting in workload imbalance among worker threads. Second, real-world graphs tend to be large. It is oftentimes impractical to find individual machines with memory capacity that can accommodate such large graphs entirely, not to mention accelerators (like GPUs) which have more limited memory capacity. Third, it remains open questions how graph processing systems should be designed for emerging graph analytics, which often involves the tradeoff among multiple key factors, such as data locality, amount of parallelism, and computation redundancy. This thesis aims to address the above three challenges of graph processing under some specific contexts. First, it focuses on improving the performance of graph analytics on modern highly-parallel processors -- GPUs. Note that GPUs are conventionally designed for regular computations. To address the irregularity of graph computations, this thesis proposes a graph transformation technique that can convert irregular graphs into regular ones while preserving the correctness of the graph analytics. Second, this thesis further examines the performance bottleneck in processing oversized graphs that cannot fit into the memory of GPUs. It finds that the data movement between CPU and GPU is very costly. To address the issue, this thesis proposes a subgraph extraction technique which can dynamically extract the active parts of the graph in each processing iteration -- they are usually small enough to fit into the GPU memory. Finally, this thesis looks into an underexplored yet important graph application -- large-scale program analysis, and proposes to systematically exploit the design space of a graph system for this new application in order to realize its full potential