动态图上的最短路径距离并行算法  

A Parallel Algorithm to Answer Shortest Distance on Dynamic Graph

作　　者：韩硕 邹磊[1] HAN Shuo;ZOU Lei(Institute of Computer Science and Technology of Peking University,Beijing 100080)

机构地区：[1]北京大学计算机科学技术研究所

出　　处：《北京大学学报（自然科学版）》2020年第1期112-122,共11页Acta Scientiarum Naturalium Universitatis Pekinensis

摘　　要：设计动态图上最短路径距离查询的并行计算框架。通过构建增量图的方法,实现一个批次内的多个查询在不同数据图版本的多线程并发执行。对于每个查询,使用双向宽度优先搜索算法来减少搜索空间,并提出搜索过程中扩展方向的决策函数。利用BSR对数据图邻接表进行编码,结合SIMD指令和图顶点重标号算法,进一步提升数据级并行度。在真实图数据集下的大量实验验证了所提方法的高效性。The paper presents a parallel algorithm framework to answer shortest distance queries on dynamic graphs.Based on maintaining a delta graph,multiple queries within a batch are executed in parallel over different versions of data graph by multi-threading.For each query,bidirectional breath-first search(BFS)is utilized to reduce search space.During the search process,an exploration direction decision-making function is proposed.Furthermore,adjacency-lists of data graph are encoded by BSR layout,combined with SIMD instructions and graph reordering algorithm,higher degree of data-level parallelism is achieved.Extensive experiments on real graph datasets confirm the superior efficiency of the proposed solution.

关 键 词：动态图 最短路径距离 增量图 线程级并行 数据级并行 双向宽度优先搜索 SIMD 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]