利用相变存储器不对称性的写入优化方法

张格毅，陈小刚，郭继鹏，3，宋志棠，陈邦明

1.中国科学院 上海微系统与信息技术研究所 信息功能材料国家重点实验室，上海200050

2.上海科技大学 信息科学与技术学院，上海201210

3.中国科学院大学，北京100049

相变存储器PCM（Phase Change Memory）是目前公认最有发展潜力的新型存储器之一。对PCM的首次研究可追溯至Ovshinsky 于1968 年开始的相变材料的相关研究工作，然而PCM 在20 世纪受制于半导体技术而发展缓慢，直至20 世纪末，才取得突破性进展[1]。目前PCM的应用有很大潜力，针对PCM特点的相关优化技术还有待发掘。PCM是利用相变材料在晶态和非晶态时的电阻率差来存储信息的非易失性存储器，其写1（set）、擦0（reset）与读取的工作原理如下：set时通过一长约100 ns～1μs的弱的电流脉冲，让相变材料转换为晶态，而reset 时通过一个短的强电流将材料转变为非晶态。读取时给材料施加一短且弱的电流脉冲，根据材料的阻值读出存储的信息。如图1所示，set的时间为reset的数倍，这一特性即PCM的擦写不对称性。

图1 相变材料在不同操作下温度示意图

PCM 是一种非易失性存储器，具有字节可寻址和可以原地更新的性质，相比目前主要的非易失性半导体存储器FLASH，其在访问速度和使用寿命方面具有明显优势。而在存储密度、功耗、成本等方面，PCM与目前主流的内存DRAM（Dynamic Random Access Memory）相比也具有明显优势[2]。这些性质使得PCM 具有替代DRAM 成为非易失性内存的潜力。但在用作内存时，PCM 也同样面对了诸多挑战，比如主存的访问方式与硬盘不同，访问的频率和集中度更大，PCM的设计者必须考虑提出新的优化技术以增加写入寿命。PCM虽然读取延时一般在100 ns以内，达到了与DRAM同一数量级。但写入延时方面，与PCM 的需要数百ns 甚至接近1 μs，而DRAM 只需20～50 ns，相差了一个数量级[3]，面对内存的访问需求仍有一定的差距。并且随着业界对PCM 的研究和开发越发深入，PCM 的定位从最初的SSD 越来越向内存靠拢，面对这些未来的发展方向，如何增加写入寿命和减少写入延时，使PCM 的性能满足内存的需要已然是目前需要考虑的重要研究课题。

针对上述PCM 面对的挑战，提出了RSIW（Reset and Set Independently Write）方案，传统的写入操作每一次写入时都同时包含set 与reset 两个操作，根据写入数据对每一位进行写1或擦0，在RSIW方案中利用转换层的技术进行映射使得这两种操作相互独立，并不局限于都在一个写入周期内执行，收到写入指令时只执行快速的reset 操作，set 操作则在存储器空闲时预先执行。目前已有的根据PCM不对称性进行优化的方案中多为根据其写入策略调整set 与reset 的顺序等操作，不能像RSIW针对不对称性进行最大化的利用。同时为了进一步解决地址映射耗时长的问题，本研究提出了包括动态PCM 转换层（Dynamic PCM Translation Layer，DPTL）和地址指针模块等可以快速完成地址映射的设计。

1 国内外研究现状

为了解决PCM 写入延时和使用寿命方面的问题，相关研究人员已经做了大量的工作比如改进材料、工艺，除了从器件本身进行改进之外，也有诸多在使用带DRAM 的混合存储系统的架构[4]和其他方面的改进。比如在文件系统方面Lee 等人提出专门针对PCM 设计的文件系统shotcut-JFS，通过避免日志数据的复制，减少大量写操作，相比传统的ext3文件系统提高了40%的整体性能[5]。Zhou等人提出部分写的机制，在写入前先读出该地址上的数据，与即将存入的数据进行对比，只修改部分有差异的位[6]。在降低写延时方面，Cho 等人提出Flip-N-Write（FNW）的方法，该方案通过增加一个翻转位，写入时先读出该地址上的数据进行对比，确定数据中需要修改的位的数量，即新旧数据之间的汉明距离，如果小于总数据的一半则直接写入，反之将数据取反后再写入，并用翻转来记录此处的数据读出时是否需要取反，从而可以将实际需要写入的数据位数始终保持在总的数据位数的一半以下，从而有效地提高写入速度[7]。部分写入FNW 的方案都是通过减少写入次数而提高写入速度的方法，同时由于写入次数减少，PCM的使用寿命也会增加。

除了上述优化方案外，近年也有人提出利用PCM的擦写不对称性进行优化的方案，例如Qureshi 等人在2012 年提出了一种preset 的方式，利用内存的工作特性，在缓存行内的数据被修改时，生成一条preset请求，在数据被写回前提前将该行对应的数据全部进行set，待写回时只需要进行reset 操作，从而提高PCM 整体性能[8]。随后Yue等人提出了Two-Stage-Write（2SW）与优化的Two-Stage-Write-Inv（2SWI）方案，这一方案将写入过程拆分为两个阶段，第一阶段进行高速reset，第二阶段增强并行写入的机制进行set。2SWI 在第二阶段的可与FNW技术结合，使得写入的时间减少为2SW方案中的一半，并在Cho 等人的研究结果上进行了优化，减少了原FNW方案预读操作的时间[9]。进一步的，Li等人提出了three-stage-write（3SW）的方案[10]，该方案第一阶段读取预写入地址中的原数据，第二阶段进行快速的reset，第三阶段进行set，第三个阶段与2SWI方案类似，但Li 的团队在第二阶段中结合了FNW 的技术，使得reset的时间能有效降低。上述的2SW、2SWI和3SW都是利用PCM 的擦写不对称的特性来提高PCM 整体性能的方法，但这些方法都是在写入时，提前进行reset，写入时还是会受到set 高延时的影响，基于上述特点本文提出了RSIW 的方法，旨在让set 和reset 两种操作相互分离，写入时只执行reset 操作，set 则在空闲时进行，使其能独立执行，故称其为擦写独立的写入方案。同时，RSIW需要对每一次PCM写入进行重新映射，在这一步骤中加入了动态磨损均衡的方案，在极大地减少写入延时的同时增加PCM整体的使用寿命。

在提升PCM 使用寿命方面，除了上述提到的改进器件性能，和各种减少写入次数的方法外，磨损均衡也是本领域的常见手段。存储器整体的使用寿命受到存储器内各个存储单元的短板效应限制，磨损均衡通过平衡内部各个存储单元的写入频率，避免了由于短板效应而导致整体使用寿命过低[11-13]。磨损均衡的算法可以分为静态磨损均衡与动态磨损均衡，其中静态磨损均衡是在存储器设备触发某一条件时，例如使用了一段时间或写入达到一定次数等，根据一定的算法来移动各个块的数据，动态的磨损均衡则是在写入时触发，根据其磨损均衡算法将数据写入至其他块上。RSIW方法本身就具备了磨损均衡的特征，运行时能够获得动态磨损均衡的效果，这一点是目前所有同类优化方案中都不具备的。

2 RSIW方案

2.1 RSIW方案简介

RSIW是一种利用相变存储器set与reset不对称性，对存储器进行优化的一种解决方案。其基本思想是将每一次写入操作都映射到一个干净的地址上，即该地址上的所有位都已经被预先set 过的地址。RSIW 最大的创新处在于将在同一个写入周期内的set与reset操作分离，将其视为两个相互独立的操作，可以不受干扰的在不同时间段执行。目前利用PCM的擦写不对称性进行优化的方案中，均是通过调整set 和reset 的顺序和方式来进行优化的，实际上每次操作都需要进行set 和reset操作，而RSIW方案则通过DPTL实现了set与reset的独立，从而更好地利用擦写不对称性来优化写入过程。

RSIW写入时基本流程的伪代码如下所示：

每次写入时，通过DPTL 获得一个干净的地址，随后立即将数据写入干净的地址内，写入的同时建立新的地址映射。写入过程中，结合了FNW技术，通过翻转位将写入的位数控制在总位数的一半以下(N/2)。由于写入的地址已知全部为1，相比同类方法省去了预读数据的步骤或增加额外的位来记录该地址内1 或0 的位数，运行效率进一步地提升。在写入的同时，PCM的控制器并行地完成对地址的映射，预备下一个干净地址和回收（set）空闲芯片上的脏地址，脏地址主要指存储了无用数据的地址，来源于内存的释放或同一数据重复命中时被映射至新的地址上。此处的并行处理并非并行计算，是因为被访问的存储单元在写入时与控制器回收脏地址之间的工作不冲突，可以在同一时间内进行，这一机制在下文中详细介绍。

