面向结构演化的动态增量图计算性能优化方法研究

As the era of “big data” is coming, the scale of complex and related data, represented as graphs, are increasing rapidly, and propose big performance challenges on graph computation. Traditional batch processing-based frameworks exist issues such as redundant computation and low resource utilization, which result high spatial-temporal overheads. Therefore, how to make performance optimization in dynamic graph streams by approaches such as incremental computation reuse, replication-based data sharing has become a key issue. To improve the efficiency of parallel job execution and resource utilization, this project leverages the features of graph data, computing resources and job characteristic, and aims to perform research on three aspects:(1) The spatial-temporal locality based incremental computation reuse; (2) The key graph characteristic based performance self-optimization; (3) The hierachical resource sharing framework based system run-time optimization. Overall, the achievements of this project can be applied into real graph computing platform. In addition, it could support higher system throughput and less job response time, as well as resource utilization and fairness.

随着大数据时代的兴起，以图为代表的复杂关联数据规模正在急剧增长，这对现有图计算框架处理能力提出了严峻挑战。传统图处理架构主要基于批处理方式，存在冗余计算，资源利用率低等问题，难以适应动态图计算的时空开销需求。因此，如何根据动态图流特征，通过计算复用、副本数据共享等方法提高性能，为图系统提供高效、易用的运行时优化成为图计算系统面临的关键科学问题。为了提高图计算系统的作业执行效率与资源利用率，本项目综合分析图数据、计算资源和作业特点，从以下三个层面展开研究：(1)基于时空局部性的增量复用问题；(2)基于关键图特征的性能自动优化问题；(3)基于分层资源共享框架的运行时优化问题。本项目的研究成果可直接应用于真实的图计算系统，能够提高图系统的吞吐率和作业响应时间、资源的利用率和公平性。

近年来，随着各类交互型应用的快速发展，图类数据大量增长，如何面向动态图场景设计高效的并行计算模型和算法是该领域目前面临的关键课题。本项目面向图结构动态增加的场景，研究了能有效提升并行计算中图处理效率的方法。本研究从图算法关键特征提取和并行系统瓶颈优化两个方面展开研究，以现有的图并行计算系统架构为基础，结合图的关键特征进行性能优化。首先，基于日志合并树设计了一种适合动态场景的图数据存储方法。然后使用并行图摘要算法对图的多种关键特征进行抽取以简化计算。另外，我们还提出了一种分层并行的混合图计算模型，并基于开源图系统进行实现，并验证了方法的有效性。本项目的研究成果不仅可以提升并行系统下的图计算性能，同时可作为一种通用的特征抽取和性能优化方法，为大图处理领域提供新的思路，可应用于知识图谱、图数据库和并行计算等相关领域。