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

项目名称： 基于分层图的海量图数据并行编程方法研究

项目编号： No.61402445

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 王蕾

作者单位： 中国科学院计算技术研究所

项目金额： 26万元

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

中文关键词： 分布式图计算；延迟数据一致性；异步并行；冗余消除；

英文摘要： 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

英文关键词： Distributed graph computation；Lazy data coherency；asynchronous parallel；redundancy elimination；