BAR:a branch-alternation-resorting algorithm for locality exploration in graph processing  

作　　者：邓军勇 WANG Junjie JIANG Lin XIE Xiaoyan ZHOU Kai DENG Junyong;WANG Junjie;JIANG Lin;XIE Xiaoyan;ZHOU Kai(School of Electronic Engineering,Xi'an University of Posts and Telecommunications,Xi'an 710121,P.R.China;School of Computer,Xi'an University of Science and Technology,Xi'an 710054,P.R.China;School of Computer,Xi'an University of Posts and Telecommunications,Xi'an 710121,P.R.China)

机构地区：[1]School of Electronic Engineering,Xi'an University of Posts and Telecommunications,Xi'an 710121,P.R.China [2]School of Computer,Xi'an University of Science and Technology,Xi'an 710054,P.R.China [3]School of Computer,Xi'an University of Posts and Telecommunications,Xi'an 710121,P.R.China

出　　处：《High Technology Letters》2024年第1期31-42,共12页高技术通讯（英文版）

基　　金：the National Key R&D Program of China(No.2022ZD0119001);the National Natural Science Foundation of China(No.61834005);the Shaanxi Province Key R&D Plan(No.2022GY-027);the Key Scientific Research Project of Shaanxi Department of Education(No.22JY060);the Education Research Project of XUPT(No.JGA202108);the Graduate Student Innovation Fund of Xi'an University of Posts and Telecommunications(No.CXJJZL2022011)。

摘　　要：Unstructured and irregular graph data causes strong randomness and poor locality of data accesses in graph processing.This paper optimizes the depth-branch-resorting algorithm(DBR),and proposes a branch-alternation-resorting algorithm(BAR).In order to make the algorithm run in parallel and improve the efficiency of algorithm operation,the BAR algorithm is mapped onto the reconfigurable array processor(APR-16)to achieve vertex reordering,effectively improving the locality of graph data.This paper validates the BAR algorithm on the GraphBIG framework,by utilizing the reordered dataset with BAR on breadth-first search(BFS),single source shortest paht(SSSP)and betweenness centrality(BC)algorithms for traversal.The results show that compared with DBR and Corder algorithms,BAR can reduce execution time by up to 33.00%,and 51.00%seperatively.In terms of data movement,the BAR algorithm has a maximum reduction of 39.00%compared with the DBR algorithm and 29.66%compared with Corder algorithm.In terms of computational complexity,the BAR algorithm has a maximum reduction of 32.56%compared with DBR algorithm and53.05%compared with Corder algorithm.

关 键 词：graph processing vertex reordering branch-alternation-resorting algorithm(BAR) reconfigurable array processor 

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