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

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

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]。根据图计算系统中数据处理对象的局部性差、“访存/计算比”高的实际特性，本文已经设计了一个优化的图数据组织形式独立压缩稀疏列(Compressed Sparse Column Independently，CSCI)和图计算加速器[13]，深入挖掘图数据潜在并行性。

绝大多数图计算应用都可以映射为稀疏矩阵向量乘法运算[14]。根据大多数流行的图计算应用的运算功能，比如广度优先搜索算法(Breadth First Search，BFS)之类的图算法将比较最大/最小运算作为核心运算。相比之下，其他图计算应用(比如Page Rank)则利用算术运算(比如求和)来迭代累加相邻的值，直到最终收敛，所以可以将图计算应用分为两类：算术运算和最小/最大比较[15]，各种图计算应用程序的核心运算总结如表1所示[16]。经CSCI数据存储格式存储的图数据在进行以上两种图应用时，不论核心运算是算术运算还是比较运算，都需要比较确定两个矩阵列向量中的元素在同一列。由于图数据规模大、稀疏性强，如何高效地实现两个稀疏列向量的比较运算就是一个值得考虑的问题，针对这一问题，本文提出两个稀疏矩阵向量的比较方法。

表1 图计算应用的核心运算总结

1 CSCI图数据格式的稀疏向量比较

1.1 图计算加速器和图数据压缩方法

图计算加速器的电路结构如图1所示，包括预处理电路、存储器、控制器、数据访问单元、调度器、混合粒度处理单元和结果产生单元。预处理电路根据CSCI数据压缩方法[13]对邻接稀疏矩阵数据进行转换处理。控制电路用于接收预处理电路中存储完毕之后发送的转换就绪指示信号，根据主机发送的图计算应用类型控制所述数据访问单元、混合粒度处理单元、结果产生单元的操作。数据访问单元从所述存储器中读取CSCI的图数据和列标识，并根据所述根顶点索引、源顶点索引或结果产生单元传送的活跃顶点索引计算指定顶点在存储器中的物理地址以进行数据访问，以及将读取的数据传输到调度器；调度器用于将CISI中列标识指示的非零元素个数暂存，并根据所述混合粒度处理单元内处理元的状态信号，将暂存的数据分配到混合粒度处理单元内的处理元进行处理。混合粒度处理单元根据控制电路内的应用类型和结果产生单元的活跃顶点数据对调度器内暂存的数据进行并行处理，并将处理后的中间数据传输至结果产生单元。结果产生单元根据控制电路内的图计算应用类型对中间数据进行处理，以及将处理过程的活跃顶点索引发送数据访问单元，将处理后的最终结果存储。

图1 图计算加速器的结构

图计算加速器的预处理电路将待处理的以邻接矩阵表示的图数据转换成独立的稀疏列压缩CSCI格式的图数据，每列独立压缩后的图数据包括列标识数据对和非零元素数据对，每个数据对都包括索引(index)和数值(value)，索引的最高两位指示索引其余位和数值的含义。

表2是CSCI格式中数据对的具体含义，当index最高两位为“01”时，index其余位表示列索引，value表示邻接稀疏矩阵中该列的非零元素数目；当index最高两位为“10”时，index其余位表示列索引，且该列为邻接稀疏矩阵的最后一列，value表示邻接矩阵中该列的非零元素数目；当index最高位为“00”时，index其余位表示行索引，value表示稀疏邻接矩阵中对应的非零元素值。

表2 CSCI格式中数据对含义

1.2 比较设计

经过CSCI[13]格式压缩过的图数据，对于多种图计算应用，都会涉及到两个稀疏矩阵列向量的比较运算操作，为高效地实现两个CSCI格式表示对的稀疏向量的比较，本文设计一种基于图计算加速器的稀疏矩阵列向量比较电路。

(1) 整体结构。稀疏矩阵列向量比较电路如图2所示，假设两个稀疏向量一个是目标向量，一个是比较向量，该设计包括64个比较运算电路，比较向量的所有非零元素输入至第一个比较运算电路，目标向量的所有非零元素分别输入至64个比较运算电路。第一个比较运算电路的输入是所有比较向量元素和目标向量的第一个非零元素，经过比较运算后可以直接输出的元素不再输出至第二个比较运算电路与目标向量的第二个非零元素进行比较运算，需要与目标向量的第二个非零元素做比较运算的元素只是比较向量非零元素的一部分，以此类推，越后面的比较运算电路的比较运算操作越少，计算量越少。

