基于动态差异化策略的高效大规模图计算系统研究

Many big-data applications such as social computing, pattern recognition, recommendation systems and natural language processing can be expressed using graph-structured computation. This also raises grand challenges to building large-scale graph-computation systems, including graph partitioning algorithms, programming models and computation engines. However, existing graph-computation usually uses a singular policy to handle large-volume graph data with variety and velocity properties, resulting in usually suboptimal usages of underlying processing resources. This project aims at investigating the use of dynamic and differentiated strategies to provide highly efficient graph-computation systems. Specifically, this project plans to combine offline analysis and online sampling, as well as approaches such as neural networking and efficiency modeling, to build systems that are aware of the dynamic properties of graph data. Meanwhile, for graph computation with different data, application and load, this project will design a variety of partitioning algorithms, programming models and computation engines, with the goal of maximizing data locality and parallelism during graph processing and being orthogonal with other optimizations on existing graph systems. The research results of this project will provide a strong basis to build large-scale graph-computation systems and assist the analysis of complex correlated data in the Big-Data era.

许多大数据应用如社交计算、模式识别、推荐系统和自然语言处理等均可以通过大规模基于图数据结构的计算进行处理，这也对如何构建大规模的图计算系统从划分算法、编程模型和计算引擎等方面的设计与实现提出了全新的挑战。然而，现有图计算系统大多采用单一性策略，缺乏对图计算中数据、算法和负载的多样性的支持，因而对目前具有种类多和变化快等特征的图数据未能充分挖掘系统效能。本项目将研究基于动态差异化策略的高效图计算系统，拟结合离线剖视和联机抽样等手段，以及神经网络和效能建模等技术，研究高效的动态特征感知方法；同时针对不同特征的图数据、应用和负载，设计并融合不同划分算法、编程模型和计算引擎的策略，充分挖掘图计算过程中的数据局部性和计算并行性，并兼容于现有面向单一策略的优化方法。项目的研究成果将为构建高效的大规模图计算系统提供有力支持，对大数据时代的复杂关联数据的分析研究起到积极的推动作用。

许多大数据应用如社交计算、模式识别、推荐系统和自然语言处理等均可以通过大规模基于图数据结构的计算进行处理，这也对如何构建大规模的图计算系统从划分算法、编程模型和计算引擎等方面的设计与实现提出了全新的挑战。然而，现有图计算系统大多采用单一性策略，缺乏对图计算中数据、算法和负载的多样性的支持，因而对目前具有种类多和变化快等特征的图数据未能充分挖掘系统效能。本项目的研究目标是构建基于动态差异化策略的高效图计算系统。 具体包含以下主要研究工作：. .首先，我们发现现有图计算系统通常采用“一刀切”的设计来处理数据分布不均匀的图，从而导致了负载不均、数据竞争、频繁通信和高内存开销等一系列性能问题。本项目提出了一种基于差异化思想的混合图计算系统，能够动态的为图数据中具有不同特征的顶点选择最适合的计算模型和划分算法。使用典型图计算应用和机器学习应用的详细测试表明，差异化策略能够带来高达5.5倍的性能提升和更少的内存占用。 . .其次，图算法本身的迭代和收敛特征导致现有图计算系统存在两种不同的计算模式：即同步和异步。然而当前尚缺少对于不同执行模式特点的深入研究，导致程序员必须手动选择适合的执行模式或者忍受性能损失。本项目给出了对两种图计算执行模式的首个详细评测和分析，并在此基础上提出了一种混合图计算执行模式，通过在线取样和离线剖视技术能够在两种模式间实现动态自主切换。该方法相比最优的单一执行模式（同步或异步）能够获得7%至73%的性能提升。 . .最后，本项目还进一步的挖掘高性能硬件特性（如，NUMA、HTM和RDMA等）对在线内存计算系统进行了大量优化探索，并获得了一个数量级以上的性能提升，其中包括面向NUMA架构的图计算系统、分布式事务处理系统和并发图查询系统等。 . .项目的研究成果将为构建高效的大规模图计算系统提供有力支持，对大数据时代的复杂关联数据的分析研究起到积极的推动作用。