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

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

扫码查看
原文链接
  • 万方数据
  • 维普
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.

graph processingvertex reorderingbranch-alternation-resorting algorithm(BAR)reconfigurable array processor

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

National Key R&D Program of ChinaNational Natural Science Foundation of ChinaShaanxi Province Key R&D PlanKey Scientific Research Project of Shaanxi Department of EducationEducation Research Project of XUPTGraduate Student Innovation Fund of Xi'an University of Posts and Telecommunications

2022ZD0119001618340052022GY-02722JY060JGA202108CXJJZL2022011

2024

10.3772/j.issn.1006-6748.2024.01.004

高技术通讯(英文版)
中国科学技术信息研究所（ISTIC）

高技术通讯(英文版)

影响因子：0.058
ISSN：1006-6748
年,卷(期)：2024.30(1)
  • 21