RSIW是针对PCM应用于非易失性内存而提出的，由于内存的访问模式不同于外存，受块和页的限制，且要求反映延时更低，目前已有的硬盘管理技术不能很好地适应内存的访问需求，但如果使用内存的管理技术，存储的控制器算力低下，会造成不可忽略的性能损耗。为了解决上述问题，本研究提出了如图2 所示的设计，在内存管理的基础上加以改进，以满足RSIW能正常执行。该设计主要包括一个动态PCM 转换层（Dynamic PCM Translation Layer，DPTL）和地址指针模块（Addr pointer），其中DPTL 主要负责对地址进行管理和映射，增设的地址指针模块负责快速提供干净地址，地址指针中含有一个块指针和多个块内指针，块内指针用于判别该块内干净的地址段，块指针提供下一个要写入的块。结合伪代码与结构图，RSIW方法在写入时，首先通过地址指针模块获得一个干净的地址段，然后将数据写在相应的PCM 存储阵列中。在PCM 写入时，DPTL 更新映射，地址指针模块更新指针，提供的数据更新其中的地址映射。读取时则首先通过DPTL 获得相应地址的映射后读出所请求的数据。

图2 RSIW的结构示意图

2.2 动态PCM转换层

动态转换层（DPTL）的主要功能是地址映射管理，将输入的逻辑地址与实际的物理地址之间建立映射。DPTL 不同已有的PTL（PCM Translation Layer）转换层技术，它需要面对的是碎片化的地址管理，并且内存会有释放旧内存，建立新内存等问题，地址管理比普通的以块和页进行管理的PTL 更复杂，更灵活，其中的地址映射表的大小也会根据使用情况而变化，具有动态的特点。由于本研究的重点不是如何设计一个完整的存储器控制器，所以只讨论DPTL中的地址管理和磨损均衡的功能，其他PTL共有的基础功能不进行赘述。

由于本研究中将RSIW 预设在了内存的应用场景下，所以访问的地址大小更灵活，不受块与页的限制，不能照搬PTL 中的传统管理方案。而内存的地址管理方面比较成功算法是平衡二叉树和伙伴算法，其中平衡二叉树的时间复杂度为O(lbn)，随着存储器容量的增加，需要的时间也会逐渐增加，PCM 本身就是大容量的存储器，并且PCM 控制器的时钟频率远不及CPU 的时间频率，进一步地加剧了管理地址时的时间损耗，所以此处提出一种基于哈希算法的映射进行管理方案，哈希查找法的时间复杂度为O(1)，且不会随数据量的增加而增加，而哈希查找法本身也是一种牺牲空间来换取速度的算法，能够与PCM 存储空间大的特点相结合。使用哈希表时如何解决冲突也是一个无法避免的重要问题，本课题采用链地址表的方法，即尝试冲突时连接到另一个表中，在该表中进行查询。使用链地址也更便于地址的拆分与合并，并且易于使用硬件加速提高查找效率。

2.3 地址的选取与磨损均衡

RSIW方案中提出了增设地址指针模块的方案以存储各个块内干净地址段的边界地址。地址指针模块中包括一指向块的块指针（图中的block_pointer）和一组记录了各个块内连续的干净地址段边界的块内指针（inblockp），块内指针的数量可以有多组，其结构如图3。PCM 最初未使用时所有地址均为干净地址，在使用中根据写入情况调整块内指针的指向范围。收到写入的指令时，通过块指针找到预写的块，然后根据块内指针获得块内干净地址段的边界，通过边界即可获得干净地址。在空闲时会回收脏地址并整理碎片，释放出干净地址并重新调整块内指针。

图3 指针模块示意图

磨损均衡是RSIW方法中必有的功能，此处提出了一种定向地址偏移的方法进行磨损均衡，该方法更易于将干净地址集中在一段连续的地址内，利于块内指针进行地址管理，除了这一种算法外其他算法也可以与RSIW相结合，但相关算法并非本研究主要讨论的问题，对此不深入讨论，仅提出这一种结合RSIW其他特性的可行的方法。该磨损均衡的算法的伪代码如下所示：

