一种图卷积神经网络的加速方法及装置、电子设备

1.本技术涉及图卷积神经网络技术领域，尤其涉及一种图卷积神经网络的加速方法及装置、电子设备。


背景技术：

2.近年来图神经网络被广泛应用于流量预测、对象检测、疾病分类、自动驾驶等。其中图卷积神经网络作为最成功的模型之一，其运行主要由两个阶段构成：聚合和组合。组合阶段的计算与传统神经网络类似，然而聚合阶段依赖于图结构，而图结构通常是稀疏和不规则的。稀疏性和不规则性将是设计图卷积神经网络结构的新挑战。
3.聚合和组合需要连续计算三个矩阵，分别是：邻接矩阵，特征矩阵，权重矩阵。其中邻接矩阵和特征矩阵属于稀疏矩阵，是指其非零元素只占矩阵元素总数的小部分，其余大部分为零。其中邻接矩阵为极稀疏矩阵，是指非零元素所占矩阵比例不到1％。权重矩阵通常是密集矩阵。
4.通常在图卷积神经网络的计算中，将计算顺序变为先进行聚合，再进行组合。也就变成了两次稀疏-密集矩阵乘法(spmm，sparse-densematrix multiplication)。在深度学习的计算中，特别是图卷积神经网络，高效处理spmm已经成为提高模型训练和推理速度的关键，也是缩减模型参数量的重要手段之一。为了实现高性能训练和推理图卷积神经网络，加速spmm具有十分重要的意义。
5.在硬件中，为了减少稀疏矩阵占用的存储空间以及提高计算效率，通常采用稀疏格式来表示稀疏矩阵。在基于pytorch的图神经网络框架pyg(pytorch geometric)中，通常采用csr，csc，coo等常用稀疏格式来表示稀疏矩阵。但对于邻接矩阵这样密集度低于1％的稀疏矩阵来说，上述稀疏格式不能很好的表示这类矩阵。其局限性主要有：
①
这类稀疏矩阵在1％密集度的大矩阵时所占用的内存量较大，需要较多冗余字节来表示行或列的信息；
②
加速器在运算上述稀疏格式表达的稀疏矩阵时，因为其主要以行或列为信息，容易使运算单元分配到的非零值不等，进而导致负载不平衡。


技术实现要素：

