写在前面

本篇是cache压缩系列论文的第六篇

本论文原标题是 CompEx++: Compression-Expansion Coding for Energy, Latency, and Lifetime Improvements in MLC/TLC NVMs
作者是Poovaiah M. Palangappa and Kartik Mohanram Department of Electrical and Computer Engineering, University of Pittsburgh, PA

背景知识

PCM和RRAM等多级/三级细胞非挥发性物质（MLC/TLC-NVMs）因其高刷新能力和低标度潜力而成为当前研究和开发的热点。MLC/TLC-NVMs除了具有非易失性（低刷新功率）和可扩展性等优点外，还具有高数据密度和记忆容量，但其生存能力有限，主要原因是编程能量高、延迟时间长以及NVM细胞的耐久性差；这些主要归因于致畸程序和验证程序编程的NVM细胞的必要性。

MLC/TLC-NVMs与单级单元NVMs（SLC-NVMs）相比具有更高的数据密度，因为它们可以存储1个以上的逻辑数据位。虽然MLC/TLC-NVMs通过封装多个逻辑位/单元提供更高的容量，但与SLC-NVMs相比，每个单元编程的能量和延迟都很高。

上图显示了三种LC的能量消耗和延迟情况

MLC/TLC-NVM技术（如PCM和RRAM）作为DRAM的替代候选技术，受到其高刷新能力和低缩放潜力的限制，是当前研究和开发的热点。然而，大多数MLC/TLC-NVMs的每个单元都有较高的写入能量和延迟，有限的生存期[1]和不对称的读/写延迟。在本节中，我们将讨论用于编程MLC/TLC NVM单元的过程及其相关限制。

MLC/TLC-NVM程序和验证（P&V）：MLC/TLC-NVM由于工艺变化、材料成分变化和电阻漂移而表现出不确定性行为。这种非确定性增加了使用电流或电压的单个精确脉冲将MLC/TLC NVM编程到正确电阻范围的复杂性。
因此，在实际应用中，MLC/TLC-NVMs采用迭代P&V程序编程，以使电池的电阻达到要求的范围。
P&V使用set to reset（STR）和reset to set（RTS）的组合。在STR（RTS）中，通过施加小（高）量级电流的长（短）脉冲，电池首先进入全套（复位）状态。然后，施加多个小持续时间重置（SET）脉冲，直到电池电阻达到所需范围。然而，由于TLC-NVM有8种不同的电阻状态，仅使用STR或RTS会导致高写入延迟。
因此，TLC-NVMs使用STR和RTS的组合进行编程，这取决于目标状态接近于如图2所示的完全设置/复位状态。因此，MLC/TLC-NVM的写入能量和延迟可以根据细胞被编程到的最终状态而变化。例如，图2示出了将TLC-RRAM编程到不同状态的平均能量和延迟。状态0和状态7要求最低的能量和延迟，因为它们可以使用单个P&V迭代进行编程，而状态3和状态4要求最大的能量和延迟，因为它们要求将最多的P&V迭代次数带入所需的电阻范围。

P&V对能量和潜伏期的影响：迭代P&V对MLC/TLC-NVMs的能量和潜伏期有负面影响。

1. 首先，由于迭代P&V方法，向MLC/TLC-NVMs写入需要比其SLC计数器部分更高的电流和延迟。
2. 其次，为了防止模块过载和防止过热，NVM模块被限制一次写入有限数量的数据，这增加了写入延迟，影响了性能。
3. 第三，由于单次写访问可能潜在地要求MLC/tlc在一个字中处于不同的目标状态，因此写操作的延迟由最长的延迟单元写决定，从而为单个写操作造成瓶颈。最后，MLC/TLC-NVMs的单次写入涉及多个P&V周期，与SLC-NVM相比，SLC-NVM的生命周期为108-10次写入

已有方案和架构思考

方案包括编码、编写调度、使用地址转换进行数据迁移和架构改进

In other words, we believe that the ability to integrate a dense high capacity MLC/TLC technology for the memory while dynamically operating that memory in the SLC/MLC mode (fully or partially, as developed in the theory of ex-pansion codes in this section) has far-reaching implications for simultaneously improving NVM energy, latency, den-sity/capacity, and lifetime (the lifetime improvement is in-direct, due to a reduction in the P&V effort needed for mem-ory operation).

