Automatic Partitioning of Very Large Graphs to Optimize Distributed Graph Processing

为了分析诸如网络图或社交网络之类的大图，使用分布式图处理系统，其中多个计算节点在图的不同分区上以分布式方式并行执行图处理算法。作为预处理步骤，图必须被划分成分布在计算节点上的几个不相交的部分。在这样做的过程中，图的质量，即通过图的低切割大小，对分布式图处理的性能至关重要。然而，获得高质量的图划分是一个具有挑战性和计算密集型的问题。在分区中投入多少资源和多少时间取决于各种因素，例如图的大小、用户的资源预算以及在分区的图上后续图处理的复杂性和运行时间。现有的图划分框架不够灵活，无法解决该优化问题。它们既不能适应用于图分区的资源量，也不能适应投资于图分区的运行时。我们的研究目标是开发一个图划分框架，该框架能够自动调整其配置以适应给定的图处理问题，从而最小化图划分和图处理的总运行时间。为了实现这一点，我们解决了以下两个研究挑战：(I)灵活图划分概念的发展和(Ii)组合图划分和分布式图处理问题的整体优化。对于第一个研究挑战，我们将现有的图划分算法扩展到在有限内存上工作，在有限的时间内提供一个图划分结果，并有效地利用图形处理单元(GPU)的硬件加速。利用我们的研究在图划分方面获得的更大的灵活性，然后我们解决了第二个研究挑战。现有的图形处理系统将直接受益于我们的研究贡献。此外，所开发的灵活图划分的概念也可以应用于处理图结构数据的相关系统，例如图形数据库。

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.