ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (2): 431-441.doi: 10.7544/issn1000-1239.2019.20170902

• 软件技术 • 上一篇    下一篇

图计算中基于一致性约束条件的迭代模型研究

孙茹君1,张鲁飞1,郝子宇1,陈左宁2   

  1. 1(数学工程与先进计算国家重点实验室 江苏无锡 214125); 2(国家并行计算机工程技术研究中心 北京 100190) (sun.rujun@meac-skl.cn)
  • 出版日期: 2019-02-01
  • 基金资助: 
    国家自然科学基金项目(9143020017);国家重点研发计划项目(2017YFB0202001)

Consistency Based Iterating Models in Graph Computing

Sun Rujun1, Zhang Lufei1, Hao Ziyu1, Chen Zuoning2   

  1. 1(State Key Laboratory of Mathematical Engineering and Advanced Computing, Wuxi, Jiangsu 214125); 2(National Research Center of Parallel Computer Engineering and Technology, Beijing 100190)
  • Online: 2019-02-01

摘要: 迭代计算是数值计算中有效的逼近方式,能够拟合多种计算模型.在大数据分析领域尤其是图计算中,迭代计算能够抽象描述大部分图算法,对结构化数据挖据和关联分析至关重要.随着数据规模的增长,很多精确算法的时空复杂度已经难以满足现实需求,迭代计算的算法越来越丰富.并行迭代是图计算的主要实现形式,已有的图并行策略大多数是同步模型,少量异步模型,对于一致性约束条件下的迭代研究较少.研究内容重点关注图计算模型中迭代执行技术,分析了同步迭代和异步迭代的适用性,以及不同一致性下的异步迭代方式,针对已有异步迭代方式的不足提出了自适应的弱一致异步执行模型,并进行了验证性实验.实验证明:该模型能有效提高部分图算法的执行效率,尤其是收敛速度和效果.

关键词: 图计算, 图迭代, 分布式计算, 同步迭代, 弱一致异步迭代

Abstract: The time and space complexity of many accurate algorithms is difficult to meet the realistic demands, while approximating algorithms are alternative choices. Iterative computing is an effective approximating method in numerical computing. A variety of algorithms and models can be classified into it. With the increase of data scale, iterative algorithms are blooming and developing. Graph computing is a natural way to express and analyze relationships. There are numerous graph algorithms being described as iterative models. Parallel iterating is regular in large graph computing. Graph iterating methods have different parallel execution models. Most of the existing parallel graph computing implementations are synchronous, and a few of them are asynchronous models. However, there are few studies about consistency constraints in graph iterating. In this paper, we discuss the iterative computing technique in graph computing model. We analyze the applicability of synchronous and asynchronous iterations, and study the asynchronous iterative methods under different consistency, as well as experimental proving. We propose an adaptive asynchronous execution model which is weakly consistent. It overcomes the shortcomings of existing asynchronous iterative methods. Experiments of this model were done in parallel and have shown that the model can effectively improve some graph algorithms, especially the iterating and converging speed.

Key words: graph computing, graph iteration, distributed computing, synchronous iterating, weakly consistent asynchronous iterating

中图分类号: