1.本发明涉及存内计算领域，尤其涉及一种基于存内计算的图卷积网络软硬件协同加速方法和装置。
背景技术：2.图结构是一种常用的数据结构，由众多节点和连接节点之间的边组成。交通网络、社交网络、分子结构等日常和研究中常用的结构都可以用图结构来抽象地表示。近年来，图神经网络模型(gnn)在基于图的任务上展现了强大的学习能力，如推荐系统、文献分类等。而图卷积网络模型(gcn)得益于其较小的计算代价和出色的准确率性能，已经成为当下最常用的一种gnn模型。如图1所示，图任务中每个节点都会拥有一个特征向量，包含了该节点的信息，而gcn的目的就是要根据这些信息和节点间的联接关系推理出所需的结论，如通过文献的作者和引用关系推理出文献的分类等。典型的图卷积网络模型包含数个网络层，每个层中包含两个阶段，分别是邻居节点特征聚合和特征向量组合。在邻居节点特征聚合阶段，每个节点会获取它相邻的点的特征向量，并使这些向量共同被一个聚合函数(如求和、求平均值函数)作用，这个步骤通常可以被抽象成用稀疏的邻接矩阵和稠密的特征矩阵进行的稀疏矩阵乘法。在向量组合阶段，上一阶段得到的结果将被送入一个多层感知机(mlp，multilayerperceptron)，得到的结果将作为下一层网络的节点特征矩阵。如果写成矩阵的形式，则可以把图卷积网络用如下的公式表达：
3.h
l+1
＝σ(ah
l
w)
4.其中σ代表非线性函数，h
l+1
,h1表示第l+1和第l层的节点特征矩阵，w表示mlp的权重矩阵，这些矩阵一般是稠密的；而a表示图的邻接矩阵，一般是不规则且稀疏的。
5.gcn和传统神经网络(如卷积神经网络(cnn))的区别在于图结构的不规则性。在特征聚合阶段，gcn需要收集节点所有(或部分)邻居节点的特征向量，而这些特征向量在内存中的摆放是不连续的。并且由于现实图规模一般很大，gcn计算时访存的负担将进一步加重。在传统的冯
·
诺伊曼架构中，由于gcn计算过程中存在的不规则访存和大量的数据搬运，架构的计算性能会极大受限。以用图形处理单元(gpu)计算gcn为例，有学者指出，当特征向量维度增大时，每次计算时gpu需要从全局内存中加载的数据量也相应变多，全局吞吐率逐渐被全局带宽所限制。如图2所示，当特征向量维度增加到32时，全局吞吐率就被全局带宽所限制，不再随特征维度增长而增加，这体现了使用冯
·
诺伊曼架构计算gcn时数据搬运的巨大负担，这些数据搬运造成整体gcn计算性能受到带宽瓶颈的限制。
6.2008年，科学家研制了阻变式随机存储器(rram，resistive random access memory)，这种器件具有阻值可变的特性，只要在器件两端加特定的电压就可以改变其电阻，且断电后电阻可以保持不变，因此可以使用rram电阻阻值表示存储的数据。研究者把rram器件以行列的方式排布组织成交叉阵列的结构，用rram的电导值代表矩阵元素的值，用字线上的电压作为输入向量，来实现存内的矩阵向量乘。由欧姆定律，可以得到位线上的输出电流与字线电压和rram电导的关系为：
[0007][0008]
写成矩阵的形式则为：
[0009]
i＝cv
[0010]
如此可以在存内实现o(1)时间复杂度的矩阵向量乘，并保持权重数据始终在存储器中，免去了大量权重数据的搬运。由于神经网络的主要计算过程可以以矩阵向量乘的形式表示，现有研究已经基于该方法设计了基于rram存内计算的cnn加速器，并成功实现了极高的加速比。与本方案最相近似的实现方案为prime，该方案将cnn的卷积核权重展开并映射到rram交叉阵列上，并将每一层的特征图作为输入向量计算矩阵向量乘来计算每一层的卷积。该方案提出的数据映射方法和硬件架构设计为解决cnn存内计算问题做出了重要贡献。如用该实现方案实现gcn的计算，因为邻接矩阵a的规模极大(矩阵元素个数一般超过108个)且非常稀疏(非零元素个数一般不超过0.1％)，将a映射到rram上需要极大规模的阵列，所以应将特征矩阵h和权重矩阵w映射到rram交叉阵列上，并把a的每一行分别输入，再依次和h、w进行矩阵向量乘，最终当a的所有行都被输入且计算完成后，计算的结果将被用于更新h矩阵，并标志着一层gcn计算的结束。
[0011]
目前基于存内计算的架构用于gcn计算仍然存在着很多的问题，列举如下：
[0012]
1.存内计算中节点间的计算并行度低，不同节点的特征聚合不能并行计算。现存的存内计算架构使用rram的交叉阵列来存储矩阵，并把向量转化成电压加载在字线上来实现矩阵向量乘。为了计算gcn中的邻居特征聚合步骤，邻接矩阵和特征矩阵之间的矩阵乘法需要被分割成很多个矩阵向量乘，而这些矩阵向量乘只能被顺序串行执行，从而导致计算延时代价较大。以一个典型图数据集arxiv数据集为例，在特征聚合阶段，原本的稀疏矩阵-矩阵乘法需要被分解成169343个顺序执行的矩阵向量乘，导致了较高的计算延时；
[0013]
2.现有的存内计算架构计算gcn时硬件资源利用率很低，未充分发挥rram交叉阵列存内计算的高计算并行度。在现有的存内计算架构中，矩阵向量乘的输入向量会被转化成电压向量并加载到rram交叉阵列的字线上，激活相应的行进行计算。但是当计算稀疏矩阵乘法时，稀疏的输入向量只会激活很少一部分的阵列行，而剩余的阵列行都会闲置。例如，在典型图数据集pubmed上，gcn的特征聚合操作平均每次只会激活19717行中的4.5行，导致了严重的阵列利用率低下的问题；
[0014]
3.现有的基于rram存内计算架构主要支持定点数计算，并采用较低的数据位宽来进一步减少计算代价。而主流的高准确率的gcn模型使用的均是32位浮点数。在适合低数据位宽定点计算的存内计算架构上部署32位浮点数的gcn模型依旧是一个亟待解决的问题。
技术实现要素：[0015]
本发明旨在至少在一定程度上解决相关技术中的技术问题之一。
[0016]
为此，本发明的目的在于，在部署算法层面，面向多核存内计算硬件设计gcn部署算法，解决如何把不规则图数据映射到规模一定的硬件阵列上，并同时提升计算并行度的问题，在硬件层面，解决存内计算单元和数据流如何设计的问题，提出了一种基于存内计算的图卷积网络软硬件协同加速方法。
[0017]
本发明的另一个目的在于提出基于存内计算的图卷积网络软硬件协同加速装置。
[0018]
为达上述目的，本发明一方面提出了基于存内计算的图卷积网络软硬件协同加速方法，包括以下步骤：
[0019]
软件方面：在进行图数据的存内计算中通过量化定点方式，将所述图数据的高位宽的浮点数转化为低位宽的定点数；并使用基于图聚类的映射算法，将所述图数据的原始图分割成多个子图得到聚类结果，并将所述多个子图的节点特征映射到用于计算特征聚合的rram交叉阵列上；以及，基于所述聚类结果使用边删除方式，将所述聚类结果中连接不同所述子图的边进行删除，以通过面向硬件的部署算法将所述图数据部署到硬件上；
[0020]
硬件方面：配置计算模块和控制模块；其中，所述计算模块包括：聚合核阵列、向量组合阵列和中间缓存，所述聚合核阵列用于计算所述图数据的特征聚合，所述向量组合阵列用于计算所述图数据的向量组合，以及所述中间缓存用于所述聚合核阵列和所述向量组合阵列的数据交换；所述控制模块包括：指令队列、图数据解码器和邻居缓存，分别用于所述图数据的指令的暂存、格式转换以及邻接向量的暂存；
[0021]
通过所述软件方面和所述硬件方面的协同设计，实现图卷积网络gcn计算的加速。
[0022]
根据本发明实施例的基于存内计算的图卷积网络软硬件协同加速方法，在软件方面，通过量化定点方式，将图数据的高位宽的浮点数转化为低位宽的定点数，将图数据的原始图分割成多个子图得到聚类结果，并将多个子图的节点特征映射到用于特征聚合的rram交叉阵列上，再使用边删除方式将聚类结果中连接不同子图的边删除，以将图数据部署到硬件上；在硬件方面，配置计算模块和控制模块，其中，计算模块包括：聚合核阵列、向量组合阵列和中间缓存，控制模块包括：指令队列、图数据解码器和邻居缓存；通过软件方面和硬件方面的协同设计，实现图卷积网络gcn计算的加速。本发明提升了计算的并行度、架构的吞吐率和硬件的资源利用率。
[0023]
另外，根据本发明上述实施例的基于存内计算的图卷积网络软硬件协同加速方法还包括：
[0024]
进一步地，所述在进行图数据的存内计算中通过量化定点方式，将所述图数据的高位宽的浮点数转化为低位宽的定点数，包括：
[0025]
在基于所述rram的存内计算中，使用面向图卷积网络的量化定点方式，对于图卷积网络每一层的特征数据和网络权重，预设数据的总量化位宽，在预设总量化位宽width
total
后，根据待量化的数据，通过下述公式计算出分配给整数和小数部分的比特数width
int
与width
dec
：
[0026][0027]
width
dec
＝width
total-width
int
[0028]
进一步地，所述使用基于图聚类的映射算法，将所述图数据的原始图分割成多个子图得到聚类结果，并将所述多个子图的节点特征映射到用于计算特征聚合的rram交叉阵列上，包括：
[0029]
使用graclus算法将图数据的原始图聚类成多个子图，并最大化子图内的连接最小化子图间的连接得到聚类结果；
[0030]
根据所述聚类结果，将特征矩阵进行分割，并把不同子图的节点对应的特征向量映射到不同的阻变式随机访问存储器交叉阵列rram中；其中，每个所述交叉阵列计算对应子图内的节点的特征聚合。
[0031]
进一步地，所述方法还包括：预定义一个边删除率阈值t，并在边删除算法中使得所述原始图中每个节点删除的邻边数小于该节点原本的度数与t的乘积；其中，t的取值范围为0《t≤1。
[0032]
进一步地，所述边删除算法为：
[0033]
输入所述原始图的节点以及每个所述子图的信息；
[0034]
对于所述原始图中每个节点，迭代地选取参与这一节点特征聚合的子图；
[0035]
每次迭代时，选择一个覆盖了这一节点最多未被覆盖的邻居的子图，让其参与这一节点的特征聚合，当一个节点邻居被覆盖的比例大于等于t时，该迭代终止。
[0036]
进一步地，所述聚合核阵列包括多个基于rram的聚合核，所述多个基于rram的聚合核以片上网络的形式相互连接，以并行地进行矩阵向量乘的计算。
[0037]
进一步地，所述聚合核阵列以乒乓的工作形式分为工作区和更新区，当所述工作区执行特征聚合运算时，所述更新区把已经计算好的节点特征写入到rram交叉阵列中。
[0038]
进一步地，所述方法还包括：利用数据转发单元从相邻的单元或者自己对应的rram交叉阵列接收数据，经过合并处理后转发给相邻的其他单元，并以片上网络的形式组织，接受所述控制模块的控制。
[0039]
进一步地，所述向量组合阵列包括一个等待队列和多个mlp核心，用于并行计算gcn的向量组合阶段；其中，所述mlp核心使用rram交叉阵列计算矩阵向量乘，并使用查找表计算非线性激活函数，当计算gcn的向量组合阶段时，所述中间缓存中存储的中间数据将首被写入到所述向量组合阵列的等待队列中。
[0040]
为达到上述目的，本发明另一方面提出了一种基于存内计算的图卷积网络软硬件协同加速装置，包括：
[0041]
软件设计模块，用于在进行图数据的存内计算中通过量化定点方式，将所述图数据的高位宽的浮点数转化为低位宽的定点数；并使用基于图聚类的映射算法，将所述图数据的原始图分割成多个子图得到聚类结果，并将所述多个子图的节点特征映射到用于计算特征聚合的rram交叉阵列上；以及，基于所述聚类结果使用边删除方式，将所述聚类结果中连接不同所述子图的边进行删除，以通过面向硬件的部署算法将所述图数据部署到硬件上；
[0042]
硬件设计模块，用于配置计算模块和控制模块；其中，所述计算模块包括：聚合核阵列、向量组合阵列和中间缓存，所述聚合核阵列用于计算所述图数据的特征聚合，所述向量组合阵列用于计算所述图数据的向量组合，以及所述中间缓存用于所述聚合核阵列和所述向量组合阵列的数据交换；所述控制模块包括：指令队列、图数据解码器和邻居缓存，分别用于所述图数据的指令的暂存、格式转换以及邻接向量的暂存；
[0043]
协同加速模块，用于通过所述软件方面和所述硬件方面的协同设计，实现图卷积网络gcn计算的加速。
[0044]
根据本发明实施例的基于存内计算的图卷积网络软硬件协同加速装置，在软件方面，通过量化定点方式，将图数据的高位宽的浮点数转化为低位宽的定点数，将图数据的原始图分割成多个子图得到聚类结果，并将多个子图的节点特征映射到用于特征聚合的rram交叉阵列上，再使用边删除方式将聚类结果中连接不同子图的边删除，以将图数据部署到硬件上；在硬件方面，配置计算模块和控制模块，其中，计算模块包括：聚合核阵列、向量组
合阵列和中间缓存，控制模块包括：指令队列、图数据解码器和邻居缓存；通过软件方面和硬件方面的协同设计，实现图卷积网络gcn计算的加速。本发明提升了计算的并行度、架构的吞吐率和硬件的资源利用率。
[0045]
本发明的有益效果：
[0046]
(1)在软件层面，通过基于节点聚类的gcn映射算法将数据部署到多核的计算架构上，把大规模稀疏图转化成可以独立并行处理的小规模稠密的子图，增加了子图级别的计算并行度。在该算法的基础上，本发明提出了边删除技术，减少了聚合阶段通信代价的同时，也减少了子图之间的数据依赖性，从而进一步提升了子图级别的并行度。此外，本发明还提出了图数据量化方法减少了硬件的计算量和存储量。
[0047]
(2)硬件层面，本发明设计了基于rram存内计算的多核gcn计算架构，支持子图级别的并行计算。同时本发明还设计了层内流水线的数据流，进一步提升了架构的吞吐率。
[0048]
本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。
附图说明
[0049]
本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明显和容易理解，其中：
[0050]
图1为现有技术中的gcn的计算流程的示意图；
[0051]
图2为现有技术中的gpu计算gcn时特征向量维度与吞吐率的关系示意图；
[0052]
图3为根据本发明实施例的基于存内计算的图卷积网络软硬件协同加速方法的框架示意图；
[0053]
图4为根据本发明实施例的基于存内计算的图卷积网络软硬件协同加速方法的流程示意图；
[0054]
图5为根据本发明实施例的基于图聚类的gcn映射示意图；
[0055]
图6为根据本发明实施例的边删除技术的算法伪代码；
[0056]
图7为根据本发明实施例的基于存内计算的gcn计算架构示意图；
[0057]
图8为根据本发明实施例的延时和能耗实验结果示意图；
[0058]
图9为根据本发明实施例的精度与延时之间权衡的示意图；
[0059]
图10为根据本发明实施例的基于存内计算的图卷积网络软硬件协同加速装置的结构示意图。
具体实施方式
[0060]
需要说明的是，在不冲突的情况下，本技术中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本发明。
[0061]
为了使本技术领域的人员更好地理解本发明方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分的实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都应当属于本发明保护的范围。
[0062]
下面参照附图描述根据本发明实施例提出的基于存内计算的图卷积网络软硬件协同加速方法及装置，首先将参照附图描述根据本发明实施例提出的基于存内计算的图卷积网络软硬件协同加速方法。
[0063]
本发明实施例的整体框架如图3所示。在整个计算流的开始，设计了面向硬件的部署算法对图数据进行初步处理并确定数据映射方法，从而将数据部署到硬件上。首先会设计gcn的量化与定点方法，把高位宽的浮点数转化为低位宽的定点数，降低硬件部署和计算的代价。之后为了更好的把图结构映射到硬件上，提出了基于图聚类的映射算法，将大图分为多个子图，并把子图的节点特征映射到用于计算特征聚合的rram交叉阵列上。在映射结束之后，设计了边删除技术来进一步把不规则的图数据变得硬件友好。
[0064]
本发明实施例还设计了基于rram存内计算的硬件架构。架构的主要计算模块包含聚合核阵列和向量组合阵列。
[0065]
图4是本发明一个实施例的基于存内计算的图卷积网络软硬件协同加速方法的流程图。
[0066]
如图4所示，该基于存内计算的图卷积网络软硬件协同加速方法包括以下步骤：
[0067]
步骤s1，软件方面：在进行图数据的存内计算中通过量化定点方式，将图数据的高位宽的浮点数转化为低位宽的定点数；并使用基于图聚类的映射算法，将图数据的原始图分割成多个子图得到聚类结果，并将多个子图的节点特征映射到用于计算特征聚合的rram交叉阵列上；以及，基于聚类结果使用边删除方式，将聚类结果中连接不同子图的边进行删除，以通过面向硬件的部署算法将图数据部署到硬件上。
[0068]
具体地，软件方面的分为以下三部分：
[0069]
(1)量化定点方案设计。在基于rram的存内计算中，如果使用定点数计算，相比使用浮点数计算将会省去指数位上的加法运算，计算代价更小，硬件架构也更简单。在现有的面向cnn的存内计算架构中，大多数工作都采用定点数进行计算。同样，数据位宽也会影响存内计算架构的性能。gcn中原始图数据位宽一般为32位，如果直接使用32位数据进行存内计算，将会消耗大量存储空间，并需要更高精度的数模、模数转换接口。一般来说，数据位宽越小，计算所需的时间，能耗和面积就越小，但是精度损失也会越大。
[0070]
本发明实施例设计了一种面向gcn的量化定点方式。对于每一层的特征数据和网络权重，用户可以指定数据的总量化位宽。在总量化位宽width
total
给定后，算法根据待量化的数据，通过以下公式计算出分配给整数和小数部分的比特数width
int
与width
dec
：
[0071][0072]
width
dec
＝width
total-width
int
[0073]
如上述公式所示，该算法会根据数据的最大值和最小值，首先决定分配给整数部分的比特数。如果整数部分需要的比特数小于用户指定的量化位宽，则把剩余的比特数全部分配给小数部分。当整数部分和小数部分的位宽确定后，程序会根据位宽对数据的整数部分和小数部分分别进行均匀量化。
[0074]
(2)基于图聚类的映射算法。为了实现基于存内计算的稀疏矩阵乘法计算，存内计算架构需要把一个矩阵存储在rram交叉阵列上，并把另一个矩阵拆分成向量，通过计算多个矩阵向量乘来完成矩阵乘法。因为图中节点的个数往往比特征向量的维度多很多(例如arxiv数据集有169343个节点，而特征向量维度仅为128)，而且图结构一般非常稀疏(例如
pubmed数据集中邻接矩阵中只有0.028％的数据是非零的)，所以这里选择将特征矩阵存储在rram交叉阵列中来减少存储代价并提升资源利用率。具体来说，本发明的一个实施例把稠密的特征矩阵h映射到rram交叉阵列上，并把稀疏的邻接矩阵a转化成一系列连续的输入向量。然而，由于输入向量的数量众多以及图结构的超稀疏性，现存的存内计算架构需要多次迭代才能完成计算，并且每次迭代只会激活导通rram交叉阵列的很少一部分行参与计算，导致rram交叉阵列硬件资源利用率低。
[0075]
为了解决上述两个问题，本发明实施例提出了基于图聚类的映射方法。这种方法使用图聚类算法把稀疏的大图分割成很多更小更稠密的子图，并根据聚类结果把节点的特征向量分别映射到对应的rram交叉阵列上。这些交叉阵列可以同时执行计算，因而可以减少聚合过程中所需要的迭代次数。映射的过程见于图5。首先，本发明使用graclus算法，把图聚类成一个个较小的子图，并最大化子图内的连接，最小化子图间的连接。然后，根据聚类的结果，本发明实施例把特征矩阵进行分割，并把不同子图的节点对应的特征向量映射到不同的rram交叉阵列上。每个交叉阵列可以计算对应子图内的点的特征聚合，而且不同的交叉阵列可以并行工作。
[0076]
(3)边删除技术。除了从架构上对信息传递提供支持，本发明实施例还提出了边删除技术，通过删除子图间的边来减少数据通信代价并降低特征聚合中的计算依赖性。在图聚类映射之后，图中还存在着少量的跨子图边，这些边连接着属于不同子图的节点。在算法执行过程中，由于这些边的存在，负责不同子图的计算单元需要共同进行计算并合并计算结果，增加额外的通信代价和数据依赖性。因此，本发明实施例通过删除这些边来减少通信代价和数据依赖性。但是删除太多的边会导致gcn的准确率下降，为了控制删边的数量，本发明实施例定义了一个边删除率阈值t，并在算法中保证每个点删除的邻边数小于该点原本的度数与t的乘积。t的取值范围为0《t≤1，t越大代表可以接受的删边率越高。
[0077]
图6的伪代码展示了该算法的流程。算法的输入为图的节点，以及每个子图的信息。对于全图中每个节点，算法迭代地选取参与这一节点特征聚合的子图。每次迭代中，算法会选择一个覆盖了这一节点最多未被覆盖的邻居的子图(图6第4行)，让它参与这一节点的特征聚合(图6第6行)。当一个节点邻居被覆盖的比例大于等于t时，该迭代终止。用这种方法，本算法得到了每个节点的特征聚合所需要的子图有哪些，也即决定了哪些边被保留，哪些边被删除。
[0078]
步骤s2，硬件方面：配置计算模块和控制模块；其中，计算模块包括：聚合核阵列、向量组合阵列和中间缓存，聚合核阵列用于计算图数据的特征聚合，向量组合阵列用于计算图数据的向量组合，以及中间缓存用于聚合核阵列和向量组合阵列的数据交换；控制模块包括：指令队列、图数据解码器和邻居缓存，分别用于图数据的指令的暂存、格式转换以及邻接向量的暂存。
[0079]
具体地，在硬件层面，如图7所示，本发明实施例设计了基于rram存内计算的硬件架构来实现高并行度的存内gcn计算。整个架构主要包含控制模块和计算模块。计算模块包含一个用于计算特征聚合的聚合核阵列，一个用于计算向量组合的向量组合阵列，以及一个中间缓存用于两个阵列的数据交换。而控制模块包含了一个指令队列，一个图数据解码器和一个邻居缓存，分别用于指令的暂存、图数据从csr格式到邻接向量格式的转换、以及邻接向量的暂存。
[0080]
聚合核阵列(图7中的(a))包含了多个基于rram的聚合核，这些核以片上网络的形式相互连接(图7中的(b))，且可以并行地进行矩阵向量乘的计算。在特征聚合步骤，特征矩阵被静态地存储在多个rram交叉阵列上，而邻接矩阵分割得到的向量会被动态地从邻居缓存加载到聚合核上。在特征聚合的每一次迭代中，多个向量被从缓存中读出，然后通过数据转发单元发送到每个聚合核中。为了充分利用上文中映射算法带来的计算并行度，这些聚合核可以独立同时工作。因为子图间可能存在连接，所以本发明实施例为片上网络的数据转发单元添加了求和器，比较器等计算单元来支持结果数据的合并。同样，这些数据转发单元也可以并行独立工作。最后，合并后的结果将被送往中间缓存，等待之后的向量组合计算。
[0081]
在每个gcn网络层的最后，向量组合阶段的结果将用于更新特征矩阵，即写回聚合核阵列。为了把每层计算最后的密集的特征更新操作分散到迭代过程中，本发明实施例把聚合核阵列分成了两个部分，即工作区和更新区，二者以乒乓的形式工作。当工作区执行特征聚合运算时，更新区可以同时把已经计算好的节点特征写入到rram交叉阵列中。而在下一层的计算开始时，二者的角色将互换，即由原本的更新区承担计算的职责变更为工作区，进行特征聚合的计算，而原本的工作区承担更新的职责变更为更新区，用以存储计算的结果。
[0082]
聚合核的内部细节如图7中的(a)所示。为了支持不同的核大小，每个核都包含了多个rram交叉阵列，及其配套的外围电路组件。为了支持不同的聚合函数，本发明实施例在rram交叉阵列旁放置了比较器和加法器用来合并不同rram交叉阵列输出的结果。一方面，如果聚合函数是均值函数或求和函数，则使用数模转换器(dac)把输入向量转化成电压，和rram交叉阵列做矩阵向量乘之后，经由模数转换器(adc)读出结果。另一方面，如果聚合函数是最大值函数，则本发明实施例每次只导通rram交叉阵列的一行，利用比较器逐行比较最终选出最大值。
[0083]
数据转发单元的设计如图7中的(b)所示。数据转发单元可以从相邻的单元或者自己对应的rram交叉阵列接受数据，经过合并处理后转发给相邻的其他单元。它们以片上网络的形式组织，并接受控制模块的控制。
[0084]
如图7中的(c)所示，向量组合阵列包含了一个等待队列和多个mlp核心，它们可以并行计算gcn中的向量组合阶段。mlp核心使用rram交叉阵列来计算矩阵向量乘，并使用查找表来计算非线性激活函数。当计算gcn的向量组合阶段时，中间缓存中存储的中间数据将首先被写入到向量组合阵列的等待队列中。和聚合核不同，对于每一个gcn网络层，向量组合阵列的每一个mlp核心都存储了这一层所有的mlp权重。因此，等待队列中存储的向量可以被送到该层的任意一个空闲mlp核心中进行计算，使得向量组合阵列可以很好地继承聚合核阵列带来的节点级计算并行度。在每个mlp核心中，不同的mlp层的权重被储存在不同的rram交叉阵列上，因此不同的mlp层可以以流水线的形式工作。当第一个输入向量完成第一层的计算时，第二个输入向量就可以被加载到第一层的rram交叉阵列上准备进行第一层的矩阵向量乘。本发明实施例在mlp核心内设计多层计算的流水线，进一步提升了向量组合阵列的吞吐率。最后，mlp最后一层的计算结果将通过非线性激活函数的查找表得到最终结果，送入中间缓存等待被写回到更新区。
[0085]
受益于以乒乓形式工作的聚合核阵列，本发明实施例可以把gcn计算的一次迭代
过程分为特征聚合，向量组合和特征更新三个阶段。在同一次迭代中，这三个阶段将依次在聚合核当前的工作区，向量组合核，以及聚合核当前的更新区进行。因此，在进行gcn计算时，不同的gcn层依次进行计算，而在层内，特征聚合、向量组合和特征更新三个阶段可以以流水线的形式工作。在这种流水线形式的数据流中，原本集中在每层最后的特征更新操作被分散在整个计算过程中，并被特征聚合和向量组合操作的延时所隐藏，从而提升了架构的吞吐率。
[0086]
步骤s3，通过软件方面和硬件方面的协同设计，实现图卷积网络gcn计算的加速。
[0087]
可以理解的是，本发明先通过面向多核存内计算硬件设计gcn部署算法，解决了如何把不规则图数据映射到规模一定的硬件阵列上，并同时提升计算并行度的问题；在硬件层面，本发明解决了存内计算单元和数据流如何设计的问题。通过以上的软硬件协同设计，本发明解决了计算并行度低和资源利用率低的问题，最终实现gcn计算的加速。
[0088]
下面通过附图对本发明实施例做进一步阐述：
[0089]
具体地，本发明的实验效果如下：
[0090]
实验使用gcn模型，在四个典型数据集cora，citeseer，pubmed和arxiv上评价本发明实施例的性能。在存内计算基线架构和本发明的架构仿真中，rram，adc和dac的数据分别来源于其他文献。数字电路部分使用synopsys design compiler和tsmc65nm工艺在300mhz频率进行仿真。实验使用cacti进行缓存的仿真，缓存大小设置为64kb。同时，实验还使用dgl框架在40核的intel xeon e5-2630 v4 2.20ghz cpu和nvidia rtx 2080ti gpu上进行gcn的评估作为cpu和gpu基线。
[0091]
(1)延时、能耗仿真
[0092]
实验在四个数据集上比较了本发明和cpu、gpu、prime的延时、能耗，结果如图8所示。从图8中的(a)中可以看出，prime在gcn任务上相比cpu只取得了44～86倍的速度提升，这比它在cnn任务上的速度提升(1596～11802倍)低了很多，这是因为图数据极其稀疏，且边的连接不规则。通过使用上文介绍的软硬件协同设计，本发明实施例相比cpu，gpu和prime分别实现了87～664倍，45～120倍，2.79～12.49倍的速度提升。图8中的(b)展示了本发明的能效提升结果。相比cpu、gpu、prime，本发明实施例分别实现了2834～7108倍，172～606倍，2.42～5.33倍的能效提升。
[0093]
(2)准确率验证
[0094]
实验主要考虑两方面因素对gcn准确率的影响，分别是边删除技术和量化误差。本发明实施例使用边删除技术来删去横跨两个子图的边，并设置了一个边删除阈值t来限制删边的比例，从而控制精度的损失。因此在延时和准确率之间存在一个权衡：更大的阈值t意味着更多边被删除，延时会减少而精度损失会增加，反之同理。对于量化误差也有类似的结果，当量化比特数更高时，计算精度也会更高但是计算延时也会相应增大。因此，实验考虑了上述两个因素，测试了不同t和不同量化比特数下准确率和延时的变化情况，结果如图9所示。图9中的t代表边删除率阈值。当t变大时更多的边将会被删除。灰线代表了精度损失小于1％时对应最小延时的t值。可见在所有数据集中，随着延时的下降，准确率也呈现下降趋势。如果限定可接受的精度损失在1％以内，则图中灰色竖线指示了限制精度损失下的延时最优的t值选取。对于cora，citeseer，都可以使用8比特量化与t＝1。而对于pubmed，arxiv和reddit，需要使用12比特数据，且对于arxiv需要选取t不超过0.2，对于reddit需要
选取t不超过0.5。
[0095]
通过上述步骤，在软件方面，通过量化定点方式，将图数据的高位宽的浮点数转化为低位宽的定点数，将图数据的原始图分割成多个子图得到聚类结果，并将多个子图的节点特征映射到用于特征聚合的rram交叉阵列上，再使用边删除方式将聚类结果中连接不同子图的边删除，以将图数据部署到硬件上；在硬件方面，配置计算模块和控制模块，其中，计算模块包括：聚合核阵列、向量组合阵列和中间缓存，控制模块包括：指令队列、图数据解码器和邻居缓存；通过软件方面和硬件方面的协同设计，实现图卷积网络gcn计算的加速。本发明提升了计算的并行度、架构的吞吐率和硬件的资源利用率。
[0096]
为了实现上述实施例，如图10所示，本实施例中还提供了一种基于存内计算的图卷积网络软硬件协同加速装置10，该装置10包括：软件设计模块100，硬件设计模块200，协同加速模块300。
[0097]
软件设计模块100，用于在进行图数据的存内计算中通过量化定点方式，将图数据的高位宽的浮点数转化为低位宽的定点数；并使用基于图聚类的映射算法，将图数据的原始图分割成多个子图得到聚类结果，并将多个子图的节点特征映射到用于计算特征聚合的rram交叉阵列上；以及，基于聚类结果使用边删除方式，将聚类结果中连接不同子图的边进行删除，以通过面向硬件的部署算法将图数据部署到硬件上；
[0098]
硬件设计模块200，用于配置计算模块和控制模块；其中，计算模块包括：聚合核阵列、向量组合阵列和中间缓存，聚合核阵列用于计算图数据的特征聚合，向量组合阵列用于计算图数据的向量组合，以及中间缓存用于聚合核阵列和向量组合阵列的数据交换；控制模块包括：指令队列、图数据解码器和邻居缓存，分别用于图数据的指令的暂存、格式转换以及邻接向量的暂存；
[0099]
协同加速模块300，用于通过软件方面和硬件方面的协同设计，实现图卷积网络gcn计算的加速。
[0100]
根据本发明实施例的基于存内计算的图卷积网络软硬件协同加速装置，在软件方面，通过量化定点方式，将图数据的高位宽的浮点数转化为低位宽的定点数，将图数据的原始图分割成多个子图得到聚类结果，并将多个子图的节点特征映射到用于特征聚合的rram交叉阵列上，再使用边删除方式将聚类结果中连接不同子图的边删除，以将图数据部署到硬件上；在硬件方面，配置计算模块和控制模块，其中，计算模块包括：聚合核阵列、向量组合阵列和中间缓存，控制模块包括：指令队列、图数据解码器和邻居缓存；通过软件方面和硬件方面的协同设计，实现图卷积网络gcn计算的加速。本发明提升了计算的并行度、架构的吞吐率和硬件的资源利用率。
[0101]
需要说明的是，前述对基于存内计算的图卷积网络软硬件协同加速方法实施例的解释说明也适用于该实施例的基于存内计算的图卷积网络软硬件协同加速装置，此处不再赘述。
[0102]
此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。
[0103]
在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示
例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。
[0104]
尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。
技术特征：1.一种基于存内计算的图卷积网络软硬件协同加速方法，其特征在于，包括以下步骤：软件方面：在进行图数据的存内计算中通过量化定点方式，将所述图数据的高位宽的浮点数转化为低位宽的定点数；并使用基于图聚类的映射算法，将所述图数据的原始图分割成多个子图得到聚类结果，并将所述多个子图的节点特征映射到用于计算特征聚合的rram交叉阵列上；以及，基于所述聚类结果使用边删除方式，将所述聚类结果中连接不同所述子图的边进行删除，以通过面向硬件的部署算法将所述图数据部署到硬件上；硬件方面：配置计算模块和控制模块；其中，所述计算模块包括：聚合核阵列、向量组合阵列和中间缓存，所述聚合核阵列用于计算所述图数据的特征聚合，所述向量组合阵列用于计算所述图数据的向量组合，以及所述中间缓存用于所述聚合核阵列和所述向量组合阵列的数据交换；所述控制模块包括：指令队列、图数据解码器和邻居缓存，分别用于所述图数据的指令的暂存、格式转换以及邻接向量的暂存；通过所述软件方面和所述硬件方面的协同设计，实现图卷积网络gcn计算的加速。2.根据权利要求1所述的方法，其特征在于，所述在进行图数据的存内计算中通过量化定点方式，将所述图数据的高位宽的浮点数转化为低位宽的定点数，包括：在基于所述rram的存内计算中，使用面向图卷积网络的量化定点方式，对于图卷积网络每一层的特征数据和网络权重，预设数据的总量化位宽，在预设总量化位宽width
total
后，根据待量化的数据，通过下述公式计算出分配给整数和小数部分的比特数width
int
与width
dec
：width
dec
＝width
total-width
int
3.根据权利要求1所述的方法，其特征在于，所述使用基于图聚类的映射算法，将所述图数据的原始图分割成多个子图得到聚类结果，并将所述多个子图的节点特征映射到用于计算特征聚合的rram交叉阵列上，包括：使用graclus算法将图数据的原始图聚类成多个子图，并最大化子图内的连接最小化子图间的连接得到聚类结果；根据所述聚类结果，将特征矩阵进行分割，并把不同子图的节点对应的特征向量映射到不同的阻变式随机访问存储器交叉阵列rram中；其中，每个所述交叉阵列计算对应子图内的节点的特征聚合。4.根据权利要求3所述的方法，其特征在于，所述方法还包括：预定义一个边删除率阈值t，并在边删除算法中使得所述原始图中每个节点删除的邻边数小于该节点原本的度数与t的乘积；其中，t的取值范围为0<t≤1。5.根据权利要求4所述的方法，其特征在于，所述边删除算法为：输入所述原始图的节点以及每个所述子图的信息；对于所述原始图中每个节点，迭代地选取参与这一节点特征聚合的子图；每次迭代时，选择一个覆盖了这一节点最多未被覆盖的邻居的子图，让其参与这一节点的特征聚合，当一个节点邻居被覆盖的比例大于等于t时，该迭代终止。6.根据权利要求1所述的方法，其特征在于，所述聚合核阵列包括多个基于rram的聚合核，所述多个基于rram的聚合核以片上网络的形式相互连接，以并行地进行矩阵向量乘的
计算。7.根据权利要求1所述的方法，其特征在于，所述聚合核阵列以乒乓的工作形式分为工作区和更新区，当所述工作区执行特征聚合运算时，所述更新区把已经计算好的节点特征写入到rram交叉阵列中。8.根据权利要求1所述的方法，其特征在于，所述方法还包括：利用数据转发单元从相邻的单元或者自己对应的rram交叉阵列接收数据，经过合并处理后转发给相邻的其他单元，并以片上网络的形式组织，接受所述控制模块的控制。9.根据权利要求1所述的方法，其特征在于，所述向量组合阵列包括一个等待队列和多个mlp核心，用于并行计算gcn的向量组合阶段；其中，所述mlp核心使用rram交叉阵列计算矩阵向量乘，并使用查找表计算非线性激活函数，当计算gcn的向量组合阶段时，所述中间缓存中存储的中间数据将首被写入到所述向量组合阵列的等待队列中。10.一种基于存内计算的图卷积网络软硬件协同加速装置，其特征在于，包括：软件设计模块，用于在进行图数据的存内计算中通过量化定点方式，将所述图数据的高位宽的浮点数转化为低位宽的定点数；并使用基于图聚类的映射算法，将所述图数据的原始图分割成多个子图得到聚类结果，并将所述多个子图的节点特征映射到用于计算特征聚合的rram交叉阵列上；以及，基于所述聚类结果使用边删除方式，将所述聚类结果中连接不同所述子图的边进行删除，以通过面向硬件的部署算法将所述图数据部署到硬件上；硬件设计模块，用于配置计算模块和控制模块；其中，所述计算模块包括：聚合核阵列、向量组合阵列和中间缓存，所述聚合核阵列用于计算所述图数据的特征聚合，所述向量组合阵列用于计算所述图数据的向量组合，以及所述中间缓存用于所述聚合核阵列和所述向量组合阵列的数据交换；所述控制模块包括：指令队列、图数据解码器和邻居缓存，分别用于所述图数据的指令的暂存、格式转换以及邻接向量的暂存；协同加速模块，用于通过所述软件方面和所述硬件方面的协同设计，实现图卷积网络gcn计算的加速。
技术总结本发明公开了一种基于存内计算的图卷积网络软硬件协同加速方法，该方法包括：在软件方面，通过量化定点方式，将图数据的高位宽的浮点数转化为低位宽的定点数，将图数据的原始图分割成多个子图得到聚类结果，并将多个子图的节点特征映射到用于特征聚合的RRAM交叉阵列上，再使用边删除方式将聚类结果中连接不同子图的边删除，以将图数据部署到硬件上；在硬件方面，配置计算模块和控制模块，其中，计算模块包括：聚合核阵列、向量组合阵列和中间缓存，控制模块包括：指令队列、图数据解码器和邻居缓存；通过软件方面和硬件方面的协同设计，实现图卷积网络GCN计算的加速。本发明提升了计算的并行度、架构的吞吐率和硬件的资源利用率。率。率。
技术研发人员：汪玉 朱昱 朱振华 戴国浩 杨华中
受保护的技术使用者：清华大学
技术研发日：2022.03.17
技术公布日：2022/7/5
