Abstract
Unstructured and irregular graph data causes strong randomness and poor locality of data acces-ses in graph processing.This paper optimizes the depth-branch-resorting algorithm(DBR),and pro-poses 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 reconfigu-rable 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 re-ordered 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 and 53.05%compared with Corder algorithm.
基金项目
National Key R&D Program of China(2022ZD0119001)
National Natural Science Foundation of China(61834005)
Shaanxi Province Key R&D Plan(2022GY-027)
Key Scientific Research Project of Shaanxi Department of Education(22JY060)
Education Research Project of XUPT(JGA202108)
Graduate Student Innovation Fund of Xi'an University of Posts and Telecommunications(CXJJZL2022011)
维普
万方数据