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

论文题目：并行规约与扫描原语在ReRAM架构上的性能优化

录用期刊：国防科技大学学报（EI中文期刊）

作者列表：

1）金洲 中国石油大学（北京）信息科学与工程学院 计算机系

2）段懿洳 中国石油大学（北京）信息科学与工程学院 计算机系 研21

3）伊恩鑫 中国石油大学（北京）信息科学与工程学院 计算机系 研21

4）戢昊男 中国石油大学（北京）信息科学与工程学院 计算机系 研20

5）刘伟峰 中国石油大学（北京）信息科学与工程学院 计算机系

背景与动机:

基于新型非易失存储器件ReRAM的crossbar阵列可以天然的实现乘加运算，通过模拟计算的方式将O（n2）复杂度的GEMV计算变为O（1）复杂度，极易应用到有大量矩阵向量乘计算的神经网络及神经形态芯片中，突破冯诺依曼体系结构实现存算一体新架构。然而，许多科学计算，例如规约和扫描并不直接依赖于GEMV运算，为了把不同长度的数据映射到固定尺寸的、只支持较小矩阵运算的交叉阵列上进行计算，我们设计了规约与扫描并行加速ReRAM架构，实现了软硬件协同设计，降低功耗并提高了性能。

设计与实现:

规约和扫描是并行计算中的两个核心原语，对诸多并行计算的性能有着显著影响，加速其算法至关重要。在本文中，主要实现了规约、扫描、分段规约与分段扫描四个核心原语的加速。重点阐述了忆阻器阵列上对不同长度数据进行规约与扫描操作的计算方法。其核心在于将扫描与规约运算转换为矩阵乘法或矩阵乘加的形式，映射到忆阻器阵列上。

本文以16*16规模的ReRAM阵列为例，将规约操作分为reduction16、reduction256、reduction16N和reduction256N四种映射方式。在reduction16中，通过将输入序列以列优先存储的方式映射到忆阻器阵列上，每个子段映射到忆阻器阵列的每一列，利用忆阻器阵列计算矩阵向量乘法，以全1向量作为输入电压，得到每条位线上的输出电流即为分段规约的结果。通过这种方式，将不规则的规约运算转换为规则的GEMM运算进行实现。其余三种映射方式在基于规约16的基础上做了进一步扩展和迭代。

扫描算法根据所处理的数据长度，分为阵列级操作和阵列间操作。通过行优先存储方式形成矩阵C，将其与数值均为1的上三角矩阵相乘，得到每行数据的前缀和结果，记为矩阵CU。接着以数值为1的下三角矩阵（对角线为0）与矩阵C相乘，得到矩阵LC。最后，将LC矩阵与全1矩阵相乘将得到的结果加上CU矩阵即可得到最终扫描原语的结果。通过三次矩阵运算，将不规则的阵列级操作转换为规则的GEMM运算。其阵列间操作与其类似。

在与上文所述的计算流程、映射方法相结合后，我们设计了加速规约与扫描原语的存算一体系统架构，达到了软硬件协同设计的目标。

设计与实现:

本工作将所提方法实现在了基于ReRAM的忆阻器阵列上，利用NvSim仿真忆阻器阵列架构的延迟与功耗，利用高级语言C++模拟了规约与扫描原语的性能与功耗。对比十核CPU和GPU上的规约与扫描算法，在Inter Core i7和GeForce RTX 2080硬件环境下，对thrust库进行了性能测试。数据图1为扫描算法在三种架构上的性能对比，数据图2为规约算法在三种架构上的性能对比，数据图3为分段扫描算法在三种架构上的性能对比，数据图4分段为规约算法在三种架构上的性能对比，如图，ReRAM架构相比于GPU，所提规约与扫描原语可实现高达两个（平均两个）数量级的加速。分段规约与扫描最大可达到五个（平均四个）数量级的加速。

作者简介:

早稻田大学博士、博士后、GCOE研究员，计算机系讲师，硕士生导师。主要从事芯片设计自动化EDA、并行稀疏线性系统求解器、基于新型非易失存储器的存算一体软硬件协同设计等。在 DAC、TODAES、IPDPS、ASP-DAC、GLSVLSI 等重要国际会议和期刊上发表30 余篇高水平学术论文。联系方式：jinzhou@cup.edu.cn。