面向超级计算机系统的大规模图遍历优化

谭 雯，甘新标，白 皓，肖调杰，陈旭光，雷书梦，刘 杰

(1.国防科技大学 计算机学院，湖南 长沙，410073；2.湖南信息学院 通识教育学院，湖南 长沙，410217)

图在生物信息、社交网络、交通运输、天体物理等领域得到广泛应用，是大数据浪潮中的主要数据结构之一。许多现实问题可以抽象为图结构。随着大数据应用的发展，其问题的规模不断增长，对超级计算机平台的图存储运算能力产生了广泛需求。这些抽象图中的顶点数和相连的边数有时可以达到万亿级的规模，使得超级计算机系统被期望拥有更高的大数据存储和运算能力[1]。

为了评测超级计算机系统对大数据应用的运行能力，Graph500测试基准被提出，成为数据密集型计算机系统的评测工具。这一基准以图论来分析超级计算机在模拟生物、安全、社会以及类似复杂问题的吞吐量，成为超级计算机测试领域的一个新的主流测试基准。

大数据问题通常具有数据规模极大、数据密集度高、计算复杂性低、分布不均衡等特征。当将现实世界中的大数据问题抽象为图时，这些特征表现为图数据的小世界性(small-world)[2]和无尺度性(scale-free)[3]。小世界性是指在图的所有顶点中，任意两个图顶点的最短路径上的顶点数远少于图中顶点总数；无尺度性是指图中大部分顶点仅与少量顶点之间直接关联，即图中大部分顶点的度数较低。同时，存在少数顶点和数量庞大的顶点之间直接关联关系，即图中存在小部分度数非常高的顶点，这些顶点被称作高度数顶点。……