新兴的图神经网络（GNN）同时具有图处理和神经网络（NN）的计算特性，传统的图加速器和NN加速器无法同时满足GNN应用的双重计算需求。我们分析了GNN推理的计算瓶颈，并提出了基于ReRAM的数模混合异构加速器。在本文中提出了一种基于ReRAM的内存中处理（PIM）架构用于GNN加速，称为ReGNN。该架构主要由用于加速矩阵向量乘法（MVM）操作的APIM模块和用于加速非MVM聚合操作的DPIM模块组成。同时，为了提高数据并行性，ReGNN根据顶点的度数和特征向量的维度在聚合引擎中设计了顶点调度器，将数据映射到相应的聚合子引擎。我们以聚合操作中常见的MAX运算为例，提供了DPIM中详细的数据映射和数据处理步骤。基于两个经典的GNN模型和4种数据集对ReGNN进行了实验评估，实验结果表明，与GPU和基于ReRAM的GNN加速器ReGraphX相比，ReGNN将GNN推理速度分别提高了228×和8.4×，能耗降低了305.2×和10.5×。
该成果“ReGNN: A ReRAM-based Heterogeneous Architecture for General Graph Neural Networks”被设计自动化领域顶级国际会议Design Automation Conference（DAC'22）录用，是中国计算机学会（CCF）推荐的A类会议。
论文链接：
https://doi.org/10.1145/3489517.3530479
摘要
图神经网络（GNNs）具有图数据的不规则内存访问和神经网络的密集计算特性。在每个图卷积层中，GNN依据图结构聚合顶点的特征向量，并通过将其应用于权重矩阵来线性改变聚合结果，这两个阶段分别称为聚合和组合。传统的图加速器和神经网络加速器不能同时满足图神经网络应用的这些双重特性。首先，模拟ReRAM只支持MVM操作，GNN模型聚合阶段的非MVM操作不适用于模拟PIM（APIM）阵列。非MVM操作通常由外围电路处理，这大大降低了性能，增加了区域开销。其次，由于高维特征向量需要按顺序处理，现有的加速器处理高维向量时效率较低。在这项工作中，我们提出了一种基于ReRAM的内存处理（PIM）架构用于GNN加速，称为ReGNN。ReGNN由用于加速矩阵向量乘法（MVM）操作的模拟PIM（APIM）模块和用于加速非MVM聚合操作的数字PIM（DPIM）模块组成。为了有效地处理GNN聚合阶段的顶点，我们根据顶点的度数和特征向量的维数，设计了一个顶点调度器和不同的子引擎。此外，我们在子引擎中设计了新的数据映射策略，以充分利用多个多维顶点聚合过程中的数据并行性。实验结果表明，与GPU和基于ReRAM的GNN加速器ReGraphX相比，ReGNN分别将GNN推理速度提高了228倍和8.4倍，同时将能耗降低了305.2倍和10.5倍。
背景与动机
图1 图神经网络计算模型
GNN源于神经网络和图处理，可用于分析和处理非欧几里得图数据。GNN对图结构中的顶点的特征向量进行聚合，并通过将其应用于权值矩阵中来线性地改变聚合结果。这两个阶段分别被称为聚合（aggregation）和组合(combination)。聚合函数通常执行简单的操作，如积累、平均值和最大值。通过多层叠加，可以聚合多跳相邻顶点的特征向量。在组合阶段，将聚合生成的顶点特征应用于神经网络权重矩阵来实现线性变换。同一层的所有顶点特征都使用相同的权重矩阵进行更新，并且权重矩阵在整个推理过程中是固定的。
PIM是一种非冯·诺伊曼架构，可以直接在内存中进行原位计算。它显著地消除了数据的移动，提高了计算的并行性。近年来，使用ReRAM交叉条阵列的PIM架构已经证明了加速以数据为中心的应用程序的潜力，如神经网络和图计算。PIM架构可以执行两种典型的计算范例：模拟计算和数字计算。
图2 ReRAM阵列结构
模拟PIM（APIM）利用基尔霍夫电路定律来加速MVM操作，可以在一个周期内执行阵列级的MVM操作。在进行模拟计算之前，将矩阵映射到表示电导率矩阵（G）的ReRAM阵列中。之后，通过使用数模转换器（DACs），将输入向量转换为模拟域中的电压矢量（V），ReRAM阵列通过计算输出电流I=G×V来执行MVM操作。最后，利用模数转换器（ADC）将输出电流转换为数字信号。虽然APIMs可以显著提高MVM操作的性能和能源效率，但计算精度和应用场景都受到了限制。
数字PIM（DPIM）主要用于执行高并行NOR逻辑操作。由于NOR是基本逻辑操作，任意运算都可以通过一系列NOR实现，因此DPIM可以支持Max、Add、Mul和其他复杂操作。由于DPIM支持行并行化，通过合理的映射也可以实现高并行性，与CMOS电路相比，提高了计算和能源效率。尽管DPIM相对于APIM的效率较低，但它支持更灵活的算术操作。
然而，设计基于ReRAM的GNN加速器仍然存在一些挑战。首先，非MVM操作通常由复杂的外围电路处理，这将导致更高的延迟、更多的能量消耗和大量的面积开销。其次，传统ReRAM阵列在执行MVM操作时，输入的特征向量通过DACs逐位转换为电压向量。顶点的高维特性严重加重了这种序列化操作，并在很大程度上抵消了APIM处理MVM操作的性能提高。最后，图顶点的幂律分布通常会导致不同处理单元之间的负载不平衡。要聚合具有不同度数顶点的特征，聚合引擎的单一执行模式很可能会导致负载不平衡问题。
设计与实现
图3展示了所提出的ReGNN架构。ReGNN由两个处理引擎组成：聚合引擎和组合引擎。前者用于执行基于图结构的遍历和聚合相邻顶点的特征向量，后者用于执行密集和常规的MVM操作。ReGNN还使用控制器Ctrl与引擎通信并建立两个引擎之间子图的执行流水线。不同引擎生成的输出存储在eDRAM缓冲区中，以供进一步处理。
图3 ReGNN架构
聚合引擎旨在减少图形结构的不规则数据访问，并有效地在顶点之间执行聚合操作。为了减少数据映射到交叉阵列的延迟，我们使用缓冲区来临时存储输入数据，以便可以部分重叠数据获取和处理的延迟。由于大多数顶点具有少量相邻顶点，只有少数顶点具有很高度数，如图4所示，我们设计了三个子引擎来对具有不同程度的顶点执行聚合操作：用于低度数顶点的通用子引擎（LDPIM），用于高度数顶点的Max子引擎（HDPIM）和用于高度顶点的Mean/Sum子引擎（APIM）。相应地，我们在聚合引擎中提出了一个顶点调度器，以提高计算并行性，并根据顶点的度和维度将聚合任务分配给不同的子引擎。
图4 顶点聚合操作加速器设计
DPIM可以通过将大多数算术运算转换为NOR逻辑运算。在本文中，我们重点介绍了基于NOR的多个定点操作数之间Max操作。图5显示了LDPIM中两行操作数的Max运算示例。首先，我们对同一行中的两个操作数执行逐位XOR操作（步骤1），每个XOR操作需要6个NOR周期。然后，从最高有效位开始扫描结果，直到找到第一个1（步骤2）。如果数字是XOR结果的第N位，我们检查第一个操作数的第N位是否为1（步骤3）。如果为1，则第一个操作数是较大的操作数，不需要额外操作。否则，此操作数被标记为1（绿色列），并最终应替换为另一个操作数。通过这种方式，我们确保行第一个位置的操作数始终是最大值。在步骤4中，此行中XOR结果的以下位全部设置为0，以避免在以下步骤中进行潜在的比较。对于第二行，我们执行相同的工作以查找较大值（步骤5-8）。最后，如果绿色列中的值为1，则交换两个操作数的位置，最终较大的值都位于每行的第一个位置（步骤9和10）。
图5 LDPIM中的Max操作
图6显示了在HDPIM中使用多个定点数字执行Max聚合操作的过程。首先，我们从最高位开始依次搜索1（步骤1）。一旦找到1，则将不匹配行的数据设置为0（步骤2）。然后，我们继续比较匹配行的下一位，直到只剩下一行操作数或者搜索到最低位（步骤3和步骤4）。我们注意到，HDPIM的阵列结构与LDPIM一致，因此聚合引擎中的DPIM阵列可以重新配置，以在实践中满足不同的资源需求。
图6 HDPIM中的Max操作
我们使用两个经典的GNN模型和4种数据集对ReGNN进行了实验评估，实验结果表明，与GPU和基于ReRAM的GNN加速器ReGraphX相比，ReGNN将GNN推理速度分别提高了228×和8.4×，能耗降低了305.2×和10.5×。
详细内容请参见：
Cong Liu, Haikun Liu, Hai Jin, Xiaofei Liao, Yu Zhang, Zhuohui Duan, Jiahong Xu, Huize Li. "ReGNN: A ReRAM-based Heterogeneous Architecture for General Graph Neural Networks," in Proceedings of the 2022 ACM/IEEE Design Automation Conference (DAC), pp. 469-474. DOI: https://doi.org/10.1145/3489517.3530479
往期 · 回顾
还没有评论，来说两句吧...