读论文笔记：Memory Ordering: A Value-Based Approach
ABSTRACT:
常规的乱序处理器采用多端口，全关联的load queue保证单线程和多处理器多线程的正确内存引用计数，但随着频率加快和工艺改进，in-flight的load数量变多，缩放原有的结构困难且高耗能，因此，本文完全消除关联load queue，而是在retirement前按程序顺序重新执行和加载指令即可保证数据依赖性和内存一致性约束。
1. Introduction
本文通过改进load/store队列来提供计算机效率。
Load和store队列通常使用内容可寻址的内存为保障内存指令的正确依赖提供一个地址匹配机制。一个load指令发布，store queue CAM会寻找一个与之匹配的地址。当一个store地址产生，load queue CAM会寻找一个先于这个store指令错误猜测发布的相匹配的load指令。load queue也会在每次load发布时被寻找，有时也在外部的无效请求时被查找。由于指令窗口的增加，in-flight的loads和stores数量增加，导致了增长的CAM访问时间。
针对现有问题别人的解决方案面临过于复杂或者无法伸缩（scalability）的问题。
本文不再通过CAM在load queue中寻找，而是提出了一种value-based repaly machanism，在load指令commit前重新载入一遍load的值，若相等则继续，若不相等说明该load和一个之前的store乱序了，违反了内存一致性模型，之前利用了不正确的值的指令都会被squashed。
为了缓解replay带来的花销（增加的缓存带宽和资源侵占），本文评估了几种过滤出需要replay的loads的启发式方法。平均只有0.02提交的指令需要replay。
本文只消除了load queue的RAM而没有消除store queue的RAM，原因在于，1、load指令比store指令占比更多（30%、14%），因此load queue的RAM更复杂。2、store-to-load，从store转发到load是更正常的，而违反RAW是小概率事件，因此store quque的RAM对性能比较关键，不能消除。3、load queue的CAM查找更加频繁（既被load又被store指令以及外部的无效信号查找），需要更多的ports。
总结本文贡献：
1、通过value-based replay消除了load queue的关联查找逻辑；
2、Replay-reduction heuristics: 过滤出了需要replay的load指令（只占很小一部分），对缓存带宽的影响可以忽略。
3、consistency model checking: 定义了检查内存一致性的限制，可以检测一些错误。
（本节中介绍了背景，提高IPC和时钟周期是相违背的，因此把目光瞄向影响性能且难于按比例扩大的load/store queue的CAM，现有的维持内存一致性的方法是每发布一个load/store指令就在CAM中查找是否有与之对应地址的已发布的load/store指令，本文提出了基于value的replay的方法，完全消除了对load queue的CAM，在每次Load提交前reload这个值，如果和之前使用的值相同，就继续，如果不同，就说明可能违反了内存一致性，因此squash这个load及之后的操作。但是replay会带来cache port的增加和资源侵占，因此本文提出了几种过滤器，可以过滤出只占很少比例的需要replay的Load。还提出了一些限制条件来检验内存一致性。）
（2节中描述了原本的关联载入队列的微结构。3节中提出了我们的value-based replay mechanism和过滤器。4节中介绍了实验，之后是我们的机制和原有load queue设计的性能对比。）
2. Associative Load Queue Design
2.1. Functional Requirements and Logical Design
load queue的正确性需求来自两种，一种是在store没有解决地址的时候，后面的load被乱序发射。第二种是跨核之间的不正确的重排序。
如果3.在2.没有计算出地址的情况下发布，而2.计算出的地址也是A，那么3.就载入了错误的值，原本的结构使2.的store指令在发布时在load queue中搜索是否有对应地址且程序顺序晚于它的load，如果有就squash该load及之后的操作。
一种解决方案是把load指令延迟到前面的store都已经被计算完地址之后发布，但是不能满足内存一致性，因为虽然前面的store地址被计算了，但是可能某个内存操作被重排序了，导致违反内存一致性模型。（比如说，一个程序被编译优化，程序排序实际没有变化，但是程序的执行顺序被改变了，原本排在后面的操作被排到了前面执行，如果只是延迟load指令到前面的store地址都被计算出来之后再执行，就会违反内存一致性，但是如果使用CAM，等到store指令发布的时候再去load queue中去搜索一下，就能squash前面的指令，维持内存一致性。）
有两种针对外界无效的方式，一种是外界传来的无效请求对cache和load queue都起作用，缓存的替换或导致load queue search。另外一种是外界的无效对已发布的load指令不起作用，而是通过之后的squash and replay该对应地址的load来维持内存一致性。
snooping的load中，无效信号会驱逐乱序的载入。而在insulated的load中，排在load队列最顶端的load执行后，发现它后面的load以及执行完成，发生了load-load乱序，因此驱逐了后面的指令，来维持内存一致性。
在snooping的load中，无效信号会驱逐乱序的load。因此p1的1.发出的无效信号会驱逐p2中2.的load。而在insulted的load中，排在load队列最顶端的P2.1在执行完成的时候，发现它后面的load也已经执行完成，发生了RAR乱序，因此驱赶了后面的指令。
隔离load适用于弱顺序模型，snooping load适用于强一致性模型。它们都是CAM的规则之下不同的应对外部无效的方法。隔离load是在每个指令被发布的时候去load queue中搜索一遍，驱赶程序顺序在其后，和其地址一样但是先被执行的load。以图(c)为例，先执行P1.2,再执行P1.1，P1.1会去load queue中查找一遍，驱逐地址一致、程序顺序在后的load，避免RAR。但是如果P1.1载入的地址是B，还是按照原本的执行顺序执行，由于没有排在P1.2前面的load A，因此不会驱逐A。由此可见，snooping load可以保证强顺序一致性，而隔离load只能保证单核内的顺序一致性（RAR），而不能保证跨核之间的RAW乱序，属于弱一致性模型。
采用snooping load的计算机不必要在load发布的时候扫描load queue，但是需要为无效信号增加专用的CAM port，采用隔离load的计算机需要在每次load发布的时候都扫描load queue。
2.2. Physical Design
Load queues通常由两个主要数据结构实施，RAM结构包含一组被组织为循环队列的entries（RAM中包含了每一个动态load的meta-data如，PC, 目的寄存器id等，并被instruction age索引），和一个关联的CAM用于在queue entries中寻找一个匹配的条目。Load queues的CAM的端口数需要满足同时发布的store和load指令数量(在弱一致性模型中load/store指令被发布时都会在load queue中查找对应地址，强一致性模型中不会)，有时还有外部的访问请求，而Store queues的CAM只需要满足同时发布的load指令数量。由age来决定一个地址匹配的load指令是否应该被驱逐。
load/store queue的ports数量由可以同时发布的load+store指令数量/load指令数量决定，load queue的端口数量可能还会因为接收外部无效信号而增加。
在相同的read/write ports下，search消耗的能量随着entries的增加而线性增加，而associative load queue search latency则对数增加。随着processor的不断改进，放大这一种模式将会带来巨大的能量和时间的损耗，因此我们需要提出一种新的load queue来替代原有的这种模式。
3. Value-based Memory Ordering
本文转化复杂性从流水线的时间关键部分（调度器/功能单元/旁路路径）到流水线的后端，原本在store指令发布的时候在load queue中查找，而现在不查找，而是在流水线提交之前增加两个步骤（replay and compare stages）。
load instructions that are replayed stall the pipeline until all prior stores have written their data to the cache. 同时，replay相比于premature阶段的load效率大大提升，因为它可以利用从TLB中取得的地址，而且若无意外，它可以直接在L1 cache中取值。同时，replay对cache的访问比store queue对cache的访问优先权低。
如果replay取得的值和premature阶段的值一样，那么就正常提交。如果值不一样，就驱逐该load指令以及之后的所有后续指令。
采用replay机制后，将关联load queue替换为一个简单的FIFO buffer，除惯常的存储在load queue的meta-data外，新增在premature阶段的载入地址和数据。
- all prior stores must have committed their data to the L1 cache.因为replay和store都需要访问cache port，如果repaly的load指令顺序先于store，那么它先，如果store的指令顺序先于replay，那么replay先执行。
- all loads must be replayed in program order.为了保证内存一致性，load的replay必须按照程序的顺序进行，使之在外部的处理器中看起来是原子性的。如果replay load遇到了cache miss，那么之后的replay需要在这个miss被解决之后再执行。
- A dyanamic load insturction that causes a replay squash should not be repalyed a second time after sqush-recovery. 因为如果再replay，对一个共享数据的争用会导致一个load反复被squash并且replay。
the value-base replay mechanism机制的缺点是虽然可以驱逐违反RAW的指令，但是不知道是由于哪个store指令导致的，因此妨碍了store set predictor之类基于store指令的预测器的预测。
我们在一个PC-indexed的表上用一个位置表示是否该load是之前的数据依赖误预测的受害者，如果是的话，需要等到它前面的所有store的地址计算出来才issue该load。
replay mechanism可能会导致效率的下降，因为占用了cache带宽，并且进行了二次访问和值的比较，因此本文提出了几种启发式的过滤措施，来过滤一些loads使之不需要replay。
3.1. Filtering Replays While Enforcing Memory Consistency
本文提出了一个constriant graph，这个graph上的点代表动态指令，边代表正确的程序顺序还包括RAW/WAR/WAW依赖边。通过这个constraint graph可以检验执行的正确性。如果图中形成了环就是说明指令没有一个总顺序，有可能会侵犯顺序一致性。
若在constriant graph中的cycle中存在两个不同处理器执行的依赖边，如果它们没有违反指令顺序重排序，就不会有违反一致性的潜力。
No-Recent-Miss Filter:
如果一个constraint graph中不存在从外部源（如另一个处理器的缓存中）载入的缓存，就不存在来自别的处理器的依赖边，就不需要replay loads来核对一致性的限制。而如果load B引发了一个cache miss（很可能是核2的store指令发送了cache无效信号），需要从核2中取cache，这个cache unit就会发送一个信号，一个“recent miss/need-replay”位会被设置到指令窗中当前的所有load指令，这些指令将会被要求replay。
No-Recent-Snoop Filter:
类似于No-Recent-Miss Filter，No-Recent-Snoop Filter用于过滤跨核之间的WAR依赖，当load指令在乱序指令窗口时，如果核观察到了一个外部对任何地址的无效，就会触发这些load指令的replay。
No-Reorder Filter:
在没有乱序，完全按照程序顺序的处理器中不需要replay，因为它们不会违反内存一致性模型。
3.2. Filtering Replays While Enforcing Uniprocessor RAW Dependences
过滤掉那些在发布时没有绕过任何未解决地址的store指令的load。
3.3. The Interaction of Filters
介绍了四种过滤器分别过滤出了哪些需要被replay的load指令，no-reorder filter可以被单独使用，no-recent-snoop和no-recent-miss讲的是跨核之间的违背内存一致性，而no-unresolved-store过滤出了单核之间可能会产生的RAW依赖的指令。
No-unresolved-store filter需要和no-recent-snoop或者no-recent-miss filter配合使用，因为后两种都是针对跨核之间的RAW。
4. Experimental Methodology
本文使用PHARMsim，一个集成SimOS-PPC全系统模拟器的乱序超标量处理器模型。
介绍了基准机器配置和其它的benchmark的描述。
选择了SPECINT2000以及SPECFP2000中几个可能会和value-based replay mechanism产生消极交互的benchmarks。
5. Experimental Evaluation
5.1. Performance Comparison
没有replay的过滤器也只产生了平均3%的性能惩罚。
图6（a）中replay all没有100%增加LIDCache访存是因为首先存在一些误猜测，这些误猜测下的load操作被squash了，不需要replay，其次可能能从store queue中得到这些replay的值。
相比于传统模式，value-based replay机制消除了更多的因为违反RAW或内存一致性的squash。因为尽管发生了RAW，但是premature阶段载入的值可能刚好就是replay载入的值（由于值的局部性，或者premature载入了一个中间的store，刚好也是这个值）。同样地，因为违反内存一致性而导致的squash也减少了很多（比如两个load虽然乱序了，但是它们实际上载入的值还是相同）。
平均reorder buffer利用率。
5.2. Constrained Load Queue Size
相比于当前有代表性的32-entries的load queue，性能平均提升了1.0%，相对于16-entries的load queue，性能提升了最多34%，平均提升8%。
5.3. A Simple Power Model
如果每次CAM的能量消耗大于高速缓存和字大小比较的能量消耗的0.02倍，本文的方案可以降低功耗。
6. Conclusions
Value-based mechanism目前主要目标在于在同时保证内存一致性的同时，缩减load/store队列的复杂性，它也有节约的能量、低功耗的潜力。