换言之，我们认为，在SLC/MLC模式下动态操作存储器（完全或部分，如本节扩展码理论所发展）的同时，为存储器集成密集的高容量MLC/TLC技术的能力，对于同时提高NVM能量、延迟，密度/容量和寿命（寿命的改善是直接的，因为减少了内存操作所需的P&V工作）。

CompEX编码方案

核心思想

本文提出了压缩扩展（CompEx）编码，这是一种低开销的方案，它将统计压缩与扩展编码协同集成，以实现MLC/TLC-NVMs中能量和延迟的同时改进。CompEx编码的核心思想是有选择地将扩展码，即仅使用MLC/TLC单元的低能状态对数据进行编码的线性分组码应用于压缩数据，从而确保以扩展编码形式产生的数据不会超过原始数据宽度。
一句话概括，就是先用个方法把数据压缩，然后以更节约能量的方式存储起来（该过程会把压缩的数据扩展）。整个过程中保持扩展后数据没增长

CompEx编码对压缩技术的选择

1. 频繁模式压缩（FPC）：
   详情参考我的这篇博客 FPC压缩
   FPC是一种利用程序数据统计信息成功压缩大量数据的压缩方案。FPC最初被提出用于二级缓存中的32位数据字压缩，以增加其内存容量。最近，FPC被扩展以减少NVMs中的位写入。在这项工作中，我们使用表1中的模式选项卡将FPC扩展到64位字。FPC维护一个包含七个最频繁的数据模式的表，与之对应的是传入的数据。当输入的数据与其中一个频繁模式匹配时，将其压缩并与对应于由表1的列1表示的模式的3位pre fix一起存储。1位标记用于指示写入的数据是否是其压缩/未压缩的形式。在读取访问期间，标记位和pre fix用于将数据解压缩为完整的单词。表1的第3、4和5列显示了每个数据模式的示例，以及它们的压缩形式和压缩数据大小。表1的第6列表示每个模式可以压缩的数据值范围，第7列表示SPEC CPU2006基准套件基于跟踪的模拟中每个模式压缩的数据字的百分比（FPC累计压缩约60%的写访问）。
   

2. BDI（BΔI）：
   详情参考我的这篇博客BDI论文解读
   
   BDI最初提出用于片上高速缓存数据压缩[39]，通过使用“基”（B）和“Delta”（Δ）存储压缩后的数据，相对于BΔI的一系列偏移提出高速缓存线C={V0，V1，…Vn−1}可以压缩并写入X={B，Δ0，Δ1，…Δn−1}2。以及一个4位标记，其中B=V0（定义）、Δi=Vi-B、n=sizeof（缓存线）/k和k=sizeof（Δ）。缓存线中存储的数据通常是规则的，动态范围有限。数据的规律性是由于常用数组数据结构来存储程序数据，而存储数据的动态范围有限则是由于计算的性质。与FPC类似，BΔI维护压缩模式表。BΔI利用数据的规律性及其有限范围，使用64字节模式压缩缓存线。
   最后一列表示SPEC CPU2006[40]基准套件的基于跟踪的模拟中，每种模式压缩的数据字（BΔI cumu相对压缩约46%的写访问）的使用年限百分比。给定一个缓存线，它与表2的每一行（模式）匹配。如果缓存线数据与模式匹配，则压缩数据连同pre fix一起存储在数据存储器中；标记位被设置为指示存储的数据是压缩格式的。相反，如果数据未被压缩，则它以未压缩格式存储；标记位被重置以记录此信息。

由于FPC和BDI的低开销和高压缩比，这项工作的动机是将其中一种压缩技术与扩展编码结合起来，在不增加任何存储开销的情况下降低能量和延迟的整体解决方案。

expand coding（扩展编码）

用于编程MLC/TLC-NVMs的迭代P&V过程导致与终端状态相比，中央MLC/TLC状态需要更多的能量和延迟。这促使数据编码只使用低能量状态，避免高能量状态，以减少整体能量和延迟。这项工作使用扩展编码，它只使用这些低能量状态对数据进行编码。本小节的其余部分提供了扩展编码的正式定义，并举例说明了扩展编码。

编码的数学定义

符号	含义
k	扩展编码后消息所占内存cell数
m	原本消息所占内存cell数
q	cell的状态数
p	cell的状态数

