基于DIMM间广播技术的通信优化方法
本文介绍来自清华大学发表于2021ISCA的论文ABC-DIMM，文章提出了基于DIMM间广播技术的通信优化方法。
DRAM基础：如图1a所示，内存系统由独立的通道组成。在每个通道中，DIMM通过数据总线和命令/地址总线连接到主机CPU内存控制器。每个DIMM进一步组织为Rank和Bank的层次结构，每个Bank由多个Row和一个Row Buffer组成。当主机CPU想要访问Bank中某一行的数据时，它通过C/A总线向Bank发送一个具有行地址的激活（ACT）命令，通知它将该行中的所有数据加载到Row Buffer。随后，它发送一个读取（RD）或写入（WR）命令，该命令具有该行中请求数据的偏移地址，以启动数据访问。当CPU不再需要访问缓冲区中的数据或希望访问另一行时，它必须用预充电（PRE）命令通知Bank，在进行后续操作之前，将缓冲区内的数据移回其所属行。内存操作所需的时间以及特定条件下操作之间的时间是明确定义的，并且在主机内存控制器发出DDR命令时必须严格遵守。内存控制器通常设计有一个复杂的有限状态机来记录系统状态，并计算出待执行命令要遵守的时序约束。
NMP基础：随着通道中Rank数量的增加，由于负载电容的增长，通过总线的数据传输变得更加困难。因此，缓冲芯片被设计并放置在DIMM上，以获得更好的信号完整性。这为高效的近内存处理提供了机会。如图1b所示，通过将处理器与缓冲芯片集成，并使每个通道中的多个LRDIMM并行工作，能够获得比主存储器大得多的总带宽。不过这不可避免地会引入并行编程问题，如通信、任务划分和调度。Chameleon是基于DIMM的NMP的先驱工作，其继承了MapReduce框架，为NMP风格的并行编程提供指导。如图2所示，Chameleon MapReduce框架将执行流程划分为NMP阶段和CPU处理阶段。一开始，CPU在DIMM之间分割输入数据，然后在NMP阶段计算出中间结果。在CPU处理阶段，CPU从每个DIMM收集中间结果，并将其Reduce到最终输出。
带宽可扩展性：内存总线本质上是一种时分复用通信介质。通过点对点通信，CPU一次只能向一个DIMM传输数据或从一个DIMM中传输数据。假设单个内存通道中有n个DIMM，并且每个DIMM具有相等的并发通信需求。当DIMM拥有通道总线时，它会占用全部内存通道带宽。然而，等待该占用花费实际通信时间的（n-1）倍，导致每个DIMM的带宽仅为全通道带宽的1/n，如图3所示。另外，由于数据首先从源DIMM加载到CPU缓存，然后写入目标DIMM，并通过内存总线传输两次，因此每个DIMM带宽进一步减半。
广播的物理可实现性：在内存总线上物理实现DIMM间广播非常简单。当DIMM/CPU通过总线传输数据时，它会物理地改变整个总线的电压电平。为此，它必须为总线上每个DIMM的端接电容器充电，即使它只想与其中一个DIMM通信。当充电过程完成时，每个DIMM都会在其本地终端看到传输的数据。在目前支持的点对点通信中，广播现象已经在物理上存在，实现DIMM间广播只是一个利用现有物理机制的想法。不过当前系统中的信号完整性是针对点对点通信而不是广播进行优化的。使用相同的参数设置可能不是最适合广播实现的。幸运的是，目前的DDR标准已经提供了一个非常通用的信号完整性优化解决方案，包括动态片上终端（ODT）机制和校准机制。前者允许DIMM根据预先配置的一组参数动态改变不同DDR命令的端接阻抗，以实现令人满意的信号完整性。后者在系统启动期间校准或训练这些参数，以适应不同系统环境的需要。
基于DIMM的NMP中的通信严重阻碍了许多数据密集型应用程序。本文使用PageRank算法作为一个示例。
PageRank算法：对于像PageRank这样的图应用，所涉及的矩阵和向量通常是它们的邻接矩阵和顶点值向量的排列。邻接矩阵中的（i，j）处的非零表示从源顶点vi到目的顶点vj的边。对于加权图，非零元素的值对应于边的权重。计算过程是迭代的：通过在每次迭代中进行广义矩阵向量乘法来计算新的秩值。图4显示了该过程的一个迭代。在迭代中，首先将每个顶点的旧秩值乘以顶点度数的倒数，并用作广义SpMV的输入向量元素。Process运算符根据相邻矩阵选择输入向量元素，Reduce运算符定义为正常加法。
Chameleon MapReduce的实现：如图5所示，矩阵按列进行切片，并预先分布在每个DIMM中。对于每次迭代，CPU首先将旧的秩值向量拆分到每个DIMM。然后，每个DIMM上的计算单元执行部分广义SpMV，并计算出输出向量的中间结果。最后，CPU从每个DIMM收集中间结果，并通过将它们相加来导出新的秩值向量。显然，这种实现不能利用广播，因为没有传输相同的数据。
广播过程实现：如图6所示，矩阵按行进行切片，并预先分布在每个DIMM中。在每次迭代的开始，每个DIMM都拥有旧秩值向量的唯一部分。为了初始化迭代，他们首先通过CPU将矢量部分广播给每一个其他DIMM，这样每个DIMM在通信阶段后都拥有旧矢量的完整版本。然后，他们能够用手中的完整旧向量和部分矩阵计算出新秩向量的相应部分。显然，广播占据了通信阶段的主导地位。这个实现的另一个有趣的特性是，所有的计算工作负载都被卸载到DIMM，而CPU只负责通信。
图7显示了在单通道配置下PageRank的性能结果。从图中可以看出，Chameleon MapReduce方案的可扩展性较低。当#DIMM低于4时，加速比缓慢增长到1.87倍，然后开始下降。图8显示了CPU处理阶段的CPU处理时间比和带宽利用率。CPU处理时间严重制约了整体性能。带宽利用率接近80%。CPU处理瓶颈本质上是CPU-DIMM的通信瓶颈。
图7和图9显示了DIMM间的性能结果和通信时间比。在不支持硬件DIMM间广播的情况下，与Chameleon MapReduce类似，通信瓶颈影响了整体性能。有了硬件间DIMM广播支持，通信成本将大大降低。图9中可以看到通信瓶颈已经消除，产生了图7所示的几乎线性的可扩展性。
MapReduce通过分割输入数据来分配任务，BroadcastProcess通过分割输出来创建任务。图10总结了BroadcastProcess框架的执行流程，该框架分为并行NMP计算阶段和广播通信阶段。当CPU检测到所有DIMM都已完成上一个DIMM的工作并达到同步屏障时，开始新的迭代。在广播阶段，部分结果从每个DIMM广播到另一个DIMM，这样每个DIMM都可以获得上一次迭代结果的完整副本。广播完成后，NMP阶段开始，每个DIMM使用本地数据计算新的结果。
通道内广播机构由广播写入和读取广播组成，其数据流如图11(a)和11(b)所示。广播写入是一种直接的机制。与传统的DDR写入相对应，它将数据从CPU MC写入通道中的每个相关Rank，将数据存储在所有Rank的相同位置。其设计不是为多个Rank中的不同地址发布大量命令，这会消耗大量的C/A带宽并严重降低广播性能，而是为每个广播只发布一个命令，以便充分利用广播带宽。广播写入本质上是CPU-DIMM广播机制，而不是DIMM间广播。在只进行广播写入的情况下，CPU必须在广播写入数据之前将数据从源DIMM加载到其缓存，从而导致广播带宽减半。为了避免这种开销，设计了读取广播。读取广播对应于传统的DDR读取。但它实际上是通过读取和同时进行广播写作来实现的。根据来自CPU的读取广播请求，源DIMM将数据移动到总线，其他DIMM将此请求视为写入命令，并同时将数据从总线存储到其本地Rank。
如图12所示，当数据块需要在多通道系统中广播时，CPU可以首先在本地通道中读取广播块并将其加载到缓存中，最后在每隔一个通道中逐个广播写入缓存块。为了在多通道配置下充分挖掘广播过程框架的潜力，需要对通信阶段进行优化的多核实现。如图12(b)所示，数据被分割成块，每个核心以循环方式向每个通道广播一个数据块。
图13展示了基于上述内部DIMM广播机制的详细硬件架构实现。
广播命令及其编码：ABC-DIMM为广播机制引入了四个新的内存命令：ACTB、PREB、WRB和RDB。WRB对应于广播写入机制，而RDB对应于读取广播机制。然而，仅仅用这两个命令来实现高性能广播是不够的，还需要分别对应于PREB和ACTB的PRE和ACT命令的广播版本。引入新命令的一个关键问题是如何用DDR4的当前C/A信号对其进行编码。本文建议将芯片ID位（图14（a）中称为C）用于新命令。这3位用于指定堆叠DRAM器件的特定层，理论上其高度可以为2、4或。然而，目前很少生产8层设备，这意味着对于大多数系统，可以安全地采用图14（b）所示的设计。因此，最高芯片ID位指示ABC-DIMM中的广播命令。
启用广播的DIMM缓冲芯片：DIMM缓冲芯片在实现新命令的功能方面发挥着关键作用。如图13（b）所示，当广播命令到达缓冲芯片时，它们首先由C/A转换器转换为常规DDR命令，然后发送到DRAM设备。如图13（c）所示，WRB、PREB和ACTB的翻译是直接的。当特定等级的C/A转换器检测到WRB命令时，它只需将最高芯片ID设置为0，并将相应的CS信号设置为1，即可将命令转换为常规WR。RDB的翻译要复杂得多。根据读取广播机制，RDB从特定Rank中读取数据，并将数据广播给所有其他Rank以及主机MC。对于数据的源Rank，RDB应充当常规RD，如图13（c）所示。对于其他存储数据的Rank，RDB应该充当WR。
启用广播的主机MC：主机MC负责将广播机制暴露给CPU并保持适当的DDR时序。CPU通过使用物理地址的最高2位作为广播标志来检测广播命令。如图13（d）所示，如果同时设置了最高2位，则地址映射单元将传入的写/读事务识别为广播写/读广播事务，并以NMP友好的方式映射地址。如图13（e）所示，为了维持广播命令的适当DDR时序，FSM和调度器的架构也需要修改。添加了一个广播队列以及相应的调度器。在这种设计中，队列将挂起的事务存储到每个列；调度器将事务解码为特定的DDR命令并利用仲裁器考虑的tRTRS来处理时序约束。
NMP的控制流程：通过上述机制，我们能够实现广播过程框架的整个控制流程。一开始，主机CPU使用新的广播命令广播数据，然后通知DIMM上的计算单元进入NMP阶段。随后，CPU通过轮询每个计算单元或由这些单元触发的中断来检测NMP阶段的完成。然后，它从每个DIMM收集数据，检查每个计算单元的状态并决定是否继续。在ABC-DIMM中，我们使用SIMD单元作为计算核心，该单元经过优化，能够有效利用DIMM上的本地内存带宽。
本文根据3个基线评估ABC-DIMM，即16核CPU基线、Chameloen MapReduce风格的NMP基线(chameleon-mr)和类似广播过程风格的MCN NMP基线（MCN-bc）。
表I总结了CPU基线系统和NMP系统的配置。我们对ABC-DIMM和NMP基线采用了相同的配置，只是ABC-DIMM启用了广播，而chameleon-mr和mcn-bc分别具有CPU-DIMM和DIMM点对点通信功能。除了广播机制之外，NMP基线和ABC-DIMM之间的主要区别在于它们的编程框架。
Chameleon-mr 采 用 框 架 ChameleonMapReduce，而mcn-bc和ABC-DIMM使用广播过程框架。本文将Ramulator与模拟器zsim集成，以评估NMP系统的CPU基线和主机CPU的性能。为了评估ABC-DIMM的主机CPU，其修改了Ramulator，并集成其提出的广播机制以及相应的时序约束。
我们评估了四种算法进行比较。PageRank（PR）之前已经讨论过了。SpMV计算稀疏矩阵和密集向量的乘积。单源最短路径（SSSP）搜索特定源顶点和其他顶点之间的最短路径。平均青少年追随者（A T）计算每个用户的青少年关注量和特定年龄以上用户的平均值。表II列出了我们使用的数据集。它们是来自不同来源的典型数据集。其中，LJ和PK是从社交网络中获得的；WK和EDU是网页链接数据集；NLR是从数值分析应用程序中获得的。
图15显示了ABC-DIMM和NMP基线在具有4通道内存系统的16核CPU上的加速，用于评估的基准。显示了三种体系结构在1通道-1-DIMM和4通道-32-DIMM配置下的性能结果。前一种配置涉及最少的通信，并揭示了单个DIMM的计算能力。后者涉及最大限度的资源，并显示了被评估的系统如何很好地挖掘系统潜力。chameleon-mr和mcn-bc在4通道配置下的扩展能力较差，并且在最大数量的DIMM下工作效果不佳。
图16显示了32-DIMM配置下评估的体系结构和基准测试的通信计算比率。通信计算比率被定义为NMP处理时间和通信时间之间的比率，其包括ABC-DIMM和mcn-bc的广播时间、chameleon-mr的CPU处理时间以及所有架构的初始化时间。这个数字有助于我们初步了解性能变化的根源。首先，ABC-DIMM在很大程度上优于chameleon-mr和mcn-bc。在4通道-32-DIMM配置下，ABC-DIMM在两个基线上的相对性能分别为4.87×和7.03×。其次，DIMM间广播是ABC-DIMM高性能的关键。从图15中，我们可以看到chameleon-mr、mcn-bc和ABC-DIMM在1通道-1-DIMM配置下实现了几乎相同的性能。这在一定程度上表明，DIMM上的本地计算能力和处理任务并不是三种体系结构性能差异的关键因素。第三，应用程序和数据集的特性对性能有明显的影响。具体来说，包括基线和ABC-DIMM在内的NMP系统在SSSP上表现最好。