Design of graph computing accelerator based on reconfigurable PE array  

作　　者：Deng Junyong Jia Yanting Zhang Baoxiang Kang Yuchun Lu Songtao 

机构地区：[1]School of Electronic Engineering,Xi'an University of Posts and Telecommunications,Xi'an 710121,China

出　　处：《The Journal of China Universities of Posts and Telecommunications》2024年第5期49-63,70,共16页中国邮电高校学报（英文版）

基　　金：supported by the National Science and Technology Major Project (2022ZD0119001);the National Natural Science Foundation of China (61834005);the Shaanxi Key Research and Development Project (2022GY-027);the Key Scientific Research Project of Shaanxi Department of Education (22JY060)。

摘　　要：Due to the diversity of graph computing applications, the power-law distribution of graph data, and the high compute-to-memory ratio, traditional architectures face significant challenges regarding poor flexibility, imbalanced workload distribution, and inefficient memory access when executing graph computing tasks. Graph computing accelerator, GraphApp, based on a reconfigurable processing element(PE) array was proposed to address the challenges above. GraphApp utilizes 16 reconfigurable PEs for parallel computation and employs tiled data. By reasonably dividing the data into tiles, load balancing is achieved and the overall efficiency of parallel computation is enhanced. Additionally, it preprocesses graph data using the compressed sparse columns independently(CSCI) data compression format to alleviate the issue of low memory access efficiency caused by the high memory access-to-computation ratio. Lastly, GraphApp is evaluated using triangle counting(TC) and depth-first search(DFS) algorithms. Performance analysis is conducted by measuring the execution time of these algorithms in GraphApp against existing typical graph frameworks, Ligra, and GraphBIG, using six datasets from the Stanford Network Analysis Project(SNAP) database. The results show that GraphApp achieves a maximum performance improvement of 30.86% compared to Ligra and 20.43% compared to GraphBIG when processing the same datasets.

关 键 词：graph computing reconfigurable accelerator parallel computing triangle counting(TC)algorithm depth-first search(DFS)algorithm 

分 类 号：O157.5[理学—数学] TP332[理学—基础数学]