在空闲时根据上一次的写入情况将块指针指向下一个可写块（具有足够干净地址的块），块的选择根据预定的方向依次进行偏移，若偏移到末位块后则跳回至第一块。完整的地址在获得可写块后，根据该块对应的块内指针所指的干净地址边界获得所需的干净地址，并存储该地址，写入时可直接使用。所述的在空闲时间所指的是在存储器接收到写入指令之间的空余时间，这段时间内完成指针模块的更新。这一算法的性能会在本文的实验部分通过实验和数据进行具体说明。

地址指针模块的功能也很容易使用电路实现，从而可以使用硬件加速进一步地提升其速度，此处结合相应的电路波形仿真进行说明，仿真实验中通过逻辑电路设计了该指针模块并使其工作在500 MHz的时钟下，其中blockp 即地址指针，inblockp1 和inblockp2 为块内指针，ctl 和write_en 为控制信号。其实验结果如图4，块内指针根据磨损均衡和垃圾回收算法可以设置多组以记录多个干净地址段，本实验中使用的算法只需要两个指针便可满足需求。从实验结果中可看出，块指针如上述算法所描述的，块内指针在控制信号的控制下每次向后移动一个块，tadr_out 输出了该块内的一个干净地址。该电路每隔几纳秒便可向DPTL 提供一个干净地址作为映射的物理地址使用，远超存储器控制器的运行速度，同时此操作可分配在空闲时间完成，配合其他模块快速完成地址映射，以满足RSIW低延时的需要。

图4 指针模块仿真实验波形结果

脏地址的回收也是伴随着动态磨损均衡和内存的使用所需解决的重要问题，脏地址的回收是否及时也关系到存储器能否有足够的使用空间。脏地址的回收如图5所示，目前的内存条结构基本都由多个存储芯片组成，每个芯片内部有Bank 组，每个组中含有多个Bank，每次访问时只会选中其中的一个Bank，如图5中选择了其中的Bank3，则其余的Bank则处于本方案中的空闲状态。采用这种机制可以有效地提高脏地址的回收效率，set 的平均时间会远低于一次reset 的时间。空闲Bank并行回收的策略虽然效率高但也带来了回收与正常读写指令冲突的问题，所以此处可以引入写取消的策略，来自上位机的读写指令优先于脏地址回收，当某一正在set 脏地址的Bank 被选中后立即停止set 而执行上位机的读写命令。

图5 RSIW方案中脏地址回收示意图

3 与同类技术对比

为了进一步验证RSIW方法的创新性与优势，本文中将这种方法与经典的FNW方案和与本方案最相近的2SW、2SWI和3SW方案进行对比说明。如图6所示，图中列举了各个方案写入时消耗的最大时间，其中一个大方块代表无优化的情况下写入一个单元花费的时间，白色方块表示一次读取花费的时间。FNW的基本思想是在接收到写的命令后首先在T0至T1时刻读取出欲写入地址处中的数据，随后对比原数据与需要写入的数据，如果写入的数据与原数据的汉明距离Δ超过写入数据长度的一半(N/2)（包括修改翻转位的影响）则标记翻转位，写入取反后的数据。其中汉明距离的计算如公式（1）所示。由于FNW 的实际写入的位数始终能保持在N/2 以内，如图6所示，最大写入时间为T7。通过简单的分析，FNW 方案的最大写入时间如公式（2）[7，10]所示，每次写入的时间开销为一次读取时间加上M/2 次写入的时间，M为完成一次缓存行内数据的写入需要写入的次数，FNW方案中每次写入的时间与set的时间相同，故使用Tset来表示一次写入的时间。

图6 RSIW方案与其他接近方案对比图

同样的，2SW 和2SWI 的写入最大时间如公式（3）和公式（4）[9-10]和图6所示，这两种方案类似，第一阶段的reset均在T4时完成，所有reset消耗的时间与一次set的时间接近，第二阶段2SWI方案中结合了FNW的技术方案，在set 阶段可以进一步地优化写入时间，2SW 在T8时完成写入，而2SWI 由于set 时间降低为原来的一半，在T6时写入完成。公式（3）、（4）中的L为一次增强并行写入可同时操作的单元数量，本文沿用了参考文献中使用的参数L=2[10]。