(2) 比较运算电路。每个比较运算电路包括了操作电路、直接输出模块和中间输出模块，具体的电路设计如图2右上部分所示。比较向量的非零元素数目是64，正如操作电路(Operate Circuit，OC)中包含了8个比较单元(Compare Unit，CU)，比较运算的结果需要传输至下一个比较运算电路的非零元素通过中间输出电路输出，可以直接输出的非零元素通过直接输出电路输出。中间输出电路输出的元素是运算元素，需要在下一个比较运算单元与下一个目标向量的非零元素进行比较运算。直接输出电路输出的元素是输出元素，为保证最后一级比较运算电路输出最终的比较运算结果，输出元素在每一级的比较运算电路都是透传。

操作电路OC包括了8个比较单元，分别为CU0-CU7，比较向量的非零元素顺序分组后，每个CU都有8个比较向量的非零元素，每个CU的具体比较过程如图3所示，实现一个目标向量非零元素和比较向量中的8个非零元素进行比较的过程。其中：target表示目标向量元素；com表示目标向量的元素；“00”表示目标向量元素的索引等于比较向量元素索引；“01”表示小于；“10”表示大于。

目标向量元素首先与比较向量的首个元素索引进行比较，小于或相等就可以结束比较，直接输出相应结果，比较向量的其他元素可以输出至下一级进行比较。若大于，接着与比较向量的最后一个元素索引进行比较。若相等输出相应结果，本级的比较结束，小于该元素索引的比较向量元素都可以送至直接输出模块；若大于比较向量的最后一个元素索引，则要与下一组比较向量继续进行比较；若小于比较向量的最后一个元素索引，继续按照二分法进行比较，得到本级比较的结果。最后将可以直接输出的向量元素送至直接输出模块，将需要输出下一级比较的比较向量元素送至中间输出模块。

图4是目标向量元素和比较向量元素的行索引三种比较情况，每个CU中目标向量的第一个非零元素与比较向量分组后的第一组8个非零元素进行行索引比较。

若比较向量的第一组中的非零元素的最小行索引(compare0_index)都大于目标向量第一个非零元素的行索引(target0_index)，则目标向量的第一个非零元素可以直接输出至直接输出电路，分组比较单元CU0-CU7不再运行，将不再进行比较的比较向量的非零元素输出至操作电路连接的中间输出模块，之后作为第二个比较运算电路的输入比较向量，继续与目标向量的第二个非零元素比较，如图4中①所示。

若比较向量的第一组中的非零元素中存在与目标向量的第一个非零元素行索引相同，则将两个非零元素的数值进行相应的运算，该结果传输至直接输出电路，比较向量中其他索引小于目标向量的第一个非零元素的索引的非零元素传输到直接输出电路，剩余大于目标向量的第一个非零元素的索引的非零元素传输到中间输出电路。剩余分组比较单元CU1-CU7不再运行，将不再进行比较的比较向量的非零元素输出至操作电路连接的中间输出模块，之后作为第二个比较运算电路的输入比较向量，继续与目标向量的第二个非零元素比较，如图4中②所示。

若比较向量的第一组中的非零元素的行索引均小于目标向量第一个非零元素的行索引，将比较向量非零元素的第一组输出至直接输出模块，目标向量第一个非零元素的行索引继续与比较向量的第二组CU2的8个非零元素的索引比较，比较方法以此类推，如图4中③所示。

(3) 共享存储。共享存储是用来存储每一个比较运算电路中可以直接输出的向量元素，如图5所示，共享存储包括一个初始地址寄存器和一个数据存储。当一个比较运算电路运算结束后，根据初始存储地址将数据依次存储在数据存储RAM中，当把本级比较运算电路直接输出的向量元素存储完毕会产生一个停止存储的地址，该地址作为下一个比较运算电路的直接输出向量元素在共享存储中的初始地址。共享存储的输出是两个稀疏向量比较运算的结果，当两个稀疏向量的所有比较运算结束后，共享存储的输出将作为整个稀疏向量的比较运算结果输出，此时，两个稀疏向量的比较运算结束。

2 实验结果及分析

