| 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 Name | Affiliation | | 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: 425 |
| Download times: 460 |
| 中文摘要: |
| |
| 英文摘要: |
| 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 |
|
|
|
