Fast and efficient parallel breadth-first search with power-law graph transformation

查看全文 作　　者：Zite [1,2]JIANG;Tao [2]LIU;Shuai [1,2]ZHANG;Mengting [3]YUAN;Haihang [2]YOU 机构地区：[1]School of Computer Science and Technology,University of Chinese Academy of Sciences,Beijing 100049,China;[2]State Key Laboratory of Computer Architecture,Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China;[3]School of Comptuer Science,Wuhan University,Wuhan 430072,China 出　　处：《Frontiers of Computer Science》索引2022年第16卷第5期,共3页 基　　金：This work was partially supported by the Natural Science Foundation of China(Grant Nos.41930110,61872272,61640221). 摘　　要：1 Introduction Most real-world graphs are large-scale but unstructured and sparse.One of the most notable characteristics of real-world graphs is the skewed power law degree distribution[1]:most vertices have a few neighbors while a few own a large number of neighbors.These characteristics present challenges for efficient parallel graph processing,such as load imbalance,poor locality,and redundant computations.Apart from modifying the graph programming abstraction or changing the execution models on different architectures,reducing the irregularity of graph data also improves the performance of graph processing[2].For example,it is wellknown that BFS has a bad temporal locality,but it is possible to transform irregular graphs to more regular ones to improve spatial locality and gain more performance. 关 键 词：NEIGHBOR PROGRAMMING REDUNDANT