严明玉 李 涵 邓 磊 胡 杏 叶笑春 张志敏 范东睿 谢 源

1(计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190)2(中国科学院大学 北京 100049)3(美国加州大学圣塔芭芭拉分校 美国加利福利亚州圣塔芭芭拉 93106)

大数据时代，越来越多的数据采用图结构进行表示.图是一种能够表达对象之间复杂关系的数据存储方式，被广泛用于表示人际关系、分子拓扑结构、大脑神经元链接等.图数据中蕴含着丰富的信息，图计算应用是一种挖掘图数据中隐含价值的重要应用.为了快速处理图数据和应对不断增长的图数据，图计算应用被广泛部署于各大数据中心，成为数据中心的典型应用.

源于图的无结构特性，图计算应用在现有通用架构上无法被高效执行.现实生活中的图没有固定的结构，节点的出边分布极度不均匀，节点与节点之间的连接极为随机.由于图计算应用的执行行为依赖于图数据，图数据的以上特性导致图计算应用的执行行为非常不规则.这种不规则的执行行为导致现有的通用架构在计算、访存和通信3个方面都面临巨大挑战.在计算方面，计算单元面临负载不均衡、密集读改写更新等挑战，导致基于CPU和GPU的图计算软件框架的性能严重不足.在访存方面，不规则的细粒度访存导致CPU的L2和L3 Cache的命中率极低[1]，Cacheline利用效率低下，同时也导致了GPU的SIMT(single instruction multiple threads)执行模型遇到了大量的访存歧义(memory diver-gence).在多节点计算、存储系统方面，不规则的细粒度……