满足关系m<k，p<q。也就是说，原本有q个状态,m个cell的信息，我为了节约能量，使用更多的k个cell，每个cell至多p个状态来保存。

值得注意的是，这里的k个cell中，理论上每个cell仍有q个可能性，我们只是选择性的用p个

编码的实例

对于1个16bits的数据来说，我们只需要6个TLC就可以了（图a）
（3，2）来说的话（图b），只有0167这四种状态，所以需要8个TLC。图c同理

数据的压缩

本文的核心思想是对压缩后的数据有选择地进行扩展编码，使扩展后的数据不超过原始数据的宽度。例如，如果n位原始数据被压缩到≤2n/3位，则（3,2）8扩展码将不会产生内存开销，并且还产生扩展编码的全部能量和延迟效益。

由于FPC压缩的64位字（或BΔI压缩的64字节缓存线）的最大大小只有19位（36字节），我们可以在FPC上轻松地分层（3,2）8扩展编码，而不会产生额外的内存开销。

下面的图中我们以16bits的字为例子（多了画图看不过来）
某个数据压缩以后是 011 101 10X XXX XXX X 1
对于每个TLC可以有8种状态的来说，这一共使用了3/6个TLC
如果使用COMPEX编码，该压缩数据可以被（3，2）处理后，仅占用4个TLC

这里的logical编码和physical编码我还没有太弄明白，感觉不应该画这种对应关系

所以，对于一个64bits的字，经过FPC压缩后，再经过COMPEX编码后最多使用18个TLC(35/2上取整 = 18)。 这是因为FPC对一个64bits的字压缩后至多35bits（见前表）.
而对于一个64B的cacheline来说，使用BDI压缩后，最多需要146个TLC。这是因为至多36bytes, （36*8+4）/2 = 146

尽管我们需要一个tag来标记是否是COMPEX的编码结果，对于65bits的FPC和513bits的BDI来说，本来需要65/3 =22TLC 和513.3=171TLC的，现在肯定是节省了。
就像上图展示的那样，tag位被添加到数据字的尾部并且被编码到最后一个TLC，由于2的幂次肯定不能被3整除，所以这个tag位一定可以被编码到已经存在的TLC种而不需要额外的开销。另外，为了保证tag位不影响延迟，我们用7来表示使用了COMPEX-CODED

核心架构

整体架构

本节描述在NVM模块控制器中集成Com-pEx编码的体系结构。CompEx编码的体系结构包括写入路径上的CompEx码编码器和读取路径上的CompEx码解码器，如图所示。CompEx编解码器（编码器-解码器）逻辑嵌入在NVM阵列和数据总线之间的NVM模块控制器中，以无缝地对所访问的数据进行编码和解码，如图所示。CompEx码编码器由压缩逻辑和扩展码编码器组成。类似地，Com-pEx码解码器由扩展码解码器和解压缩逻辑组成。基于FPC的Com pEx cod ing使用字大小的写/读访问，而基于BΔI的Com-pEx编码使用缓存线大小的访问。
（有一说一他这个图是抄的，我看过这个图）

写过程

写入：每当MLC/TLC NVM模块从处理器端的内存控制器接收到写入访问时，CompEx编解码器按如下方式处理它们。
首先，传入的数据通过压缩逻辑传递，该逻辑将数据与所有压缩模式进行比较，以尝试数据压缩。如果数据是可压缩的，则压缩数据通过扩展码编码器；不可压缩数据直接发送到写入电路。
扩展码编码器将压缩数据的每2位片段编码为3位码字。然而，由于编码数据的宽度总是小于64位（对于FPC）和64字节（对于BΔI），因此CompEx编码具有零内存开销。
请注意，可能需要更新标记位以记录CompEx编码的结果，而不考虑它是否成功。但是，如前所述，这个标记位可以连接起来，并且可以使用最后一个TLC将ab吸收到数据中，而不需要为标记位添加额外的单元。

读过程

读取：当MLC/TLC NVM模块从存储器控制器接收到读取访问时，NVM模块控制器侧的CompEx编解码器在将数据转发到存储器控制器之前对其进行解码。读取电路读取整个字的单元并将数据转发到CompEx编解码器。标签位从读取字的最后一个TLC中恢复，用于确定数据是否必须被强制解码或直接转发到NVM模块控制器。

评估

我们对CompEx编码的评估是基于

