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

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

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

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 237 on Tianhe pre-exascale system with 2.131E+12 TEPS(traversed edges per second).