张 旭，常轶松,3，张 科,3，陈明宇,3

(1. 中国科学院计算技术研究所， 北京 100190； 2. 中国科学院大学， 北京 100049； 3. 鹏城实验室， 广东 深圳 518000)

互联网的快速发展使得图(graph)成为一种被广泛使用的数据抽象方法, 用于表达数据之间关联关系。基于图表示的社会网络、交通网络、文章相似度、疾病暴发路径、学术文章引用关系等数据，以及应用在这些种类繁多的图数据上的最短路径、分类问题、最小割集和连通分支、PageRank及其变种等图算法构成了各种图计算应用[1-3]。随着大数据时代的到来及人工智能应用的兴起，图计算已被广泛应用于机器学习(如图卷积网络、图神经网络等[4])、计算机视觉、模式识别等相关领域。因此，提高图计算应用的处理性能将对未来智能信息产业的发展起到至关重要的作用。

另一方面，基于传统冯·诺伊曼体系结构的通用处理器计算平台是支撑以图计算应用基础软件框架(如Google Pregel[5]、美国加州大学伯克利分校GraphX[6]等)高效运行的重要基础平台。随着图数据规模的不断增长，图应用负载对通用处理器平台的能力提出了更高的要求。如何提高通用处理器平台的图数据处理性能，以应对不断增长的图数据计算规模带来的挑战，是本文关注的主要研究内容。

图可以表示成一个由顶点集合和边集合组成的二元组，每条边由顶点集合中两个点相连接所构成；每个顶点和每条边都可以被赋予一个权重值。面向真实应用场景的图数据一般规模较大，数据间的关联关系也呈现复杂多变的特点。……