Distributed heterogeneous systems for large-scale graph processing

Abstract

Graph processing is increasingly popular in a variety of scientific and engineering domains. Consequently, graphs and graph-processing algorithms have become increasingly more diverse. Following the big data trend in every computer-related domain, graphs have also become increasingly larger. Processing graphs is requiring more sophisticated computer systems. Important for this thesis, graph-processing systems now need to combine scalability (a grand challenge in computer science) and raw processing power (an endless race), with efficiency especially in cost and energy requirements (a difficult to define and ensure non-functional property for computer systems). New trade-offs between these elements are offered by two important trends in computer systems. First, distributed systems have grown in popularity and cost-efficiency. Second, GPUs offer an excellent performance-energy ratio and are included in most modern computers. By combining distributed CPU-based systems and non-distributed GPU-enabled systems into distributed heterogeneous systems, large-scale graph processing may become possible and efficient. However, many challenges still exist in the area of graph processing before distributed heterogeneous systems can be well understood. In this thesis, we conduct fundamental and applied research to address three major challenges in three research directions of graph processing: application (understanding new data characteristics and sharing graphs), knowledge (evaluating and comparing the performance of various graphprocessing systems), and design (designing new partitioning policies and entire graphprocessing systems that can use both CPUs and GPUs on multiple machines).