A survey on dynamic graph processing on GPUs: concepts, terminologies and systems  

作　　者：Hongru GAO Xiaofei LIAO Zhiyuan SHAO Kexin LI Jiajie CHEN Hai JIN 

机构地区：[1]National Engineering Research Center for Big Data Technology and System/Services Computing Technology and System Lab/Cluster and Grid Computing Lab,School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China [2]Zhejiang Lab,Hangzhou 311121,China

出　　处：《Frontiers of Computer Science》2024年第4期1-23,共23页中国计算机科学前沿（英文版）

基　　金：National Natural Science Foundation of China(Grant Nos.61972444,61825202,62072195,and 61832006);Zhejiang Lab(2022P10AC02).

摘　　要：Graphs that are used to model real-world entities with vertices and relationships among entities with edges,have proven to be a powerful tool for describing real-world problems in applications.In most real-world scenarios,entities and their relationships are subject to constant changes.Graphs that record such changes are called dynamic graphs.In recent years,the widespread application scenarios of dynamic graphs have stimulated extensive research on dynamic graph processing systems that continuously ingest graph updates and produce up-to-date graph analytics results.As the scale of dynamic graphs becomes larger,higher performance requirements are demanded to dynamic graph processing systems.With the massive parallel processing power and high memory bandwidth,GPUs become mainstream vehicles to accelerate dynamic graph processing tasks.GPU-based dynamic graph processing systems mainly address two challenges:maintaining the graph data when updates occur(i.e.,graph updating)and producing analytics results in time(i.e.,graph computing).In this paper,we survey GPU-based dynamic graph processing systems and review their methods on addressing both graph updating and graph computing.To comprehensively discuss existing dynamic graph processing systems on GPUs,we first introduce the terminologies of dynamic graph processing and then develop a taxonomy to describe the methods employed for graph updating and graph computing.In addition,we discuss the challenges and future research directions of dynamic graph processing on GPUs.

关 键 词：dynamic graphs graph processing graph algorithms GPUS 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP391.3[自动化与计算机技术—控制科学与工程]