3SW 方案消耗的最大时间如公式（5）和图6 所示，第一阶段为读取阶段，在T1时刻完成，第二阶段reset相比上述的方案结合了FNW技术，耗时更短，第三阶段同2SWI方案的第二阶段相同，最终在T5时完成写入。

RSIW方案消耗的最大时间如公式（6）和图6所示，RSIW方案只需进行reset便能完成写入，所以消耗的时间是最短的。基于内存的工作原理，只有被选中的bank在进行写入，而相较于被选中的bank和存储器控制器，在T0到T1都处于空闲状态，可以执行set操作和地址映射。

除了从图6中进行形象的对比外，通过公式计算也能更具体地对比各个方式的优劣，此处使用上海微系统与信息技术研究所信息功能材料实验室的PCM项目组生产的一款64 MB的PCM芯片的工作和性能参数进行计算。其中，Tread约等于Treset，set 的时间约为reset 的六倍。公式中的M和L使用Li 等人论文中的数据，L=2[10]。代入上述参数后可得TFNW=25Treset、T2SW=32Treset、T2SWI=20Treset、T3SW=17Treset和TRSIW=4Treset。结果如图7所示，RSIW方案速度最快，相比上述方案中读写周期最短的3SW减少了76.5%，相比FNW、2SW和2SWI分别减少了84%、87.5%和80%。

图7 各方案写入延时对比图

4 实验

本实验选择了gem5[14]仿真器作为主要的实验平台，该仿真器平台示意如图8，gem5 是一款受众多研究者青睐的事件驱动全系统仿真模拟器，由多所大学和公司联合开发，包括AMD、ARM、HP、MIPS、普林斯顿大学、麻省理工学院以及密歇根州大学等多家机构，其仿真结果真实可信，具有灵活，可用性强，可协作性高的特点，广泛应用于学术界中的众多研究中[15]。由于PCM芯片成熟的产品较少，芯片设计流片的时间和经济成本一般的研究团队都难以承受，因此使用仿真器来进行实验验证也是大部分相关研究人员的首选。

图8 仿真平台示意图

仿真模型中系统的架构具有两层缓存，第一层cache的容量为16 KB，第二层cache的容量为64 KB，使用32 GB的PCM作为主存。CPU选择了2 GHz的Timingsimple X86架构。仿真器中PCM的性能参数选用了上海微系统与信息技术研究所信息功能材料实验室的PCM 项目组生产的64 MB 的PCM 芯片的工作参数，和其他根据该芯片获得的实验参数进行设置，其中主要参数设置如下：100 ns的reset延时，600 ns的set延时，100 ns的读取延时，所有实验中的PCM 器件模型的参数保持一致，保证实验结果不受物理材料和器件影响。仿真使用的testbench 为SPEC2006[16]测试集中的八个测试程序，SPEC2006 为SPEC（Standard Performance Evaluation Corporation）公司发布的一款用于评估计算机系系统性能的标准测试集，由两个整数测试和浮点测试的子测试集组成，被广泛地应用于各种计算机方面的研究中。为了能客观准确地验证各个技术方案的优劣选择了perlbench、bzip2、gcc、mcf、milc、leslie3d、sjeng、lbm 这八个testbench 进行测量，其中前四个为整数测试，后四个为浮点测试。

4.1 哈希函数分析

哈希函数的不同直接会导致产生冲突的次数不同，进而对RSIW 的性能产生重要的影响。本研究对比了常用的用于查找的哈希函数中选择了取余法、折叠法和平方取中法。其中折叠法有两种，折叠法1在原数据的基础上进行折叠，折叠法2先将原数据以哈希表的长度作为进制进行了换算后再进行折叠，提高其装填因子。实验中为了能更好地进行对比，将哈希表的长度设置得比较小，各组实验的装填因子均在0.9 以上。各个方案中产生冲突的次数如图9所示，其中产生冲突最少分别是折叠法2 与取余法，产生冲突最多的为平方取中法。平方取中法选取的是中间的几位，与折叠法2 同样，哈希值不能均匀分布在哈希表中，效果明显劣于其他算法。根据实验用的内存访问trace 的分析，逻辑地址本身的分布就比较均匀，所以在使用取余法时也能获得很好的效果，改进后的折叠法2的效果与取余法接近。综合考虑了各方面因素，取余法计算简单，且计算出的哈希值与输入的数据相关性比较好，所以选择取余法作为DPTL中的哈希函数。

