点击数: 更新日期: 2023-04-10
中文题目：AmgR: 在ReRAM上利用存算一体加速AMG
论文题目：AmgR: Algebraic Multigrid Accelerated on ReRAM
录用期刊/会议：Design Automation Conference (DAC, CCF-A类会议)
录用/见刊时间：2023年2月24日
作者列表：
1）范明嘉 中国石油大学（北京）信息科学与工程学院 计算机科学与技术系 研21
2）田潇天 中国石油大学（北京）信息科学与工程学院 计算机科学与技术系 研19
3）何银涛 中国科学院计算技术研究所
4）李军贤 中国石油大学（北京）信息科学与工程学院 计算机科学与技术系 研22
5）段懿洳 中国石油大学（北京）信息科学与工程学院 计算机科学与技术系 研21
6）胡潇喆 美国塔夫茨大学
7）王颖 中国科学院计算技术研究所
8）金洲 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术系
9）刘伟峰 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术系
文章简介:
在本文中，我们提出了一种利用电阻随机存取存储器 (ReRAM) 来加速代数多重网格 (Algebraic multigrid, AMG)的存算一体架构AmgR，相比于基于传统冯诺依曼的CPU和GPU架构，AmgR在更低能耗的情况下获得了更高的性能。
摘要:
线性方程组求解是科学计算的一个基本问题，其优化经历了几十年的研究。代数多重网格 (AMG) 是最著名的求解器之一，由于其良好的可扩展性，在高性能计算中被广泛使用。然而，AMG的加速面临着巨大的挑战，目前的加速工作都是基于传统冯·诺依曼这样的存算分离架构实现的，这导致了大量的数据传输开销。在本工作中，我们提出了一种基于电阻随机存取存储器 (ReRAM) 的存算一体架构AmgR，用来加速AMG。然而，在ReRAM上实现AMG加速是非常具有挑战性的，原因如下：(1) AMG中有多种不同类型的计算模式；(2) 存在一些不规则操作，特别是聚集操作，不能直接使用适合于ReRAM阵列的矩阵向量乘法来实现；(3) ReRAM存在写耐久性差的问题，而在加速AMG过程中需要将大量数据写入ReRAM，这将会导致高昂的写成本。为了解决以上这些挑战，我们首先提出了一种可重用架构，可以实现AMG的各个计算模式，被许多计算模式所重用，从而提高资源的利用率；其次，我们为实现聚集操作提出了一个专用的硬件单元；最后，我们提出了一种新的映射策略，在极大程度上减少了数据搬运次数和对ReRAM的写次数。最后，我们将AmgR与CPU平台上的HYPRE和GPU平台上的AmgX进行了比较。实验结果表明，与HYPRE和AmgX相比，AmgR的性能分别平均提高了一个数量级和两个数量级，而能耗则分别平均降低了两个数量级和三个数量级。
背景与动机:
代数多重网格 (AMG) 是科学计算领域里最为重要的线性解法器之一。然而目前AMG加速工作都是基于传统冯·诺依曼这样的存算分离架构实现的，导致在处理器和内存之间的数据移动开销很大。为了突破传统冯·诺依曼架构的限制，快速读取访问数据，本文提出了一个用于AMG加速的基于ReRAM的存算一体架构AmgR。
设计与实现:
AMG整个算法具有一定的复杂性，其分为Setup阶段和Solve阶段，共有十种不同的计算模式（如Algorithm 1 和Algorithm 2所示）。如若想要把AMG中所有计算模式在ReRAM实现，一种解决方案是为每种计算模式设计专门的硬件模块，这个硬件开销是相当巨大的。
为了尽可能减少硬件开销，我们充分利用AMG中计算模式的相似性，设计了一种基于ReRAM的可重用架构AmgR，如图1所示，其包含AGG模块、ASPR模块、AC模块，Control以及Global Buffer这五个组件。
图1:架构图
其次，我们发现AMG中通过聚集操作进行网格粗化部分，如图2所示的过程：根据图2(a)所示的无向图边的权重，每次将前k（聚集大小）个权重较大的边所连接的点聚集成一个粗点。其不能直接使用适合于ReRAM的矩阵向量乘法来实现。为了实现这类不规则操作，我们利用CAM搜索特性设计了一个专门的硬件单元来实现，如图1中的AGG所示。
图2:聚集过程
最后，我们为了减少数据的移动，提高资源的复用，提出了新的映射策略。此映射策略有效利用操作数在AMG整个数据流中使用频率不同的特征，将矩阵A、S、P、R将分别固定在ASPR模块的四个MAC crossbar上，为了进一步减少开销，我们还把D-1压缩存储，并将b和D-1也固定在了MAC crossbar上。如图3(a)和3(b)所示，其分别表示采用映射策略前和采用映射策略后的数据搬运情况。我们可以很明显看出采用映射策略后，数据搬运量大大减少，同时也减少了在ReRAM上的写次数。
图3:映射过程中的数据搬运（数字代表AMG中的十个计算步骤，箭头代表数据搬运）
实验结果及分析:
我们使用NeuroSim和NVSim对AmgR的性能和能耗进行仿真，并与CPU上的HYPRE和GPU上的AmgX进行性能和能耗比较。如图1所示，AmgR相对于AmgX和HYPRE性能分别平均有两个数量级和一个数量级的提升。 如图2所示，AmgR相对于AmgX和HYPRE能耗分别平均降低了三个数量级和两个数量级。
图1：AmgR、HYPRE和AmgX的性能比较
图2：AmgR相对于AmgX的能耗对比（上），AmgR相对于HYPRE的能耗对比（下）
我们又挑选了六个不同规模的矩阵，其相关信息如表1所示。并在AmgR、HYPRE和AmgX上进行性能和能耗评估，其结果分别如图3和图4所示。
表1：六种矩阵信息
图3：在六种矩阵下AmgR、HYPRE和AmgX的性能比较
图4：在六种矩阵下AmgR、HYPRE和AmgX的能耗比较
结论:
在本文中，我们提出了基于ReRAM的加速器AmgR，其可以有效地加速AMG。对于AmgR，我们设计了多个计算单元来实现AMG的所有计算操作模式。针对聚集这类不规则操作，我们提出了专用的硬件单元来实现。而且我们还提出了一种新的映射策略来减少数据搬运和对ReRAM的写次数。实验结果表明，AmgR与CPU上的HYPRE和GPU上的AmgX相比，AmgR的性能分别平均提高了一个和两个数量级，而能耗则平均降低了两个和三个数量级。
通讯作者简介:
金洲，早稻田大学博士、博士后、GCOE研究员，计算机系讲师，硕士生导师，入选北京市科协青年人才托举工程。主要从事芯片设计自动化EDA、并行稀疏线性系统求解器、基于新型非易失存储器的存算一体软硬件协同设计等。主持并参与国家自然科学基金青年项目、重点项目，科技部重点研发微纳电子专项、高性能计算专项青年科学家项目，国家重点实验室开放课题、企业横向课题等十余项。在DAC、TCAD、TODAES、IPDPS、TCAS-II、ASP-DAC、GLSVLSI等重要国际会议和期刊上发表30余篇高水平学术论文。联系方式：jinzhou@cup.edu.cn。