6.本技术实施例的目的是提供一种图卷积神经网络的加速方法及装置、电子设备，以解决现有稀疏格式针对图卷积神经网络中极稀疏矩阵的低效率，以及pe负载不平衡的问题，本发明能够提高pe阵列的运算利用率，提高图卷积神经网络中spmm的运算效率。
7.根据本技术实施例的第一方面，提供一种图卷积神经网络的加速方法，其特征在于，包括：
8.将邻接矩阵和特征矩阵使用稀疏格式ccl表示，所述邻接矩阵和特征矩阵为gcn模型通过pyg框架得到的原始数据；
9.将使用ccl表示的稀疏数据按照pe数来进行优先调度排列，并将经过优先调度排列好的数据存储在片外存储器；
10.加速器获取特征矩阵，并按照优先调度的顺序分发到每个pe中，与pe内部缓存的权重矩阵进行输出优先的外积计算；
11.根据所述特征矩阵的hat位来判断该稀疏矩阵行是否计算完毕；
12.当所述特征矩阵和所述权重矩阵计算完毕生成中间矩阵后，加速器继续获取邻接矩阵，并按照优先调度的顺序分发到每个pe中；
13.根据稀疏数据的列坐标，pe从向量存储器群读取相应的行向量，并进行外积运算，最终得到三个矩阵相乘的计算结果。
14.可选的，所述将邻接矩阵和特征矩阵使用稀疏格式ccl表示，包括：
15.将邻接矩阵和特征矩阵使用稀疏格式ccl表示，其中ccl稀疏格式包括val、col、hat三个数组；
16.其中val数组按行顺序存储稀疏矩阵中的非零值；col数组按照val数组的顺序存储其非零元素的列坐标；hat数组按照val数组的顺序存储其非零元素的行位置信息。
17.可选的，hat数组按照val数组的顺序存储其非零元素的行位置信息，包括：
18.hat数组由2bits表示，其中2'b10表示该非零元素所在位置为所在行中非零元素的首位，2'b01表示该非零元素所在位置为所在行中非零元素的末位，2'b11表示该非零元素为该行唯一的非零元素，2'b00表示该非零元素所在位置为所在行中非零元素的中间位置。
19.可选的，将使用ccl表示的稀疏数据按照pe数来进行优先调度排列，包括：
20.将稀疏矩阵按照行顺序依次分配给pe，当存在pe先计算完成时，立马为pe分配新的一行，而不是等待所有的pe运算完后再集中读取。
21.可选的，加速器获取特征矩阵，并按照优先调度的顺序分发到每个pe中，与pe内部缓存的权重矩阵进行输出优先的外积计算，包括：
22.pe收到以ccl稀疏格式表示的稀疏数据，将val数组中的数据传入到先进先出；
23.将col数组中的数据读取出来，并使用特征矩阵非零值的列坐标索引权重矩阵的行向量；
24.加速器获取特征矩阵，并按照优先调度的顺序分发到每个pe中，与pe内部缓存的权重矩阵进行输出优先的外积计算；
25.将读取到的行向量与先进先出中的非零值进行标量
×
向量计算，得到的结果暂存在pe的输出缓存中。
26.可选的，根据所述特征矩阵的hat位来判断该稀疏矩阵行是否计算完毕，包括：
27.当hat位为2'b01或2'b11时，表示该外积运算输出矩阵的行向量计算完毕，把该中间矩阵行发送到向量存储器群，等待下一次的外积运算；
28.当hat位为2'b10或2'b00时，表示该外积运算输出矩阵的行向量仍然需要计算，pe继续读取该稀疏矩阵行的非零元素值，来进行外积运算和累加。
29.可选的，根据稀疏数据的列坐标，pe从向量存储器群读取相应的行向量，并进行外积运算，最终得到三个矩阵相乘的计算结果，包括：
30.根据邻接矩阵的列坐标，pe从向量存储器群读取相应的行向量，并进行外积运算，最终得到三个矩阵相乘的计算结果。
31.根据本技术实施例的第二方面，提供一种图卷积神经网络的加速装置，包括：
32.ccl编码模块，用于将邻接矩阵和特征矩阵使用稀疏格式ccl表示，所述邻接矩阵和特征矩阵为gcn模型通过pyg框架得到的原始数据；
33.ccl调度模块，用于将使用ccl表示的稀疏数据按照pe数来进行优先调度排列，并将经过优先调度排列好的数据存储在片外存储器；
34.数据分配模块，用于加速器获取特征矩阵，并按照优先调度的顺序分发到每个pe中，与pe内部缓存的权重矩阵进行输出优先的外积计算；
35.判断模块，用于根据所述特征矩阵的hat位来判断该稀疏矩阵行是否计算完毕；
36.数据计算模块，用于当所述特征矩阵和所述权重矩阵计算完毕生成中间矩阵后，加速器继续获取邻接矩阵，并按照优先调度的顺序分发到每个pe中；
37.片上网络模块，用于根据稀疏数据的列坐标，pe从向量存储器群读取相应的行向量，并进行外积运算，最终得到三个矩阵相乘的计算结果。
38.根据本技术实施例的第三方面，提供一种电子设备，包括：
39.一个或多个处理器；
40.存储器，用于存储一个或多个程序；
41.当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现如第一方面所述的方法。
42.根据本技术实施例的第四方面，提供一种计算机可读存储介质，其上存储有计算机指令，其特征在于，该指令被处理器执行时实现如第一方面所述方法的步骤。
43.本技术的实施例提供的技术方案可以包括以下有益效果：
44.由上述实施例可知，本技术采用ccl编码格式及优先调度算法，克服了传统稀疏编码格式导致的对冗余字节过多表示，以及在多个pes进行并行计算时所导致的负载不平衡现象。进而充分对密集度小于1％的极稀疏矩阵进行压缩，充分节省片上存储资源，并且使pes之间负载平衡，充分利用硬件资源。
45.应当理解的是，以上的一般描述和后文的细节描述仅是示例性和解释性的，并不能限制本技术。
附图说明
46.此处的附图被并入说明书中并构成本说明书的一部分，示出了符合本技术的实施例，并与说明书一起用于解释本技术的原理。
47.图1是本发明实施例提供的一种图卷积神经网络的加速方法的流程图。
48.图2是本发明实施例提供的ccl稀疏格式表示方法示意图。
49.图3是本发明实施例提供的对稀疏矩阵采用优先调度处理方法示意图。
50.图4是本发明实施例提供的一种图卷积神经网络的加速装置的框图。
具体实施方式
51.下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
52.参见图1，图1是本发明实施例提供的一种图卷积神经网络的加速方法的流程图，所述图卷积神经网络的加速方法，包括：
53.s1、将邻接矩阵和特征矩阵使用稀疏格式ccl表示，所述邻接矩阵和特征矩阵为gcn模型通过pyg框架得到的原始数据；
54.s2、将使用ccl表示的稀疏数据按照pe数来进行优先调度排列，并将经过优先调度排列好的数据存储在片外存储器；
55.s3、加速器获取特征矩阵，并按照优先调度的顺序分发到每个pe中，与pe内部缓存的权重矩阵进行输出优先的外积计算；
56.s4、根据所述特征矩阵的hat位来判断该稀疏矩阵行是否计算完毕；
57.s5、当所述特征矩阵和所述权重矩阵计算完毕生成中间矩阵后，加速器继续获取邻接矩阵，并按照优先调度的顺序分发到每个pe中；
58.s6、根据邻接矩阵的列坐标，pe从向量存储器群读取相应的行向量，并进行外积运算，最终得到三个矩阵相乘的计算结果。
59.由上述实施例可知，本技术通过采用稀疏格式ccl对密集度小于1％的极稀疏矩阵进行压缩，充分节省片上资源，并利于对稀疏矩阵和密集矩阵进行计算。并且通过采用优先调度，改变了稀疏矩阵运算所导致了负载不平衡现象，大大提升矩阵运算效率。并通过设计针对ccl相应的硬件模块，完成gcn三个矩阵计算。
60.具体地，在步骤s1将邻接矩阵和特征矩阵使用全新稀疏格式ccl表示之前，所述图卷积神经网络的加速方法还包括：
61.将邻接矩阵、特征矩阵划分为小块，具体大小取决于硬件架构的设计；
62.具体地，在步骤s1中，所述gcn模型为最经典的双层gcn模型，经过pyg网络框架训练而得到的gcn模型。
63.具体地，在步骤s1中，所述矩阵数据为推理过程中需要计算的数据，数据格式为fp32，对于图卷积神经网络训练方法和训练加速器本发明暂不涉及。
64.示例性地，在步骤s1中，稀疏矩阵的大小为4*4，如图2所示，图2为一个4*4的稀疏矩阵使用ccl稀疏格式表示后的结果。该实例中，稀疏矩阵中的大写字母表示矩阵里的非零值，ccl使用三个数组来对齐进行表示，分别是：val、col和hat。其中val数组按行顺序存储稀疏矩阵中的非零值；col数组按照val数组的顺序存储其非零元素的列坐标；hat数组按照val数组的顺序存储其非零元素的行位置信息，hat数组由2bits表示，其中2'b10表示该非零元素所在位置为所在行中非零元素的首位，2'b01表示该非零元素所在位置为所在行中非零元素的末位，2'b11表示该非零元素为该行唯一的非零元素，2'b00表示该非零元素所在位置为所在行中非零元素的中间位置。
65.具体地，在步骤s2中，所述片外存储器为双倍速率同步动态随机存储器(doubledataratesdram，ddr)，其存储方式为连续存储。
66.示例性地，在步骤s2中，稀疏矩阵大小为8*8，pe数量为4，如图3所示，图3为一个8*8的稀疏矩阵通过优先调度分配到4个pe。该实例中，稀疏矩阵按照行顺序依次分配给pe，如果未经处理，当pe1和pe2先计算完成后，还需要等待pe0和pe3计算完成；当一个周期后pe0完成时，pe0、pe1和pe2还需等待pe3计算完成。当pe3完成后，pe1和pe2等待了两个周期，pe0等待了一个周期。而经过优先调度的后，当pe1和pe2计算完稀疏矩阵的第一行和第二行时，
立马为其分配稀疏矩阵的第四行和第五行；当pe0计算完稀疏矩阵的第零行时，立马为其分配稀疏矩阵的第六行；当pe3计算完稀疏矩阵的第三行时，立马为其分配稀疏矩阵的第七行。
67.优选地，在步骤s2中，提前将稀疏矩阵按照优先调度的方式排列，并将排列好的数据存储到片外存储器中。
68.具体地，在步骤s3中，加速器获取特征矩阵，并按照优先调度的顺序分发到每个pe中，与pe内部缓存的权重矩阵进行输出优先的外积计算，包括：
69.s31、pe收到以ccl稀疏格式表示的稀疏数据，将val数组中的数据传入到先进先出；
70.s32、将col数组中的数据读取出来，并使用特征矩阵非零值的列坐标索引权重矩阵的行向量；
71.s33、将读取到的行向量与先进先出中的非零值进行标量
×
向量计算，得到的结果暂存在pe的输出缓存中。
72.具体地，在步骤s33中，将读取到的行向量与fifo中的非零值进行标量
×
向量计算，得到的结果暂存在pe的输出缓存中，包括：
73.优选地，通过mac阵列来进行标量
×
向量运算，其中mac阵列中mac的个数取决于读取到的权重矩阵向量长度，本发明使用的mac个数为16。
74.具体地，在步骤s4中，根据特征矩阵的hat位来判断该稀疏矩阵行是否计算完毕，包括：
75.当hat位为2'b01或2'b11时，表示该外积运算输出矩阵的行向量计算完毕，把该中间矩阵行发送到向量存储器群，等待下一次的外积运算；
76.当hat位为2'b10或2'b00时，表示该外积运算输出矩阵的行向量仍然需要计算，pe继续读取该稀疏矩阵行的非零元素值，来进行外积运算和累加；
77.具体地，在步骤s5中，当特征矩阵和权重矩阵计算完毕生成中间矩阵后，加速器继续获取邻接矩阵，并按照优先调度的顺序分发到每个pe中，包括：
78.当特征矩阵和权重矩阵计算完成后，生成的中间矩阵存储到向量存储器群，方便下一轮spmm计算时被pe阵列读取；
79.具体地，在步骤s6中，根据邻接矩阵的列坐标，pe从向量存储器群读取相应的行向量，并进行外积运算，最终得到三个矩阵相乘的计算结果。本发明实施例所提供的图卷积神经网络加速方法，通过将稀疏数据采用ccl稀疏格式表示，并通过优先调度排列后存储到ddr中供加速器读取，有利于输出重用的外积运算方法，并且提高了pe阵列进行标量
×
向量运算的资源利用率，达到了负载平衡，进而提高了数据运行效率。
80.与前述的图卷积神经网络的加速方法的实施例相对应，本技术还提供了图卷积神经网络的加速装置的实施例。
81.图4是根据一示例性实施例示出的一种图卷积神经网络的加速装置框图。
82.参照图4，该装置包括：
83.ccl编码模块，用于将邻接矩阵和特征矩阵使用稀疏格式ccl表示，所述邻接矩阵和特征矩阵为gcn模型通过pyg框架得到的原始数据；
84.ccl调度模块，用于将使用ccl表示的稀疏数据按照pe数来进行优先调度排列，并
将经过优先调度排列好的数据存储在片外存储器；
85.数据分配模块，用于加速器获取特征矩阵，并按照优先调度的顺序分发到每个pe中，与pe内部缓存的权重矩阵进行输出优先的外积计算；
86.判断模块，用于根据所述特征矩阵的hat位来判断该稀疏矩阵行是否计算完毕；
87.数据计算模块，用于当所述特征矩阵和所述权重矩阵计算完毕生成中间矩阵后，加速器继续获取邻接矩阵，并按照优先调度的顺序分发到每个pe中；
88.片上网络模块，用于根据稀疏数据的列坐标，pe从向量存储器群读取相应的行向量，并进行外积运算，最终得到三个矩阵相乘的计算结果。
89.关于上述实施例中的装置，其中各个模块执行操作的具体方式已经在有关该方法的实施例中进行了详细描述，此处将不做详细阐述说明。
90.对于装置实施例而言，由于其基本对应于方法实施例，所以相关之处参见方法实施例的部分说明即可。以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本技术方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。
91.相应的，本技术还提供一种电子设备，包括：一个或多个处理器；存储器，用于存储一个或多个程序；当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现如上述的图卷积神经网络的加速方法。
92.相应的，本技术还提供一种计算机可读存储介质，其上存储有计算机指令，该指令被处理器执行时实现如上述的图卷积神经网络的加速方法。
93.本领域技术人员在考虑说明书及实践这里公开的内容后，将容易想到本技术的其它实施方案。本技术旨在涵盖本技术的任何变型、用途或者适应性变化，这些变型、用途或者适应性变化遵循本技术的一般性原理并包括本技术未公开的本技术领域中的公知常识或惯用技术手段。说明书和实施例仅被视为示例性的，本技术的真正范围和精神由权利要求指出。
94.应当理解的是，本技术并不局限于上面已经描述并在附图中示出的精确结构，并且可以在不脱离其范围进行各种修改和改变。本技术的范围仅由所附的权利要求来限制。

