Automatic Partitioning of Very Large Graphs to Optimize Distributed Graph Processing

为了分析大型图形，例如web图形或社交网络，采用分布式图形处理系统，其中许多计算节点以分布式方式并行地在图形的不同分区上执行图形处理算法。作为预处理步骤，必须将图划分为几个不相交的部分，这些部分分布在计算节点上。在这样做的过程中，图的质量，即通过图的低切割尺寸，对分布式图处理的性能至关重要。然而，产生高质量的图分区是一个具有挑战性和计算密集型的问题。在分区上投入多少资源和时间取决于各种因素，例如图大小、用户的资源预算以及在分区图上进行后续图处理的复杂性和运行时间。现有的图划分框架不够灵活，无法解决这个优化问题。它们既不能适应投入到图分区中的资源量，也不能适应投入到图分区中的运行时。我们的研究目标是开发一个图分区框架，它可以自动适应给定的图处理问题，从而最小化图分区和图处理的总运行时间。为了实现这一目标，我们解决了以下两个研究挑战：(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.