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

作     者：甘新标 谭雯 刘杰 Gan Xinbiao;Tan Wen;Liu Jie

作者机构：国防科技大学计算机学院长沙430017 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2021年第58卷第3期

页      面：458-466页

核心收录：

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家数值风洞项目(NNW2019ZT6-B21,NNW2019ZT6-B20,NNW2019ZT5-A10) 国家重点研发计划项目(2018YFB0204301) 湖南省自然科学基金项目(2020JJ4669) 并行分布式处理实验室基金项目(6142110190206,6142110180203) 

主　　题：Graph500 双向位图 稀疏矩阵压缩存储 图遍历 天河E级验证系统 

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