面向图计算内存系统的实现与拓展

Implementation and development of memory system for graph computing

图计算系统是处理大规模图数据的重要工具,在城市交通规划、社交网络分析、消费统计等领域都具有重要意义。针对传统的图计算算法无法高效处理大规模图数据与普通用户难以实现并行算法等问题,文中实现了多个并行图计算接口,使用push和pull的混合计算模型,拓展了原子操作,并基于Ligra图计算系统实现深度优先搜索及子图匹配算法。拓展后的并行图计算算法比传统的图计算算法提速1000倍左右。

Graph computing system is an important tool for processing large-scale graph data,which is of great significance in the fields of urban transportation planning,social network analysis,consumption statistics and other fields.Multiple parallel graph computing interfaces are used in this paper in view of the inefficiency of large-scale graph data processing by traditional graph computing algorithms and the difficulties of ordinary users in implementing parallel algorithms.The hybrid computing model of push and pull is used to expand the atomic operation.The depth priority search and sub graph matching algorithm are realized based on the Ligra graph computing system.The expanded parallel graph computing algorithm is about 1000 times faster than the traditional one.