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

在大数据时代，超级计算机系统面临着处理大规模图数据的挑战。Graph500作为一个数据密集型计算机系统的评测基准，衡量超级计算机处理大数据应用的能力，特别是以每秒遍历的边数（TEPS）为性能指标。然而，传统的超级计算机在处理大规模图数据时效率较低，其性能受限于图的测试规模和内存带宽。因此，为了提高Graph500的性能和测试规模，文章提出了基于双向位图的压缩稀疏行（Bi-CSR）存储方法。 双向位图的稀疏矩阵压缩存储方法Bi-CSR是本文的核心贡献。这种方法通过使用双向位图来大幅减少大规模图的存储空间，从而解决了存储空间限制的问题。相比于其他常见的稀疏矩阵存储格式，如COO、DIA、CSR、CSB、ELL和HYB，Bi-CSR在天河E级验证的Graph500测试中表现出良好的性能。例如，CSR格式在天河验证系统上的最大测试图规模为36，性能达到1310GTEPS，而Bi-CSR通过提高压缩效率和优化内存使用，进一步提升了图的测试规模和性能。 近年来，针对Graph500的核心算法——广度优先搜索（BFS）的优化遍历研究不断取得进展。例如，Bader等人利用多线程技术隐藏访存延迟，Agarwal等人利用位图数据结构提高访问局部性，Beamer等人提出了混合的Top-down与Bottom-up算法减少边的遍历，Ueno等人面向大规模并行环境设计了高效的BFS算法，林恒等人则在“神威太湖之光”上实现了可扩展的BFS算法。这些优化技术本质上都是通过加速图遍历来提升Graph500的测试性能。 图遍历速度对Graph500的测试性能至关重要，测试图的规模越大，性能越高。内存空间的大小直接决定了图的测试规模，因为图形通常用邻接矩阵表示，尤其是对于具有低平均度数的顶点，邻接矩阵通常是稀疏的。因此，选择合适的邻接矩阵存储格式对Graph500的性能有着直接影响。不同的稀疏矩阵存储格式在效率、灵活性、可扩展性和适用场景上各有优劣，而Bi-CSR在这种背景下脱颖而出，展示了其在存储优化和性能提升方面的优势。 本文通过对双向位图的稀疏矩阵压缩存储方法Bi-CSR的探讨，不仅解决了大规模图数据存储的问题，还提升了Graph500的测试性能，为超级计算机在大数据时代的应用提供了新的解决方案。这种方法的应用和优化对于未来E级计算机系统的设计和性能提升具有重要指导意义。