甘新标 谭 雯 刘 杰

(国防科技大学计算机学院 长沙 430017)

(xinbiaogan@nudt.edu.cn)

大数据时代，超级计算机系统结构面临着巨大的机遇和全新的挑战.图搜索处理对计算机系统存储和带宽要求甚高，传统的超级计算机系统处理大规模图数据的效率低下.Graph500作为数据密集型计算机系统的评测基准，能够准确反映E级计算机系统的大数据处理能力和指导E级计算机系统设计.

Graph500以每秒遍历的边数(traversed edges per second， TEPS)为性能指标来衡量超级计算机处理数据密集型应用的能力.Graph500测试性能主要受限于图测试规模和访存带宽，尤其是内存空间大小直接决定了图的测试规模.因此，本文提出了基于双向位图的大规模图数据压缩存储方法(bidirectional-bitmap based compressed sparse row， Bi-CSR)以增加Graph500图测试规模，并提升Graph500图测试性能.

本文的主要贡献有2个方面:

1) 提出了基于双向位图的稀疏矩阵压缩存储方法Bi-CSR，大幅减少了大规模图存储空间.

2) 将Bi-CSR应用于天河E级验证的Graph500测试，达到了良好的测试性能.

1 相关工作

很多现实问题可以抽象为图形结构，因此，图形理论在众多学科中应用广泛[1-3].从现实问题中抽象出来的图形结构通常具有2个特点：小世界性(small-world)[4]和无尺度性(scale-free)[5].

图遍历是大数据时代背景下的一种典型的数据密集型应用，Graph500测试基准是典型的数据密集型程序.其核心搜索程序能够适用于数据密集型应用，能够解决真实世界中的实际搜索问题，测试数据集能够反映真实数据集的普遍特征，并且Graph500具有较差的时间和空间局部性，因此，Graph500具有一般……