ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2021, Vol. 58 ›› Issue (3): 458-466.doi: 10.7544/issn1000-1239.2021.20200090

• 软件技术 • 上一篇    下一篇

基于双向位图的CSR大规模图存储优化

甘新标,谭雯,刘杰   

  1. (国防科技大学计算机学院 长沙 430017) (xinbiaogan@nudt.edu.cn)
  • 出版日期: 2021-03-01
  • 基金资助: 
    国家数值风洞项目(NNW2019ZT6-B21, NNW2019ZT6-B20, NNW2019ZT5-A10);国家重点研发计划项目(2018YFB0204301);湖南省自然科学基金项目(2020JJ4669);并行分布式处理实验室基金项目(6142110190206, 6142110180203)

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).

摘要: 大数据时代, Graph500是评测超级计算机处理数据密集型应用能力的重要工具, E级验证系统的图遍历处理能力主要受限于内存空间和访存带宽, 尤其是内存空间利用率直接决定了图的测试规模和测试性能.针对天河E级验证系统小内存特征, 提出了基于双向位图的大规模图数据压缩存储方法(bidirectional-bitmap based CSR, Bi-CSR), Bi-CSR在CSR矩阵压缩的基础上引入行方向位图和列方向位图协同完成稀疏矩阵压缩存储, 行方向位图主要负责行方向位图的压缩存储与索引, 列方向位图除了进一步压缩图存储空间, 还负责为顶点遍历向量并行优化提供加速空间.Bi-CSR大幅度减少了稀疏矩阵存储空间.面向天河E级验证系统, 当图输入规模为2\+\{37\}时, Graph500的图存储空间节约效率接近70%, 全系统稳定测试性能为2.131E+12TEPS, 性能最大加速比超过100倍.

关键词: Graph500, 双向位图, 稀疏矩阵压缩存储, 图遍历, 天河E级验证系统

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

中图分类号: