文章摘要
DENG Junyong(邓军勇)*,WANG Junjie *,JIANG Lin **,XIE Xiaoyan ***,ZHOU Kai *.[J].高技术通讯(英文),2024,30(1):31~42
BAR: a branch-alternation-resorting algorithm for locality exploration in graph processing
  
DOI:10. 3772 / j. issn. 1006-6748. 2024. 01. 004
中文关键词: 
英文关键词: graph processing, vertex reordering, branch-alternation-resorting algorithm (BAR), reconfigurable array processor
基金项目:
Author NameAffiliation
DENG Junyong(邓军勇)* (* 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) 
WANG Junjie *  
JIANG Lin **  
XIE Xiaoyan ***  
ZHOU Kai *  
Hits: 276
Download times: 305
中文摘要:
      
英文摘要:
      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 and 53. 05% compared with Corder algorithm.
View Full Text   View/Add Comment  Download reader
Close

分享按钮