图9 冲突产生次数对比

4.2 磨损均衡优化结果

磨损均衡是应用于PCM 中的一项重要技术，在实验中，由于提出新的动态磨损均衡算法并不是本文的主要研究方向，RSIW 也可以与其他动态磨损均衡算法兼容，且其他同类的优化方案中也不具有磨损均衡的功能，故这组实验中仅使用无优化的写入标准差与采用了RSIW 方案的写入标准差进行对照，以表明RSIW 具有磨损均衡的功能。实验中以使用了定向地址偏移的方法进行动态磨损均衡，并对比了各组testbench下的写入标准差。写入标准差能有效衡量各个块之间写入次数差异，也是对比磨损均衡算法时常用的指标。实验结果如图10，通过与对照组的对比，可看出RSIW 使用的定向地址偏移法能有效均衡数据在各个块之间的写入差异，写入标准差均能降到1 以下，相较未进行均衡的对照组表现突出。

图10 写入标准差优化对比

4.3 对系统性能提升结果对比

RSIW对性能的提升也是用于衡量其优劣性最重要的指标，通过gem5 的仿真得到了在不同testbench 下计算机性能优化效果对比如图11，其中的纵坐标为每秒指令数（Instructions Per Second，IPS），该指标能有效衡量计算机的运行效率，是对比计算机系统性能的常用指标，横坐标则是在不同的testbench 和不同的技术方案。图中的数据均以性能最差的2SW方案为基准进行了归一化，以便直观地看出各个方案系统性的优化效果。从图中可以看出，实验结果受到不同testbench 而影响，RSIW 方案可以明显地提高系统的运行效率，相比2SW、FNW、2SWI 和3SW 技术RSIW 将系统的运行效率平均提高了69.1%、54.6%、44.4%和37.1%。其中提升效果最好的为mcf 组，相较2WS 方案IPS 提升了近一倍，相较3SW 也有64.4%的提升，提升效果最不明显的是leslie3d组，相较2WS方案提升了50.2%，与性能最好的3SW相比提升了35.8%，其中整数类型的测试集效果差别比较大，优化的效果优于浮点类型的测试集。由于gem5 中的实验仿真中系统处理主存外，还设置了两层SRAM的缓存，缓存的存在减弱了主存的性能对计算机整体性能的影响，所以实际的实验结果与之前第3章中的计算结果有一定差异，但也更接近真实的优化效果。

图11 instructions rate提升对比

5 结束语

为了解决PCM 应用于非易失性内存时写入延时，写入次数不能满足需要的问题，本研究利用PCM reset与set 操作时间不对称的特点提出了RSIW 方案来优化PCM的写入速度，提高使用寿命。RSIW通过转换层建立映射，将PCM 的set 与reset 操作分离，相比现有的技术方案性能获得了显著的提升。针对存储器控制器运行速度低的特点，提出了相应的优化方案，提出DPTL，地址指针模块等手段来提高RSIW的运行速度，并通过实验对其内部的实施细节，例如地址管理的算法，进行讨论。同时，使用了定向地址偏移的动态磨损均衡算法进行实验，实验结果证明了RSIW可以与动态磨损均衡算法相结合，显著地降低各个块之间的写入标准差。文中还将RSIW 与FNW、2SW、2SWI 和3SW 方法进行对比，根据数理推导，相比上述方法一次读写周期的时间分别减少了84%、87.5%、80%和76.5%。最后的实验中，使用了gem5 仿真器和SPEC2006 测试集中几个具有代表性的测试基准进行实验，并与多种同类的技术方案在同架构和配置下对比了其IPS。通过实验结果证明了RSIW 可以有效地改善系统性能，相对其中性能最差的对比技术方案2WS平均IPS提高了50%，相比对照组中性能提高最好的3SW方案也有35.8%。通过上述的论证与实验有效地证明了RSIW相比同类的技术方案能更有效地优化其写入速度，并且可以提供有效的磨损均衡。