图计算加速器中稀疏向量比较单元的设计与实现

田 璞 蒋 林 邓军勇 赵一迪 刘新闯 樊 萌

1(西安邮电大学电子工程学院 陕西 西安 710121) 2(西安科技大学集成电路设计实验室 陕西 西安 710054)

0 引 言

大数据时代，每天产生的数据量呈指数增长，预计到2020年，全球的数据量有望达到44 ZB[1-2]。这些数据很大一部分以图的形式存储在各个领域中，而图是一种众所周知的数据格式，例如在线零售、社交网络、机器学习和生物信息学中的数据以图的形式存储[3-4]。现实世界中实体规模的扩张导致相应图数据的规模有数十亿个顶点和上万亿条边，庞大的顶点和边构成的结构信息，以及顶点与边附带的各类属性信息使得遍历、查找、分析等图计算过程中无法预知相邻顶点，造成存储访问的随机性强、局部性差，图计算实时性强的高“访存/计算比”不仅要求带宽高，而且带宽浪费严重[5-6]。真实世界图数据的平均度数通常只有几到几百，与上千万甚至上亿个顶点的规模相比显得极为稀疏，且度数呈幂律分布。该分布的图数据往往组织成邻接稀疏矩阵的形式存储，由于零元素多、规模大，压缩以后存储可以节约大量的空间[7]，常见的图数据压缩格式有压缩稀疏列(Compressed Sparse Column，CSC)、压缩稀疏行(Compressed Sparse Row，CSR)、坐标列表(Coordinate List，COO)，但这些压缩方式难以精确寻址，且现有的图计算加速器需要将压缩后的图数据重新解压缩才能执行后续处理。

随着图计算、稀疏线性代数和机器学习的兴起，图计算应用变得越来越重要和普遍[8]。对于常用的图计算应用，专用的硬件加速器是实现高性能低功耗的一种途径[9-12]。……