基于分层图的海量图数据并行编程方法研究

With the rapid growth of the Internet and social networks, graph data scale is increasing dramatically and graph algorithms are getting more and more important. Due to the lack of a distributed graph computing framework, the information of social network data is far from well used. How to efficiently handle massive graph data with complex relationships and improve graph computing efficiency is a challenging research problem. This proposal takes typical graph applications as the example, 1) to control global communication overhead, proposes hierarchy graph based parallelism and the mapping mechanism to support hierarchical parallelism. This mapping mechanism uses three types of parallel mode and hierarchical management of computing resource and dynamically maps hierarchical parallelism to hardware parallel unit. Due to the increased parallelism and reduced global communication, the running efficiency is improved. 2) To improve efficiency of computing resource usage, proposes master-tail parallel method based on graph minor and the way of using MPMD parallel mode to reduce graph data scale using extra computing resource. 3) An abstraction of parallel programming interface that simplifies distributed parallel programming and improve programming efficiency.

随着互联网和社会网络的迅猛发展，图数据规模越来越大，图算法越来越重要。由于缺乏分布式图计算框架，导致社会信息网络数据的价值远远没有发挥出来。如何高效处理具有复杂关系的海量图数据以及提高图计算的编程效率是一个具有挑战性的研究问题。本项目以典型图应用为驱动，1.针对全局通信开销难以控制的问题，提出基于分层图的层次并行方法，研究支持层次并行的映射机制。该映射机制通过三种并行模式和分层的计算资源管理，将层次并行度动态映射到硬件并行单元上高效执行。由于能挖掘更多并行度，把全局通信转化为局部通信，从而提高计算效率。2.针对计算资源利用率低的问题，提出基于缩图的主裁并行方法，研究支持MPMD并行模式，用额外的计算资源来进行图规模缩减，由于数据规模大幅度减少，从而降低通信量，提高计算效率。3.在上两个工作之上，抽象出一套简洁的高层并行编程接口，简化分布式并行编程，适用更多图应用，提高编程效率。

随着互联网和社会网络的迅猛发展，图数据规模越来越大，图算法越来越重要。由于缺乏分布式图计算框架，导致社会信息网络数据的价值远远没有发挥出来。如何高效处理具有复杂关系的海量图数据以及提高图计算的编程效率是一个具有挑战性的研究问题。本项目以典型图应用为驱动，1.针对全局通信开销难以控制的问题，提出基于分层图的层次并行方法，研究支持层次并行的映射机制。该映射机制通过三种并行模式和分层的计算资源管理，将层次并行度动态映射到硬件并行单元上高效执行。由于能挖掘更多并行度，把全局通信转化为局部通信，从而提高计算效率。2.针对计算资源利用率低的问题，提出基于缩图的主裁并行方法，研究支持MPMD并行模式，用额外的计算资源来进行图规模缩减，由于数据规模大幅度减少，从而降低通信量，提高计算效率。3.在上两个工作之上，抽象出一套简洁的高层并行编程接口，简化分布式并行编程，适用更多图应用，提高编程效率。项目执行顺利，完成了预期的研究目标，取得的研究成果包括：1. 提出一种面向分布式图计算的数据一致性延迟机制，能有效降低全局同步和通信开销；2. 提出一种基于并行边的消息传输机制，能够解决消息传输中的瓶颈；3. 提出一种图敏感的动态优化技术，能自适应动态调节全局同步频率，使得计算快速收敛；4. 提出一种分布式锁无关的异步并行方法和一种基于分层图的层次并行方法，通过负载均衡来提高计算资源利用率；5. 提出一种冗余计算消除的图计算优化技术，消除公共DAG子图带来的冗余计算，从而大幅度提高计算效率。 项目资助下在国内外著名会议和期刊上发表论文16篇，包括领域国际著名会议PPoPP2016、PPoPP2018、ICS2015、NPC2016等，国际著名期刊TC、TPDS、TSE、TACO、JSC等，国内核心期刊软件学报、计算机研究与发展等。申请专利3项，并基于PowerGraph构建分层图的海量图数据并行编程框架原型系统。通过本项目的研究，从一定程度上解决了分布式图计算编程框架的执行效率和编程效率。