本文所设计的图计算中稀疏向量的比较运算电路，基于Verilog HDL语言在ModelSim SE-64 10.1c上完成设计和功能验证，并且采用Xilinx公司的ISE14.7开发环境进行综合，使用Xilinx公司ZYNQ系列的zc706 FPGA开发板对硬件电路进行测试。图数据选自斯坦福大学SNAP(Stanford Network Analysis Project)的数据集Flickr[17]。

2.1 仿真设计结果

在对本文所设计的稀疏向量比较运算电路进行验证时，首先将数据集中的非零元素转换为CSCI格式，然后将这些压缩过的数据作为整个设计的输入。根据每个向量中非零元素的数目不同，分别对整个设计进行验证。图6是仿真的部分波形图，图6(a)是第一级比较运算电路的波形图，第一级比较运算的实现周期是23，图6(b)是第36级比较运算电路的波形图，该级比较运算的实现周期是16。可以看出比较运算电路的实现周期数减少了。

(a) 第1级比较运算电路

(b) 第36级比较运算电路图6 比较运算电路仿真结果

如图7所示，根据稀疏向量中非零元素数目的不同，每一级比较运算电路实现的周期数也不同，前几级的比较运算电路实现的周期数比较多，但是越往后，比较运算电路所做的计算量越少，实现的周期数也越少。图7中的比较向量/目标向量中的非零元素数目分别是：64/64、55/50、40/42、32/40、23/20，虽然非零元素的数目不同，但所呈现的趋势一样。横坐标表示比较运算电路的第一级至最后一级，每八个比较运算电路为一组，第一级的比较运算电路实现的周期数目在19～26个，第二级电路的实现也在20～24个周期，第三级至第四级的比较运算电路所实现的周期个数比前两级明显减少，且周期数基本保持在11～15个，后面三级的比较运算电路实现的周期数也明显的减少，甚至有的运算电路由于非零元素数目的个数太少，导致最后三级的比较运算电路不执行，直接输出最终的比较结果。

图7 不同非零元素数目每个比较运算电路实现的周期数

2.2 综合结果

由于图计算加速器的主要瓶颈就是在两个稀疏向量的比较运算上，所以本文所设计的两个稀疏向量比较单元的性能在一定程度上可以代表整个图计算加速器的性能。表3是与文献[9]的资源利用的对比结果，可以看出，本文所设计的硬件电路LUTs资源使用减少了80 k，FFs资源使用减少了281 k。

表3 本文与文献[9]的资源使用对比

图的大小是图计算的一个关键性能参数，表4是各图计算加速器所用的数据集和数据集中的顶点V及边E的大小。文献[9]的数据集为SpMV，文献[11]和文献[12]均来自社交网络和合成图Kronecker，由表4可以看出，本文所采用的数据集Flickr比文献[9]的数据集规模大，最大的顶点数目和最大的边数目分别是GraphSOC[9]的58倍和7.9倍，但均小于文献[11]和文献[12]图的规模。GraphOps[11]和GraFBoost[12]采用的图的大小均大于Flickr，特别是GraFBoost[12]的数据集大小远远大于Flickr。

表4 数据集和数据集中的顶点及边的大小

与图计算加速器GraphSOC[9]、GraphOps[11]和GraFBoost[12]的数据集、图数据压缩格式和频率进行了比较，结果如表5所示。GraphOps[11]采用的图数据压缩格式是自定义的，GraFBoost[12]采用的图数据压缩格式是CSR，本文采用的图数据压缩格式是CSCI[13]。本文硬件电路综合的频率均高于以上三个图计算加速器，分别提高了5.6%、76%和111%。

在数据集大小相差不多的情况下，本文所设计的硬件电路比GraphSOC的资源使用低，且具有更高的综合频率。虽然综合频率高于GraphOps[11]和GraFBoost[12]，但是本文用于验证的数据集均小于这两个加速器，并且本文设计的硬件电路是图计算加速器的一部分。

3 结 语

为了高效地实现图计算加速器中的稀疏矩阵列向量的比较运算，本文设计一种稀疏矩阵列向量的比较运算电路。本文提出的电路由64个比较运算电路和一个共享存储模块组成，经实验分析，与其他的图计算加速器相比，具有更高的工作频率和更少的资源利用率。通过在Xilinx公司的ZC706开发板上进行验证，表明可实现稀疏向量比较的功能。