ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2020, Vol. 57 ›› Issue (6): 1152-1163.doi: 10.7544/issn1000-1239.2020.20200115

Special Issue: 2020计算机体系结构前沿技术专题

Previous Articles     Next Articles

Efficient Optimization of Graph Computing on High-Throughput Computer

Zhang Chenglong1,2, Cao Huawei1, Wang Guobo1,2, Hao Qinfen1, Zhang Yang1, Ye Xiaochun1, Fan Dongrui1,2   

  1. 1(State Key Laboratory of Computer Architecture (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190);2(School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 100049)
  • Online:2020-06-01
  • Supported by: 
    This work was supported by the National Key Research and Development Program of China (2018YFB1003501), the National Natural Science Foundation of China (11904370, 61732018, 61672499), and the Innovation Project of the State Key Laboratory of Computer Architecture (CARCH4509).

Abstract: With the rapid development of computing technology, the scale of graph increases explosively and large-scale graph computing has been the focus in recent years. Breadth first search (BFS) is a classic algorithm to solve graph traverse problem. It is the main kernel of Graph500 benchmark that evaluates the performance of supercomputers and servers in terms of data-intensive applications. High-throughput computer (HTC) adopts ARM-based many-core architecture, which has the characteristics of high concurrency, strong real-time, low-power consumption. The optimization of BFS algorithm has made a series of progress on single-node systems. In this paper, we first introduce parallel BFS algorithm and existing optimizations. Then we propose two optimization techniques for HTC to improve the efficiency of data access and data locality. We systematically evaluate the performance of BFS algorithm on HTC. For the Kronecker graph with 2scale=230whose vertices are 230 and edges are 234, the average performance on HTC is 24.26 GTEPS and 1.18 times faster than the two-way x86 server. In terms of energy efficiency, the result on HTC is 181.04 MTEPS/W and rank 2nd place on the June 2019 Green Graph500 big data list. To our best knowledge, this is the first work that evaluates BFS performance on HTC platform. HTC is suitable for data intensive applications such as large-scale graph computing.

Key words: breadth first search (BFS), high throughput, Graph500, graph algorithm, super computing

CLC Number: