并行规约与扫描原语在ReRAM架构上的性能优化*

金 洲，段懿洳，伊恩鑫，戢昊男，刘伟峰

(中国石油大学(北京) 信息科学与工程学院， 北京 102249)

规约和扫描是并行计算中的两个核心原语，对诸多并行计算的性能有着显著影响。并行规约是并行点积、并行矩阵乘法、计数等并行算法中的一个常见操作[1-2]。并行扫描的应用包括排序(快速排序和基数排序)和合并、图计算(如最小生成树、连通分量、最大流、最大独立集、双连通分量等)，以及计算几何(如凸包、多维二叉树构建、平面最近点对等)[3-12]。此外，规约和扫描还对基本线性代数子程序中稀疏矩阵-向量乘(sparse matrix vector multiplication， SpMV)、稀疏矩阵-矩阵乘(general sparse matrix matrix multiplication， SpGEMM)等矩阵运算的性能具有显著影响[13]，这些矩阵运算在气象预报、大规模电力系统仿真等科学与工程计算中具有广泛的应用。因此，规约与扫描原语的并行加速具有重要的研究价值。

加速规约与扫描原语的一般思路是利用CPU、GPU等多核或众核处理器以并行的方式执行算法，可以带来成倍的性能提升[14]。然而，传统的冯·诺依曼体系结构中计算单元与存储单元之间频繁的数据吞吐会严重影响总体计算性能。与计算本身功耗相比，操作数移动功耗可达10倍之多[15]。同时，为了满足对内存带宽不断增长的需求，片外互连传输速率的增长速度快于每比特能量下降的速度，从而导致更高的峰值功耗[16]。

近来，采用基于忆阻器等新型非易失存储器件的存算一体技术逐渐成为一个新的热点研究内容[11]。由其构成的内存架构最显著的特点是具有原位计算[9]的能力，可从根本上避免数据的移动。其中，应用较为广泛的一种是氧化还原阻性存储器(resistive RAM， ReRAM)。相比其他非易失存储器，如相变存储器(phase-change RAM， PCM)、自旋转移扭矩存储器(spin-transfer torque RAM， STT-RAM)等，ReRAM具有集成密度大、开关速度快、操作功耗低、开启/关闭阻值比高、多值存储、耐久性高，以及与CMOS制备工艺兼容性好等诸多优点，是更具吸引力的方案[11]。

基于ReRAM的存算一体架构可使用结构化的交叉阵列和基本的欧姆定律并行地计算矩阵向量乘法(matrix-vector multiplication， GEMV)，可参见文献[16-18]。ReRAM架构已在机器学习、图计算等依赖GEMV的计算密集型应用中展现了巨大的潜力。Chi等[17]最早设计了基于ReRAM的深度学习加速器PRIME。He等[19]提出了考虑ReRAM状态和功耗之间关系的神经网络加速器SARA。3DICT[20]实现了神经网络训练中的反向传播。在图计算方面，Dai等[21]提出了一种在混合存储多维数据集阵列上进行图形处理的存内处理架构GraphH；Huang等[22]提出了基于三维ReRAM的大规模并行图处理加速器RAGra； Nai等[23]提出了一种图计算的全栈解决方案GraphPIM。然而，如何将规约和扫描原语应用到只适合GEMV运算的ReRAM架构上，仍存在以下多个关键挑战。

1)如何将不依赖GEMV的规约与扫描原语在忆阻器阵列上实现加速，尤其是如何将不同长度的数据映射到固定尺寸的、只支持较小矩阵运算的交叉阵列上。

2)如何将科学计算中所需的较高精度数据映射到只支持2～6 bit的ReRAM单元上，并一步实现矩阵的乘加运算。

3)如何设计电路和架构使其尽可能地匹配加速算法并实现数据重用，减少擦写次数，避免写操作带来额外功耗。

本文面向基于ReRAM的存算一体架构，以矩阵乘法的形式进行规约和扫描算法的加速，将其不同规模问题高效地映射到固定尺寸的忆阻器阵列上，同时展示实现上述算法所需的电路设计与硬件架构，实现软硬件协同设计。并与当前最先进的GPU实现方法进行对比，验证了所提算法的高性能与低功耗。

1 研究背景

1.1 规约和扫描算法

将在这一小节简要介绍规约、扫描以及分段规约与分段扫描四个核心原语，简单回顾其基本并行算法以及当前最先进的GPU加速并行算法。首先，给出如下基本定义。

定义1给定长度为n的输入序列，如x1,x2,x3, …,xn, 规约原语计算并输出结果：

(1)

定义2给定长度为n的输入序列，如x1,x2,x3, …,xn, 扫描原语计算并输出包含n个结果的序列：

(2)

定义3给定输入序列包含k个长度为m的子段，分段规约原语计算并输出包含k个结果的序列：

(3)

定义4给定输入序列包含k个长度为m的子段，分段扫描原语计算并输出包含km个结果的序列：

(4)

规约与扫描的一种常见并行方式是将其拆分为多个可并行的子任务，并对其结果进一步规约或扫描，通过多次迭代得到最终结果。GPU上的规约和扫描大多通过warp级、block级以及grid级三个层次联合实现。一个block包含多个warp，warp级的规约结果在block级再次规约，在grid 级对block级结果进行规约，并形成最终完整的规约结果。warp级的规约和扫描操作通常通过shuffle指令来完成，算法1展示了其计算过程，一个warp中的多个线程通过寄存器来共享数据，而无须同步或共享内存。

算法1 GPU上使用shuffle的规约和扫描算法

1.2 ReRAM

ReRAM是一种新兴的非易失性存储器，具有高密度、快速读取和低漏功率等优点，是极具前途的构建未来存算一体体系结构的非线性元器件[9]。ReRAM可通过改变单元电阻来存储信息，其中一种实现方式是以金属氧化层作为阻变特性材料，其金属-绝缘体-金属结构如图1(a)所示，由顶部电极、底部电极以及夹在电极之间的金属氧化物层组成。通过施加外部激励，ReRAM单元可以实现在高阻态(关闭状态)和低阻态(开启状态)之间切换，这两种状态可分别用于表示逻辑的0和1。其伏安特性曲线如图1(b)所示。

图1 ReRAM物理结构及电子特性Fig.1 ReRAM physical structure and its electrical characteristics

ReRAM的crossbar交叉阵列[15]结构还可以天然地实现乘加运算，通过模拟计算的方式将O(n2)复杂度的GEMV计算变为O(1)复杂度，极易应用到有大量矩阵向量乘计算的神经网络及神经形态芯片中。ReRAM的交叉阵列结构如图2所示，将ReRAM单元连接到同一行的称为字线，连接到同一列的称为位线，电压从字线输入，电流从位线输出。将矩阵中的值编程为各ReRAM单元的电导G，向量以电压的形式输入，连接到相同字线的ReRAM单元共享同一个输入电压Vi，根据欧姆定律和基尔霍夫电流定律(Kirchhoff′s current law， KCL)，可得到流过各ReRAM单元的电流I=V·G，连接到相同位线的ReRAM单元输出的电流之和即为GEMV的一个结果。

图2 使用ReRAM的crossbar交叉阵列实现的乘加运算Fig.2 Implementation of GEMV operation through the ReRAM crossbar

ReRAM的交叉阵列被证明可以有效地加速神经网络计算，其中主要考虑卷积层和全连接层，全连接层的本质为矩阵向量乘，卷积层则可转化为矩阵矩阵乘，使得非常适合在ReRAM上进行计算，如将数值较为稳定的学习参数(卷积层的卷积核和全连接层的权值)映射到计算单元，利用ReRAM天然的并行计算优势提高训练效率[17]。ReRAM也被用于处理图计算问题，通过稀疏矩阵压缩[15]、切片技术或剪枝[24]，可将图计算中的矩阵运算映射到ReRAM阵列中，提高计算效率。总的来说，通过压缩稀疏格式和找到良好的映射方法，ReRAM可以很好地提高神经网络、图计算等应用的效率。

2 并行加速算法

与GPU类似，在基于ReRAM存算一体架构上的并行规约与扫描操作也可以被划分到多个忆阻器阵列上并行计算，并将结果再次分配到多个忆阻器阵列上进行并行规约与扫描，通过多次迭代得到最终结果。因此，忆阻器阵列上的高效规约算法是忆阻器阵列间进一步并行的基础和前提。这里，将重点阐述忆阻器阵列上对不同长度数据进行规约与扫描操作的计算方法，即忆阻器阵列级别的规约与扫描算法，阵列间的操作则与阵列上类似。核心在于将扫描与规约运算转换为矩阵乘法或矩阵乘加的形式，映射到忆阻器阵列上。

2.1 规约

规约操作可较为直观地变为如式(5)所示矩阵向量乘的方式，但忆阻器的阵列是固定且较小的，无法将任意尺寸的规约操作直接映射并实现到忆阻器阵列上。本文将以16×16的忆阻器阵列为例，介绍适用于固定尺寸忆阻器架构的、利用GEMV实现的规约算法。该方法可扩展至任意尺寸的忆阻器阵列。

(5)

首先，考虑较为简单的两种情况。①对包含16个子段(长度均为16)总长为256的输入序列进行分段规约，其计算方式如图3、图4所示，将输入序列以列优先存储的方式映射到忆阻器阵列上，则每个子段可被映射到忆阻器阵列的一列上，利用式(5)矩阵向量乘法的方式，以全1向量作为输入电压，每条位线上的输出电流即为分段规约的结果。②对子段长度为256的输入序列进行规约，并将元素以列优先的方式将其映射至忆阻器阵列上，复用上述情况①的计算过程，将情况①获得的结果再次以列优先存储的方式映射到忆阻器阵列上，与全1向量相乘，通过一次迭代即可获得最终结果，如图5、图6所示，该过程共需完成两次GEMV运算。

图3 Reduction16的计算方式(矩阵形态)Fig.3 Calculation method of reduction16(in matrix form)

图4 Reduction16的计算方式(忆阻器形态)Fig.4 Calculation method of reduction16(in crossbar form)

图5 Reduction256的计算方式(矩阵形态)Fig.5 Calculation method of reduction256(in matrix form)

图6 Reduction256的计算方式(忆阻器形态)Fig.6 Calculation method of reduction256(in crossbar form)

有上述两个基本原语之后，任何子段规约均可以表示为16倍数或256倍数长度。这里将分别考虑这两种情况：

1)一种对子段长度为16倍数的序列进行规约，将其中每16个元素看作一个基本单位块，如图7、图8所示，以16N作为长度间隔，分别取出长度为16的基本单位块，将其以列优先存储的方式写入第一次运算的ReRAM阵列(即放入第一列与第二列的数据之间间隔为16N)，接着取16N中的第二块数据并再次以16N为间隔，依次取出多个块写入下一次运算ReRAM阵列中，并与上一次运算的规约结果向量累加，则可得到每个16N分段前两个块的部分规约结果。以此类推，直至做完为止。即取各子段中前16个元素依次映射为忆阻器阵列上的一列，与全1向量相乘，得到各子段前16个元素的规约结果后，对各子段中第二组16个元素以同样方式依次映射，并将第一次规约的结果映射至忆阻器阵列的第i+1行(i=16)，再次与全1向量相乘，则可以得到各子段前32个元素规约结果。计算16个16N长度的分段规约共需N次迭代，其详细计算过程如算法2所示。这种方式更适合忆阻器阵列较少，单个忆阻器阵列上需计算数据的总长较长的情况。

图7 Reduction16N的计算方式(矩阵形态)Fig.7 Calculation method of reduction16N(in matrix form)

图8 Reduction16N的计算方式(忆阻器形态)Fig.8 Calculation method of reduction16N(in crossbar form)

算法2 Reduction16N的算法

2)另一种是对子段长度为256倍数的输入序列进行规约，对N个长度为256的序列分别调用上述情况②的计算过程，并将每个256序列的规约结果标量累加到下一个256序列上。然而，该方法的缺点是共需2N次乘加运算，每一个256长度的规约都多计算了一次矩阵乘法。如图9、图10与算法3所示，将每一个256长度规约计算的结果映射至下一个256长度运算的忆阻器阵列的第i+1行(i=16)，与全1向量相乘后，前一个256长度规约计算的结果被直接累加在下一个256长度运算结果上，最终对累加后的结果进行一次规约操作即可，该方法进一步优化了计算过程，将运算次数减少为N+1。

对于子段长度在(256m,256(m+1))区间的序列还可以结合上述两种原语进一步优化性能，即利用256倍数原语对于256m长度的数据进行规约，而对剩余序列则利用16倍数原语进一步加速。

图9 Reduction256N的计算方式(矩阵形态)Fig.9 Calculation method of reduction256N(in matrix form)

此外，在此基础上，阵列间还可以进行并行规约，以256N长度的序列为例，将数据切分成N个长度为256的序列，调用情况①则可得到N个256序列中以长度为16划分的分段结果，调用情况②将每个长度为256序列的部分结果写进忆阻器阵列的每一列，给定输入向量1，则可得到N个以256为长度的子段规约结果，将N个结果再调用一次情况②，以此类推，则共需两次或多次迭代(log16256N次迭代)完成所需运算。可将阵列级规约方法和阵列间并行规约方法相结合，对不同规模的输入序列可自由选择多种不同算法进行组合，以达到最优性能。

图10 Reduction256N的计算方式(忆阻器形态)Fig.10 Calculation method of reduction256N(in crossbar form)

算法3 Reduction256N算法

2.2 扫描

忆阻器阵列级的扫描算法如图11、图12和算法4所示，与规约算法不同的是，该方法将输入序列以行优先存储的方式映射至忆阻器阵列。首先将以行优先存储方式形成的矩阵C与数值均为1的上三角矩阵相乘，可得到每行数据的前缀和结果，记为矩阵CU。接着以数值为1的下三角矩阵(对角线为0)与矩阵C相乘，得到矩阵LC，其中第一行为0，第2～n行是C矩阵的前(n-1)行在列上的前缀和结果。最后，将LC矩阵与全1矩阵相乘，则可在每一行的每个位置上均得到该行的规约结果，即为每一行在其之前的所有数据的总和，将得到的结果加上CU矩阵即可得到最终扫描原语的结果。通过两次矩阵乘法与一次矩阵加法共三个步骤，即可完成扫描的计算任务。以16×16的矩阵运算为例，则该运算可得到分段为256的序列前缀和结果，若分段长度为16，则仅需阵列级扫描算法即可完成16个子段长度为16的序列的扫描计算。对于子段为16倍数或256倍数序列的规约与扫描原语的计算思想类似，这里不再赘述。

图11 基于ReRAM架构阵列级扫描算法(矩阵形态)Fig.11 Array level scan algorithm ReRAM-based architecture(in matrix form)

图12 基于ReRAM架构阵列级扫描算法(忆阻器形态)Fig.12 Array level scan algorithm ReRAM-based architecture(in crossbar form)

算法4 分段扫描算法

阵列间的并行扫描方法如图13所示(以迭代一次作为示例)，将输入序列划分到多个忆阻器阵列上，对每个划分利用阵列级扫描原语进行操作，收集各划分序列的最大数(最后一个结果)形成新的较短待扫描序列，迭代上述过程，直至最终扫描序列长度≤256(即1次可完成扫描操作的序列长度)，将扫描结果逐个累加至上一次迭代所扫描序列的各数值上(即将每个位置扫描结果矩阵的值均与上一次迭代相应矩阵进行加法操作)，重复回代加法的操作，直至迭代展开至最原始的序列，则得到整个序列的扫描结果。完整的计算流程如算法5所示。

图13 阵列间的并行扫描算法Fig.13 Bank level parallel scan algorithm

算法5 阵列间并行扫描算法

2.3 忆阻器架构及映射

上述算法涉及多个如R=A×B+C模式的矩阵乘加运算，对于该类型运算可如图14所示，将矩阵B映射到ReRAM交叉阵列的上半部分，其中每两个ReRAM单元表示一个数据，矩阵C以相同方式被映射到ReRAM交叉阵列的下半部分，将A矩阵作为输入向量的上半部分，下半部分以对角为1的矩阵补齐，通过如上操作，可一步实现矩阵的乘加操作。值得注意的是，本文所有的矩阵乘法、加法、乘加运算均可以这种方式映射到ReRAM交叉阵列上一步实现，即只需控制不同的输入向量即可，如纯粹的矩阵乘法将C矩阵或C矩阵对应的输入向量设为0即可。

图14 矩阵到ReRAM阵列的映射Fig.14 Mapping matrix to ReRAM crossbar

此外，为满足科学计算等应用中对规约与扫描原语较高精度的需求，可将数据通过比特切片的方式映射到多个忆阻器阵列上，在单个交叉阵列上则利用两个相邻单元来存储相同数据(如16×16的矩阵可被映射到16×32的忆阻器阵列上)，并通过移位与加法实现完整的运算得到最终结果。以32 bit精度的数据为例，该数据切片方式与上述映射方式相结合，则16×16矩阵乘加运算可在8个ReRAM阵列上一步实现(单个ReRAM单元存储2 bit)。

图15展示了基于上述电路设计的加速规约与扫描原语的存算一体系统架构，与上文所述的计算流程、映射方法以及数据切片相结合，达到软硬件协同设计的目标。该架构包含多个bank，每个bank包含多个计算单元，每个计算单元包含多个ReRAM阵列，此外，还包含控制单元、输入输出buffer、数据buffer和互联，以及数字模拟转换器(digital-to-analog converter, DAC)、模拟数字转换器(analog-to-digital converter, ADC)外围电路与移加器等多个组成部分。单个ReRAM阵列可选择从字线或位线输入，多个ReRAM阵列之间可并行地进行运算。

图15 ReRAM加速器的架构Fig.15 Architecture of ReRAM accelerator

在扫描原语中，步骤②和步骤③(见图11)两步中涉及对相同矩阵C的操作，可将C矩阵在ReRAM阵列上复用，而无须进行两次较为耗时的ReRAM写操作，其对应的电路设计如图15所示，通过片选决定输入与输出的端口。将C矩阵编程写入ReRAM阵列，步骤②需对矩阵C的行进行点积操作，而步骤③需对C矩阵的列进行点积操作。在步骤②中将U矩阵中的列向量以电压的形式从位线输入，在字线收集电流即为计算结果的一列；在步骤③中，将L矩阵的行向量以电压的方式从字线输入，在位线获得输出结果的一行。通过该方式无须多次擦写即可实现对C矩阵的行或列有选择地进行点积。该方式显著增加数据的复用，减少写操作的次数，提高性能减少功耗。

3 实验结果与分析

3.1 实验环境

本文将所提方法实现在了基于ReRAM的忆阻器阵列上，利用HSPICE仿真电路行为，NvSim仿真忆阻器阵列架构的延迟与功耗，以及高级语言C++模拟了规约与扫描原语的性能与功耗。如表1所示，本文中的忆阻器架构包含128个bank，每个bank包含128个计算单元，每个计算单元包含64个ReRAM阵列，ReRAM阵列尺寸为32×32，每个ReRAM单元可存储2 bit，DAC精度为2 bit。ReRAM的读延迟为1.332 ns，写延迟为20.362 ns，每个ReRAM阵列的功耗为15.153 mW。此外，本文还对比了十核CPU和GPU上的规约与扫描算法，在Inter Core i7和GeForce RTX 2080硬件环境下，对thrust库[25]进行了性能测试。输入数据为32位int型。忆阻器架构上的并行算法可根据输入序列长度在文中展示的多个优化算法间进行调优，即将多大长度的规约与扫描任务分配到多少忆阻器阵列上，如何划分单个忆阻器阵列上需处理的子段长度，如何选择合适的忆阻器阵列级的算法等，均可根据不同情况进行选择，这里展示不同输入参数下观测到的最佳性能。

表1 ReRAM架构配置

3.2 算法性能分析

本文将规约和扫描算法分别在ReRAM加速架构和GPU、CPU上进行性能对比，共分为两组对比实验：第一组对比总长变化的规约和扫描算法；第二组对比总长不变情况下，子段长度变化的分段规约和扫描算法。通过两组对比实验，可以看到本文中所提出的算法在ReRAM加速架构上所获得的良好加速效果。

理论上，对256长度的数据在GPU上实现warp级规约，基于shuffle指令的操作通常需要进行8次32个元素规约的迭代，共需要256个时钟周期，因为每个 shuffle 指令和加法需要4个周期，而在ReRAM存算一体架构上则只需要2个时钟周期。此外，基于ReRAM的存算一体架构单次时钟周期的时间与功耗也较低。

如图16和表2所示，对于总长改变的扫描原语，CPU、GPU和ReRAM架构的性能都随着数据段的增长而缓慢增长，而ReRAM架构在数据段相同的情况下，最高比CPU加速75 302.82倍，比GPU加速906.66倍， CPU平均加速25 075.76倍，GPU平均加速302.49倍(图中横坐标为取log2对数处理的数据总长，纵坐标为取log10对数的每秒通量数据)。同样地，如图17和表3所示，对于总长改变的规约算法，ReRAM架构最高比CPU加速81 258.97倍，比GPU加速454.81倍，CPU平均加速30 090.39倍，GPU平均加速152.38倍。

图16 总长可变的扫描算法在CPU、GPU和ReRAM架构的性能对比Fig.16 Performance comparison of scan algorithm with variable total length on CPU、GPU and ReRAM architectures

表2 扫描算法在GPU和ReRAM架构上性能对比

图17 总长可变的规约算法在CPU、GPU和ReRAM架构的性能对比Fig.17 Performance comparison of reduction algorithm with variable total length on CPU、GPU and ReRAM architectures

表3 规约算法在GPU和ReRAM架构上性能对比

对于总长不变，即总长度为229的数据段，不同分段时规约和扫描算法的性能，ReRAM加速器都比传统GPU快3～5个数量级，尤其在小分段的情况下，ReRAM架构可以达到4～5个数量级的加速效果。图18为总长不变，分段size为215到228扫描算法的性能比较，相比GPU，最高加速比为92 342.39倍，平均性能加速比为13 261.39倍。相比CPU，最高加速比为34 759.34倍,平均加速比为15 925.73倍。图19为总长不变，分段size为215到228规约算法性能比较，相比GPU最高加速比为367 733.57倍，平均性能加速比为55 680.80倍。相比CPU，最高加速比为372 421.71倍，平均性能加速比为173 853.25倍。综上，ReRAM架构展现了明显的加速优势，尤其是对于分段规模较小的问题可达到较大的性能提升效果，这类规模较小的分段规约与扫描原语在数值计算、神经网络中具有极为广泛的应用场景。此外，相比GPU，ReRAM加速架构上的功耗减少了79%。

图18 总长不变、分段长变化的扫描算法在CPU、GPU和ReRAM架构的性能对比Fig.18 Performance comparison of scan algorithm with constant total length and variable segment length on CPU、GPU and ReRAM architectures

图19 总长不变、分段长变化的规约算法在CPU、GPU和ReRAM架构的性能对比Fig.19 Performance comparison of reduction algorithm with constant total length and variable segment length on CPU、GPU and ReRAM architectures

本文针对不同规模的输入序列均给出了较为适用的方法。对于不分段的规约与扫描来说，尽可能填满所有ReRAM阵列并进行迭代统筹的方式最为高效，其所需时钟周期是16为底的对数函数(16为单次可运算的矩阵阶数)。当分段规模大于等于256时，分段尺寸和交叉阵列规模也是影响计算结果的因素。以规约为例，假设对数据总长为2x的序列做分段规约，分段长度为2k，ReRAM阵列共M个，字段长度为16倍数的规约原语需要计算(2x-k-4%M+1)×2k-4次时钟周期，而字段长度为256倍数的规约原语则需计算(2x-k%M+1)×(2k-8+1)次时钟周期。根据所给定字段的长度和个数，可利用公式快速定位最优算法。对于分段尺寸较小的情况，例如子段长为32、64等，采用字段长度为16倍数的规约原语会获得较好的性能，而对于较大的分段规模，如512、1 024等，则是利用256倍数的计算方式较为高效。此外，还可根据情况对文中的不同算法进行组合。

4 结论

规约与扫描是并行计算中的核心原语，对科学计算、机器学习等诸多应用均具有显著的性能影响。本文面向忆阻器阵列的存算一体架构，首次将规约与扫描以矩阵向量乘的形式实现并映射到忆阻器阵列上，提出将任意长度的输入序列映射到固定尺寸的忆阻器阵列上的多种高效算法，以及与之相适应的电路设计与存算一体架构，尽可能地实现数据重用，避免写操作，实现了软硬件协同设计。此外，还对不同尺寸的输入序列选择何种算法可达到最优性能进行了仿真与分析。与GPU上的实现相比，所提算法实现了多个数量级的性能提高，对于总长不变的分段规约与扫描，性能最高可加速5个数量级；总长改变的情况下，规约最高可加速454.81倍，平均加速可达152.38倍，扫描最高可加速906.66倍，平均加速302.49倍，同时降低了79%的功耗。