ISSN 1000-1239 CN 11-1777/TP

• 软件技术 •

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

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.