技术特征：
1.一种图卷积神经网络的加速方法，其特征在于，包括：将邻接矩阵和特征矩阵使用稀疏格式ccl表示，所述邻接矩阵和特征矩阵为gcn模型通过pyg框架得到的原始数据；将使用ccl表示的稀疏数据按照pe数来进行优先调度排列，并将经过优先调度排列好的数据存储在片外存储器；加速器获取特征矩阵，并按照优先调度的顺序分发到每个pe中，与pe内部缓存的权重矩阵进行输出优先的外积计算；根据所述特征矩阵的hat位来判断该稀疏矩阵行是否计算完毕；当所述特征矩阵和所述权重矩阵计算完毕生成中间矩阵后，加速器继续获取邻接矩阵，并按照优先调度的顺序分发到每个pe中；根据稀疏数据的列坐标，pe从向量存储器群读取相应的行向量，并进行外积运算，最终得到三个矩阵相乘的计算结果。2.如权利要求1所述的图卷积神经网络加速方法，其特征在于，所述将邻接矩阵和特征矩阵使用稀疏格式ccl表示，包括：将邻接矩阵和特征矩阵使用稀疏格式ccl表示，其中ccl稀疏格式包括val、col、hat三个数组；其中val数组按行顺序存储稀疏矩阵中的非零值；col数组按照val数组的顺序存储其非零元素的列坐标；hat数组按照val数组的顺序存储其非零元素的行位置信息。3.如权利要求2所述的图卷积神经网络加速方法，其特征在于，hat数组按照val数组的顺序存储其非零元素的行位置信息，包括：hat数组由2bits表示，其中2'b10表示该非零元素所在位置为所在行中非零元素的首位，2'b01表示该非零元素所在位置为所在行中非零元素的末位，2'b11表示该非零元素为该行唯一的非零元素，2'b00表示该非零元素所在位置为所在行中非零元素的中间位置。4.如权利要求1所述的图卷积神经网络加速方法，其特征在于，将使用ccl表示的稀疏数据按照pe数来进行优先调度排列，包括：将稀疏矩阵按照行顺序依次分配给pe，当存在pe先计算完成时，立马为pe分配新的一行，而不是等待所有的pe运算完后再集中读取。5.如权利要求1所述的图卷积神经网络加速方法，其特征在于，加速器获取特征矩阵，并按照优先调度的顺序分发到每个pe中，与pe内部缓存的权重矩阵进行输出优先的外积计算，包括：pe收到以ccl稀疏格式表示的稀疏数据，将val数组中的数据传入到先进先出；将col数组中的数据读取出来，并使用特征矩阵非零值的列坐标索引权重矩阵的行向量；加速器获取特征矩阵，并按照优先调度的顺序分发到每个pe中，与pe内部缓存的权重矩阵进行输出优先的外积计算；将读取到的行向量与先进先出中的非零值进行标量
×
向量计算，得到的结果暂存在pe的输出缓存中。6.如权利要求1所述的图卷积神经网络加速方法，其特征在于，根据所述特征矩阵的hat位来判断该稀疏矩阵行是否计算完毕，包括：
当hat位为2'b01或2'b11时，表示该外积运算输出矩阵的行向量计算完毕，把该中间矩阵行发送到向量存储器群，等待下一次的外积运算；当hat位为2'b10或2'b00时，表示该外积运算输出矩阵的行向量仍然需要计算，pe继续读取该稀疏矩阵行的非零元素值，来进行外积运算和累加。7.如权利要求1所述的图卷积神经网络加速方法，其特征在于，根据稀疏数据的列坐标，pe从向量存储器群读取相应的行向量，并进行外积运算，最终得到三个矩阵相乘的计算结果，包括：根据邻接矩阵的列坐标，pe从向量存储器群读取相应的行向量，并进行外积运算，最终得到三个矩阵相乘的计算结果。8.一种图卷积神经网络的加速装置，其特征在于，包括：ccl编码模块，用于将邻接矩阵和特征矩阵使用稀疏格式ccl表示，所述邻接矩阵和特征矩阵为gcn模型通过pyg框架得到的原始数据；ccl调度模块，用于将使用ccl表示的稀疏数据按照pe数来进行优先调度排列，并将经过优先调度排列好的数据存储在片外存储器；数据分配模块，用于加速器获取特征矩阵，并按照优先调度的顺序分发到每个pe中，与pe内部缓存的权重矩阵进行输出优先的外积计算；判断模块，用于根据所述特征矩阵的hat位来判断该稀疏矩阵行是否计算完毕；数据计算模块，用于当所述特征矩阵和所述权重矩阵计算完毕生成中间矩阵后，加速器继续获取邻接矩阵，并按照优先调度的顺序分发到每个pe中；片上网络模块，用于根据稀疏数据的列坐标，pe从向量存储器群读取相应的行向量，并进行外积运算，最终得到三个矩阵相乘的计算结果。9.一种电子设备，其特征在于，包括：一个或多个处理器；存储器，用于存储一个或多个程序；当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现如权利要求1-7任一项所述的方法。10.一种计算机可读存储介质，其上存储有计算机指令，其特征在于，该指令被处理器执行时实现如权利要求1-7中任一项所述方法的步骤。

技术总结
本发明公开了一种图卷积神经网络的加速方法，将邻接矩阵和特征矩阵使用全新的稀疏格式CCL表示，将使用CCL表示的稀疏数据按照PE个数来进行优先调度排列并存入到片外存储器，加速器通过总线获取特征矩阵，并按照优先调度的顺序分发到每个PE中，与权重矩阵行向量进行外积计算，根据特征矩阵的HAT位来判断该稀疏矩阵行是否计算完毕，当特征矩阵和权重矩阵计算完毕生成中间矩阵后，加速器继续获取邻接矩阵，并按照优先调度的顺序分发到每个PE中，根据稀疏数据的列坐标，PE从向量存储器群读取相应的行向量，并进行外积运算，最终得到三个矩阵相乘的计算结果。阵相乘的计算结果。阵相乘的计算结果。


技术研发人员：张培勇 崔英博
受保护的技术使用者：浙江大学
技术研发日：2023.04.04
技术公布日：2023/7/20