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

摘要

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.