ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2021, Vol. 58 ›› Issue (3): 458-466.doi: 10.7544/issn1000-1239.2021.20200090

Previous Articles     Next Articles

Bidirectional-Bitmap Based CSR for Reducing Large-Scale Graph Space

Gan Xinbiao, Tan Wen, Liu Jie   

  1. (College of Computer Science and Technology, National University of Defense Technology, Changsha 410073)
  • Online:2021-03-01
  • Supported by: 
    This work was supported by the National Numerical Wind Tunnel Project (NNW2019ZT6-B21, NNW2019ZT6-B20, NNW2019ZT5-A10), the National Key Research and Development Program of China (2018YFB0204301), the Hunan Provincial Natural Science Foundation of China (2020JJ4669), and the Foundation of Parallel and Distributed Processing Laboratory (6142110190206, 6142110180203).

Abstract: Graph500 is an important and famous benchmark to evaluate data-intensive applications for supercomputers in the big data era. The graph traversal processing ability of pre-exascale system is mainly restricted to memory space and communication bandwidth, especially the utilization of memory space ultimately determines the testing graph scale, and the graph testing scale absolutely dominates the performance of Graph500. Hence, Bi-CSR (bidirectional-bitmap CSR) is proposed based on CSR (compressed sparse row) for testing Graph500 on Tianhe pre-exascale system, The Bi-CSR would reduce large-scale graph space by introducing row-bitmap and column-bitmap to compress sparse matrix storage for Graph500.The aim of row-bitmap based on CSR is mainly cutting down graph memory space, while column-bitmap based on CSR would not only further reduce memory space but also improve graph traversal by using array of VPE(vector processing element), because VPEs are optimized and equipped in Tianhe pre-exascale system, which would speedup graph traversal when making fully use of VPEs. Accordingly, Bi-CSR would greatly reduce large-scale graph space while introducing row-bitmap and column-bitmap to compress sparse matrix storage of Graph500 for Tianhe pre-exascale system. Experimental results demonstrate that Bi-CSR would reduce large-scale graph space by 70% when testing input of Graph500 is 2\+\{37\} on Tianhe pre-exascale system with 2.131E+12 TEPS (traversed edges per second).

Key words: Graph500, bidirectional-bitmap, compress sparse matrix storage, graph traversal, Tianhe pre-exascale system

CLC Number: