Graph Accelerators—A Case for Sparse Data Processing  

作　　者：陈文光 Wen-Guang Chen(Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China)

机构地区：[1]Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China

出　　处：《Journal of Computer Science & Technology》2024年第2期243-244,共2页计算机科学技术学报（英文版）

摘　　要：Graph is a powerful sparse data structure that intuitively represents entities and their relationships.Classic graph traversal algorithms such as Breadth-First Search(BFS),Single-Source Shortest Path(SSSP),PageRank,and Weakly Connected Components(WCC)have extensive applications in social network analysis,risk management for finance,and recommendation systems.However,graph processing in CPUs and GPUs is not very efficient due to its irregular memory accesses.Many people have proposed software approaches to speed up graph processing,such as PowerGraph,PowerLyra,and Shentu,which address load imbalance issues by replicating high-degree vertices.XStream and GridGraph attempt to improve memory access locality by scanning the edge list of graphs while localizing the range of vertices accessed in a stage.Ligra and Gemini provide adaptive dual compute modes(bottom-up and topdown),which are particularly effective for BFS-like algorithms such as BFS and SSSP.However,pure software approaches have their limitations,and it is desired to see how hardware could be employed to accelerate graph processing.

关 键 词：intuitive DESIRED LIMITATIONS 

分 类 号：O15[理学—数学]