1. 全系统仿真来评估CompEx编码的系统级性能。
2. 基于跟踪的仿真来评估存储器级能量和CompEx编码的延迟。

全系统仿真

CompEx编码是通过一个系统的全系统模拟来评估的，该系统集成了TLC-RRAM存储器，使用全系统多核模拟器MAR-SS和DRAM-Sim2，DRAM-Sim2是一个循环精确的主存储器模拟器。

MARSS使用PTLSim[58]的x86核心模型，PTLSim[58]是一个周期精确的x86微体系结构模拟器，并将其插入QEMU[59]中，QEMU[59]是一个用于模拟整个系统的二进制翻译系统。QEMU提供了模拟各种I/O设备（HDD、以太网、HID等）的能力，这些设备可用于在不进行任何修改的情况下启动整个操作系统（本文中是Linux）。注意，在这项工作中，我们修改了MARSS，以便在整个内存层次结构中随着ad-dress传播写数据。

我们使用DRAMSim2，一个周期精确的主存模拟程序来模拟DDR3 NVM主存系统。MARSS和DRAMSim2集成在一起，为整个系统提供单一、无缝、循环精确的模拟。由于TLC-NVM内存中的每个访问可能有不同的访问延迟，因此我们修改DRAM-Sim2来解释这一点。

MARSS设置：MARSS被配置为模拟在3GHz下运行的标准4核无序系统。每个核心都有自己的一级缓存，其中有两个用于数据和指令的32kB SRAM的单独实例；二级缓存是私有的，每个核心都有自己的256kB SRAM实例；最后，三级缓存是一个大小为8MB的单个共享回写缓存。表4列出了每个缓存级别的延迟。

轨迹驱动仿真

为了运行深度、数十亿指令模拟，Com pEx编码使用内部跟踪驱动模拟器（用于评估内存阵列级动态能量）和NVMain（用于评估内存模块级的总能量）来评估。我们修改了NVMain，以反映CompEx编码的可变写入延迟，还配置了NVMain，以模拟与表4中相同的架构。这些记录道是在运行3.3 GHz Intel Core i7 CPU的计算机上使用Intel Pin二进制检测工具从SPEC CPU2006基准套件生成的。请注意，我们还使用Gem5系统模拟器使用等效体系结构验证这些结果；结果与本文所报告的一致，为简洁起见，不讨论这些结果。我们的模拟框架从处理器捕获内存访问，只记录发送到主存的访问。在跟踪生成过程中，基准测试首先运行5×105个内存写操作，忽略程序初始化时的写操作；然后运行基准测试，直到记录了4×106个内存写操作（平均相当于大约4 bil lion指令）或程序终止。

额外的讨论

CompEx编码和ECC:

MLC/TLC NVM易受软错误和硬错误的影响，这需要使用错误检测和纠正（EDAC）技术，如ECC、ECP等。带EDAC的NVM通常使用可分离编码技术，即数据字段与EDAC字段分开存储。由于写入操作可能会同时改变数据和EDAC字段，因此对数据字段进行编码的CompEx的好处可能会被EDAC字段中的高延迟写入所抵消。为了解决这一潜在缺点，我们建议，当数据字段可压缩时，EDAC字段应以扩展编码形式写入-扩展编码EDAC字段所需的额外单元格可从压缩数据字段后的剩余单元格中获取。我们可以推断基于FPC（BΔI）的CompEx编码在最坏的情况下会留下4（30）个tlc未使用，其目的是以扩展编码形式提供EDAC，以保持/延长CompEx编码的延迟/能量效益。另一方面，如果数据字段是不可压缩的，则数据和EDAC字段都是使用传统二进制编码编写的。

CompEx编码和加密

NVM非易失性已成为一个严重的数据安全问题即使在系统断电后，存储的数据仍会继续存在于内存中，从而使敏感数据暴露给恶意入侵者。阻止此类攻击的主要建议是在写入NVM主存之前进行数据加密。然而，加密会扰乱数据，并可能降低强制编码所必需的数据规则性。这种限制可以通过将CompEx编解码器与加密引擎集成来规避。通过在加密之前压缩数据，可以对加密的数据使用扩展编码来保留CompEx编码的大部分优点。由于加密引擎主要位于处理器内的内存控制器中，因此本方案要求CompEx编解码器从NVM模块移动到处理器。对CompEx编码和加密之间相互作用的全面研究不在本文的讨论范围之内。