Automatic Partitioning of Very Large Graphs to Optimize Distributed Graph Processing

点击翻译按钮获取中文摘要

To analyze large graphs, such as web graphs or social networks, distributed graph processing systems are employed, where a number of compute nodes execute a graph processing algorithm in a distributed fashion in parallel on different partitions of the graph. As a preprocessing step, the graph must be partitioned into several disjoint parts that are distributed across the compute nodes. In doing so, the quality, i.e., a low cut size through the graph, is crucial to the performance of distributed graph processing. However, yielding high graph partitioning quality is a challenging and compute-intensive problem. How many resources and how much time to invest into partitioning depends on various factors such as the graph size, the resource budget of the user, and the complexity and run-time of subsequent graph processing on the partitioned graph. Existing graph partitioning frameworks are not flexible enough to solve that optimization problem. They can neither adapt the amount of resources nor the run-time that is invested into graph partitioning. The goal of our research is to develop a graph partitioning framework that automatically adapts its configuration to a given graph processing problem such that the total run-time of both graph partitioning plus graph processing is minimized. To make this possible, we tackle the following two research challenges: (I) development of concepts for flexible graph partitioning and (II) the overall optimization of the combined graph partitioning and distributed graph processing problem. Regarding the first research challenge, we extend current graph partitioning algorithms to work on constrained memory, to deliver a graph partitioning result within a time bound, and to effectively exploit hardware acceleration by graphics processing units (GPUs). Exploiting the increased flexibility in graph partitioning gained by our research, we then tackle the second research challenge. Existing graph processing systems will directly benefit from our research contributions. Further, the developed concepts on flexible graph partitioning can also be applied in related systems that deal with graph-structured data, such as graph data bases.