计算机体系的一些基本知识
解决流水线停滞主要是解决：资源争用数据依赖性控制依赖性1. 资源争用资源争用指，流水线中的两个阶段都需要某个硬件资源，解决资源争用的主要方法：复制资源，例如：使用独立的数据、指令内存，内存结构提供多个读写端口检测资源争用，停滞其中一个阶段例如，在ID阶段需要访问RegFile，以取出操作数，在WB阶段也需要访问RegFile，以将执行结果写回寄存器组中，这样就发生了对RegFile这一资源的争用。实际中，可以让RegFile在前半个周期给ID使用，后半个周期给WB使用。2. 数据依赖性数据依赖性包括：先写后读（read after write，RAW）、先写后写（write after write，WAW）、先读后写（write after read，WAR）依赖。RAW (Flow Dependency)——真正的数据依赖性
WAR (Anti Dependency)
WAW (Output Dependency)
其中，WAW、WAR是由于寄存器数量有限，要不断地重用寄存器名而造成的依赖性，实际上他们是对寄存器名的依赖，而非寄存器值的依赖，因此通过寄存器重命名解决。寄存器重命名将在后续实现精确异常时介绍，这篇文章主要讲介绍RAW数据依赖性的解决。解决RAW依赖性的方法：检测并等待（stall）√检测并绕行数据（bypass/forward）√检测并在软件层面消除依赖性（software level: compiler，插入nop）检测并将其移动到独立的指令之后（指令重排序，乱序执行）预测需要的值，试探性地执行，最后检验其他如细粒度多线程，无需检测2.0 依赖性检测（互锁）检测流水线中指令间的依赖性，以保证正确执行。也分为软件层面、硬件层面的互锁。实际上，MIPS也可称作 microprocessor without interlocking pipeline stages，也就是说硬件层面不做互锁、软件层面做互锁。依赖性检测方法：计分板（Scoreboarding）给RegFile中的每个寄存器 设置一个有效位Valid bit。如果一个指令要写寄存器，则将其有效位置0；在指令译码阶段，检测是否这条指令的 源、目的寄存器的有效位都为1，如果为1：无依赖性，如果为0：有依赖性、停滞流水线。 优点是简单，缺点是会因为所有类型的依赖性而停滞。组合逻辑检测设置特定的组合逻辑来检测 指令后面的阶段是否会写到当前正在译码出的寄存器中。 优点是不会在WAW、WAR依赖上停滞，缺点是逻辑更复杂、且随着流水线变深 逻辑很复杂。2.1 检测并等待等到指定数据被写入RegFile后，再从RegFile读操作数，会造成流水线停滞，很慢
流水线停滞（stall）的实现方法：使PC 或者 IF/ID锁存器 失能(disable)，确保停顿的指令 保持在原来的阶段插入nops指令2.2 数据绕行（data bypass）对于有数据依赖性的两条指令，后一条指令 只能等 前一条指令将结果写回RegFile，才能用写回的寄存器中的数据，这样会使流水线停滞、减小吞吐量、降低性能。可以通过 依赖性检测+数据绕过，一旦计算出前一条指令的结果，虽然还没到写回的阶段，可以提前把结果送给后一条指令。举例：
① 在执行阶段，完成了加法运算，此时已经得到了应该写回s0寄存器的值；由于第二条指令的源寄存器 是 第一条指令的目的寄存器，存在RAW依赖性，如果等到写回后再执行第二条指令，效率很低；因此直接将第一条指令执行后的运算结果，提供给第二条指令的执行阶段，就能提高效率② 同理，在还没写回前，将运算结果先提供给后续的指令 作为源操作数③ 利用写回在前半周期、取操作数在后半周期（满足设计条件自动实现，可以看做无依赖性）对应到硬件实现：
Hazard Unit 用来检测依赖性（检测方法如score boarding），检测出指令间的依赖性后，产生控制信号ForwardAE、ForwardBE，用来控制两个MUX，00表示无数据依赖性，直接使用对应的源寄存器值即可（对应举例中的③）01表示有数据依赖性，从访存后取结果 替代源寄存器的值（对应举例中的①）10表示有数据依赖性，从执行后的锁存器中取结果 替代源寄存器的值 （对应举例中的②）数据bypass 一般发生在 访存 或 写回 阶段，如果某个阶段要写目的寄存器、并且目的寄存器和后面的源寄存器冲突，就使用数据bypass。如果访存和写回阶段都和目的寄存器冲突，那么优先使用访存阶段的结果，因为它的值时最新执行出来的。数据绕行的特例——lw指令lw指令在访存阶段后才能得到执行结果，因此下一条依赖性指令必须stall一个周期，才能进行数据绕行。
硬件实现：从Hazard Unit引出StallD和StallF，迫使译码和取指阶段的寄存器保持它们原有的值从Hazard Unit引出FlushE，清除执行阶段寄存器的内容，插入一个气泡（理解为此时用不到EX阶段的硬件资源）
3. 控制依赖性控制依赖性，即对 程序计数器PC 依赖性。由于PC中存放着下一条指令的地址，因此所有的指令都和前一条指令有控制依赖性：如果下一条指令不是控制跳转指令，因为我们知道指令长度，因此可以很容易地 算出下一条顺序指令的PC如果下一条指令是控制跳转指令，例如，beq（branch equal）知道第四个阶段才知道是否要跳转，也就是分支指令的下一条指令的取指 是先于 分支指令被解析的。一旦分支预测错误，那么从分支指令往后的指令都会被冲刷。
第一条指令在执行后，发现预测错误，需要跳转，于是进行流水线冲刷，这样就浪费了三个周期。解决方法：等分支指令执行完成，再执行后续的指令提前解析分支（Early Branch Resolution）做分支预测，并提高分支预测的准确性3.1 提前解析分支在译码阶段就提前判断。例如beq指令，提前判断两个源操作数是否一样：
这样在第二个阶段就完成了分支判断，在第三个阶段开始下一条指令，最多浪费一个周期：
优点：减小分支预测失误惩罚，减小CPI（cycle per instruction）缺点：会增加每个时钟周期的时间，频率降低额外的硬件开销，这种特定的硬件不会别的指令用到最终的MIPS五级流水线处理器
包括数据依赖性检测、数据绕行、停滞、提前分支解析的逻辑。
1. 为什么要引入流水线？
对于一条指令，我们可以将其执行划分为以下五个步骤：
取指（IF，Instruction Fetch）
译码（ID，Instruction Decode）
执行（EX，Execute）
访存（MEM，Memory Access）
写回（WB，Write Back）
一个时钟周期执行上述步骤中的一个，那么理论上执行一条指令需要5个时钟周期，即CPI（Cycles Per Instruction）为5。
这种处理器叫作多周期处理器，其本质是状态机，不足在于并发性不足：在不同的指令处理周期中，有一些硬件资源是空闲的，例如：当指令在ID或EX时，IF资源是空闲的；在访存时，大多数数据路径都是空闲的。
因此引入流水线，利用空闲的硬件资源来提升并发性，获得更高的指令吞吐量。
2. 流水线
2.1 基本思想
把指令处理周期分成不同的处理阶段，确保在每个阶段有足够的硬件资源来处理一条指令，同一时间每个阶段在处理不同的指令。
如下图，当达到稳定状态后，以后的每个时钟周期都能完成一条指令，即CPI=1，吞吐量提升到原来的5倍。
2.2 理想与实际的流水线
2.3 流水线级数与吞吐量流水线在实现时，用寄存器将每个阶段隔开，当时钟周期到来时，将前一阶段的处理结果保存在寄存器，并输出给下一个阶段。在没有流水线情况下，延时为T，最后一级寄存器延时为S，则BW=1/(T+S)。（BW即bandwidth）
对于k级流水线，均匀划分的情况下，每一级之间用寄存器隔开。每一级延时为T/k，寄存器延时为S，则BW_{k-stage}=1/(T/k+S)。虽然增加了吞吐量，但是每一级之间加入寄存器，增大了硬件消耗，并且这些需要传给下一级寄存器中的数据可能是非常庞大的。
高流水线级数的处理器是追求更高的主频，以获取更高的吞吐率和性能。低流水线级数的处理器是极低的功耗，提高能效比。2.4 流水线中的控制信号对于一条给定的指令，其控制信号和单周期控制信号一样，只是控制信号是在不同的周期才被需要，两种思路：和单周期处理器一样，由指令一下子译码出全部控制信号，通过寄存器逐级向后传播至需要的阶段使用
把指令字向后传播，在相应的阶段 译码出 需要的控制信号实际上，现在的处理器往往采用两者结合的方式。2.5 流水线设计中的问题平衡每个阶段的工作量，尽可能均匀划分使流水线在一些因素扰乱的情况下，尽可能 正确、充满、不断地流动，减小停滞（stall）解决指令间依赖性——数据依赖性、控制依赖性解决资源争用解决多周期操作的长延时问题处理异常、中断不断提高吞吐量，减小停滞
这篇文章主要将之前的流水线更加一般化，引入多周期指令的执行，并分析多周期指令执行时存在的问题，如何在含多周期操作的流水线中实现精确异常，给出ROB、HB、FF、Checkpoint这几种解决方法，本文主要详细介绍了最常用的ROB，ROB不仅便于实现精确异常，还能够通过寄存器重命名解决上一篇文章中提到的WAR、WAW依赖性，此外还为下一篇文章中要介绍的乱序执行打下基础。1. 多周期指令的执行在执行阶段，不同的指令会花费不同的执行周期数，对应地在EX阶段有多种功能单元（Function Unit，FU），它们需要花费不同的时间。
例如，整数加法与除法程序：
但这样的问题在于，违背了冯诺依曼架构，指令的完成并不是按顺序的，不符合ISA顺序执行的语义！！！除非在DIV执行完成前，后面执行的指令都是与其独立的。也正是利用这一点，可以合理调整指令执行顺序，乱序执行。并且如果除法指令在执行时发生了异常，那么很难找到除法指令对应的精确PC。2. 异常与中断异常：程序执行的内部问题（eg：除数为0）中断：在程序执行时，需要处理的外部事件（eg：键盘输入）异常和中断都需要：在当前运行处停止保存当前状态值处理异常/中断（在handler中处理）返回原程序继续运行（如果需要的话）3. 精确异常/中断当要处理异常/中断时，体系结构状态应该是精确的。精确指，能够精确地知道，只执行完异常指令后的RegFile、PC、Memory。需要满足：所有之前的指令全部交付之后的指令不能交付这里的交付/退休（commit/retire）指，完成执行并更新体系结构状态。3.1 为什么需要精确异常？保持冯诺依曼模型顺序执行的语义帮助软件调试使能够更容易地从异常中恢复使能够更容易地重新开始运行程序使能够陷入（trap）软件（如：软件实现的操作码）3.2 在流水线中检查、处理异常当最老的、准备退休的 指令被检测出会造成异常，控制逻辑将：确保体系结构状态是精确的（RegFile、IP、Memory）冲刷流水线中所有年轻的指令保存ISA规定的IP和寄存器重定位取指引擎到异常handler4. 多周期指令的精确异常处理解决办法：重排序缓冲（Reorder Buffer, ROB）历史缓冲（History Buffer）未来缓冲（Future Buffer）检查点（Checkpointing）下面主要介绍ROB：4.1 Reorder BufferROB解决流水线执行多周期指令问题的主要思想是：允许指令乱序执行完成，在指令执行完成后先将它们的结果先写到ROB，但是需要在结果对体系结构状态有效之前，对它们做重排序，在指令退休时将结果写回RegFile。
ROB中存储着所有被译码、还没退休的指令信息：当指令译码时，在ROB中按顺序保留下一个entry当指令完成时，把结果写入ROB对应的entry当最老的指令没有异常地完成执行，将其结果写入RegFile或内存4.2 ROB EntryROB的一个entry为：（ROB缓存中的一行）
V：用于指示当前存储空间是否有效（设想一条指令已经退休了，则V可设为无效）DestRegID：目标寄存器的IDDestRegVal：待存入目标寄存器的值StoreAddr：目标存储器地址StoreData：待存入目标存储器的值PC：这条指令对应的PCValid bits：需要有效位来确定指令是否已经执行完成Exception：是否发生异常的标志位（对于整体的ROB有oldest、youngest指针）其中信息用于实现以下操作：将ROB中的指令变回原来的顺序如果指令可以没有异常地退出，用指令的执行结果 更新体系结构状态如果一条指令在退休前出现异常/中断，精确处理异常/中断4.3 ROB用到 独立指令的流水线中在执行阶段后先将结果写到ROB，在指令退休时将结果写入RegFile。这样就符合冯诺依曼结构的顺序执行语义，并且方便精确异常的实现。
4.4 ROB用到 非独立指令的流水线中后续指令需要之前执行完、但还没退休的指令的执行结果，这一结果可能存在ROB。可以通过停滞流水线，或从ROB中读取值来实现，显然后者是一种更优的选择。实际上，寄存器结果可能在 RegFile、ROB、bypass paths中：
如果指令尚未执行完，则等指令执行完后、尚未写回ROB时，通过bypass paths获得value如果指令执行完（已经写入ROB）、尚未退休（尚未写回RegFile），通过ROB获取value如果指令已退休（写回RegFile），通过RegFile获取值。4.5 ROB的访问ROB的直接访问：ROB表设置的有oldest和youngest指针，分别指向最老的、还没退休的指令 和 最年轻的、刚译完码的指令。oldest到youngest所指的指令，是按照程序顺序排列的，可以据此访问ROB对应的Entry。ROB的间接访问：给RegFile中的每个寄存器设置 有效位、ROB ID、寄存器值。采用间接访问的方法，首先访问RegFile，检测目标寄存器是否是有效的，如果无效，那么RegFile中存储着对应的ROB ID，于是访问对应的ROB Entry即可。
4.6 重点：用ROB给寄存器重命名之前讲到WAR（先读后写）、WAW（先写后写）不是真正的数据依赖性，因为同一个寄存器中的值前后没有关系，它们之所以存在就是因为 寄存器空间有限，ID名称有限。实际上，WAR、WAW只是覆盖原来的值，与原来的值无关。寄存器ID通过ROB entry ID重命名，重命名后ROB Entry ID就可以用来表示寄存器了，ROB中将存放着寄存器的值。因此可以解决WAR、WAW依赖性。4.7 顺序流水线与ROB流水线阶段：Fetch (F)Decode (D)：访问RegFile/ROB，在ROB中分配entry，检查指令是否可执行，如果可以则派遣（dispatch）指令Execute (E)：指令可以乱序完成执行Completion (R)：将结果写回ROBRetirement (W)：检查是否有异常，没有则写回体系结构寄存器/内存，有则冲刷流水线、从异常handler开始执行实现顺序派遣、乱序完成、顺序退休的流水线：
4.8 ROB的tradeoffs优点：容易实现精确异常、可以消除WAR、WAW依赖性缺点：需要访问ROB才能获取还没被写到RegFile的值，增加了延迟与复杂性5. 补充介绍其他几种实现精确异常的方法：5.1 History Buffer（HB）基本思想：当指令完成时更新RegFile，但是在异常发生时撤销更新当指令译码时，保存一个HB entry当指令完成时，将这个寄存器原来的值写到对应的HB中当指令是最老的、且无异常/中断，这条指令对应的HB entry置为无效当指令是最老的、且有异常需要被处理时，在HB中的有效的值将写回体系结构寄存器。
优点：RegFile包括指令执行后的最新结果。缺点：需要读取目标寄存器原来的值5.2 Future File(FF) + ROB基本思想：存两个RegFile体系结构RegFile：为了精确异常，按照程序顺序更新体系结构RegFile未来的RegFile：一旦指令完成就更新未来RegFile
优点：无需从ROB中读取最新执行出的结果缺点：多个RegFile，需要在异常发生时，将体系结构RegFile复制到未来RegFile5.3 Checkpoint流水线问题——分支预测错误在流水线中，分支预测错误 就类似于一种 异常，分支预测错误的恢复 类似于处理异常。分支预测错误比异常更加常见，因此需要快速恢复状态，来减小预测错误带来的性能降低。分支预测错误状态恢复 的对比ROB：冲刷流水线中比分支指令年轻的指令，完成ROB中的所有指令HB：冲刷流水线中比分支指令年轻的指令，撤销分支之后的所有指令，从历史缓冲区的尾部倒回到分支，将旧的值逐一恢复到RegFile中FF：等待直到分支指令是最老的指令，将体系结构RegFile复制给未来RegFile，冲刷整个流水线更优的解决方案——Checkpoint在分支指令被解码时，记录前端寄存器状态为检查点，用比分支更早的指令结果更新检查点状态，一旦指令错误预测，恢复分支相关的检查点在分支指令解码时：复制一份future file，并将其与分支关联在指令产生一个寄存器结果时：所有更年轻的指令的future file checkpoints更新为新的值在检测出分支预测错误时：当检测出分支预测错误时，恢复future file checkpoint；冲刷比分支年轻的指令；释放比分支指令年轻的检查点优点：checkpoint一恢复，马上就能得到正确的前端寄存器状态 --> 低状态恢复延迟缺点：存储开销，管理checkpoints的复杂性
上一篇文章为了在流水线中实现多周期操作、精确判断异常位置，介绍了顺序派遣、乱序完成、顺序退休的流水线。这篇文章将介绍顺序派遣带来的问题，给出对于含有多周期操作流水线的更优执行方式——乱序执行，实现乱序派遣、乱序完成、顺序写回的流水线，逐周期地介绍经典的Tomasulo算法是如何实现乱序执行的，最后补充介绍乱序执行时load和store指令产生的内存依赖性。
1. 顺序执行的问题
上篇文章介绍了含多周期指令的流水线：
实际上，在ID和IE阶段之间，还有一步称为：Dispatch（派遣），即：将译码后的指令派遣给相应的功能单元，顺序执行即顺序派遣后执行指令。
但是，顺序派遣的缺点在于：由于存在RAW依赖性（真依赖性），当前指令的停顿，会使后面指的派遣也停顿，尤其是如果前面的指令是延迟很长的指令，流水线停顿很久，大大降低性能。
例如：
由于ADD指令的R3和前面的指令存在RAW依赖性，不得不等到前面的指令执行完才能继续下面的指令，但是前面的IMUL、LD都是延迟可变的指令（运行时才知道延迟），因此直到IMUL、LD的执行出结果，整个流水线是停滞的。
为了解决顺序派遣带来的长延迟问题，可以采用的方案有：
乱序执行（硬件动态调度）
编译时指令调度（软件静态调度）
预测值地试探性执行
其他如细粒度多线程
本文主要介绍乱序执行解决派遣延迟问题。
2. 乱序执行
基本思想：把依赖性指令移到独立指令后。
具体来说，如果指令B与之前执行的指令A存在依赖性，那么将指令B放入保留站（Reservation Stations, RS），让后面的独立指令先执行，直到A指令执行完成、B指令获得源数据，接下来派遣B指令。
实际上指令的派遣是数据流（dataflow）顺序的，也就是派遣源数据准备好的指令。
2.1 顺序派遣 vs. 乱序派遣
（1）顺序派遣+精确异常——16周期
由于第二条指令依赖于前面的指令，使后续指令全部停滞
（2）顺序派遣+精确异常——12周期，更优
虽然第二条指令是依赖性指令，它本身需要等待到它的源值都准备好时才能派遣进入E阶段；但是后续的独立指令源数据已经准备好了，可以超前于第二条指令执行。
2.2 乱序执行的实现
1）寄存器重命名：用tag给寄存器重命名
2）缓存指令：把指令插入保留站
3）追踪源值是否准备好：把tag广播，对比 源tag 和 广播的tag，如果一致，则说明源值准备好了
4）当所有的源值准备好了，派遣给对应的功能单元
2.3 双峰结构的现代流水线
第一个峰：保留站（RS，调度窗），用于乱序派遣指令，减小停滞、提高效率
第二个峰：重排序（ROB，指令窗），用于按照程序的顺序写回，保持冯诺依曼顺序执行程序的语义
3. Tomasulo算法
Tomasulo算法是动态调度（乱序执行）的一种经典算法。
3.1 实现步骤
在重命名前
如果保留站在重命名前还有空间，就把指令和重命名的操作数（源值/tag）插入到保留站
否则停滞
在保留站中的每条指令需要：
监视通用数据总线（CDB），监视指令源值对应的tag；
一旦观测到tag，把tag对应的源值存入这条指令对应的保留站Entry；
当两个操作数都可用时，就准备派遣指令
当指令准备好时，将其派遣到相应的功能单元（FU）
当指令在FU完成执行后
仲裁CDB
把tag及其对应的值放到CDB（广播tag）
RegFile是连接在CDB上的
RegFile也有一个tag，指示寄存器的最新写入者
如果RegFile的tag与广播的tag匹配，将广播值写入寄存器(并设置有效位)
回收重命名tag
3.2 举例
下面举例详细介绍乱序执行过程：
我们将模拟下面的程序，并假设ADD需要4个周期、MUL需要6个周期、只有一个乘法器和一个加法器。
我们需要用到寄存器别名表（Register Alias Table, RAT）、保留站表（RS）：
第1个周期：
正常完成取指。
第2个周期：
为MUL指令分配空间RS x：
检查RS是否还有空间：还有空间，为这条指令分配RS x
访问RAT，把指令源寄存器的值存入RS x
重命名目的寄存器R3为x，它的新的值将有RS x 产生
第3个周期：
（1）RS x 对应指令的MUL指令的两个源操作数都已经准备好，将其派遣到乘法单元，开始执行
（2）ADD指令译码，为其分配空间RS a，把R5重命名为a
第4个周期
（1）RS a对应的ADD指令需要等待，因为其源数据有无效的
（2）第二条ADD指令译码，为其分配空间RS b，把R7重命名为b
第5个周期
RS b 对应指令的ADD指令的两个源操作数都已经准备好，将其派遣到加法单元，开始执行
第6个周期
RS c 对应指令的ADD指令的两个源操作数都已经准备好，将其派遣到加法单元，开始执行
第7个周期
（1）RS y对应的MUL指令需要等待，因为其源数据有无效的
（2）R5原来被重命名为a，在这个周期被重命名为d，在RS中Source1仍为a
第8个周期
（1）RS x对应的乘法指令已经执行完成，广播tag x和MUL指令的执行结果，更新tag x对应的RAT、RS（值与有效位）
（2）RS b对应的加法指令已经执行完成，广播tag b和ADD指令的执行结果，更新tag b对应的RAT、RS（值与有效位）
（3）RS y对应的MUL指令需要等待，因为其源数据有无效的
第9~20个周期
在第9、12、15、19个周期时，广播tag和执行结果
最后补充两点：
（1）从上面的图看出并非是按顺序执行完指令的，因此需要ROB，使指令按顺序交付。
（2）这里的RS是分散的，对于每个FU有一个RS，实际上也可以做集中式的RS。
4. 思考
4.1 为什么乱序执行是有效的？
乱序执行通过并发执行独立操作，来容忍多周期操作的延迟。
回顾2.1小节，如果所有指令的执行只需要一个周期，那么顺序执行与乱序执行效果是一样的，因此乱序执行主要用来解决多周期指令使流水线停滞的问题。
4.2 如果有某条指令的执行需要1000个周期？
为了保证效率、使指令能够持续地译码，指令窗的大小也需要为1000。
指令窗指的是，机器中能存储的译码但还没交付的指令数目，它决定了乱序执行对延迟的最大容忍程度。
5. 补充介绍：乱序执行时的内存地址不确定——load和store
前面我们讨论的主要是寄存器间的依赖性，实际上内存之间也会存在依赖性，甚至处理起来更加困难，例如：
前一条store指令向内存中地址A写数据，后一条load指令需要把内存中地址A的数据读到寄存器中。
5.1 寄存器和内存的区别在哪里？
5.2 load和store问题出在哪里？
load/store需要访问的内存地址在指令执行前是不确定的
对内存地址重命名是十分困难的（不像寄存器数目那么少）
load和store指令之间的依赖性必须在它们执行后才能判断
乱序执行时，当一条load/store地址准备好时，可能比它older/younger的store/load的地址还未知
5.3 解决思路
（保守法）使load指令停滞，直到它前面的所有store都计算出了需要访问的地址
优点：简单，无需恢复
缺点：会因为独立的load指令停滞流水线
（激进法）总是假设后来的load需要访问的地址与之前的store指令是独立的
优点：简单，不会因为独立的load指令停滞流水线
缺点：在预测错误时，需要恢复/重执行
（智能法）预测load是否依赖于那些不知道地址的store
使用一个store等待列表，检测load的地址是否和之前的store地址匹配
优点：更准确
缺点：在预测错误时，仍需要恢复/重执行
5.4 性能提升
由下图，预测store-load依赖性对性能提升很有帮助，简单的预测器（基于历史信息）就可以实现大部分潜在性能的提升。
5.5 store和load指令间的数据bypass
尽管我们知道啦所有历史store指令访问的地址，我们仍然需要知道：
如何判断它是否和store指令有依赖性？
如果存在依赖性，如何把store的值bypass给load指令？
线代处理器主要采用LQ（load queue）和SQ（store queue）。
store-load数据旁路逻辑为：（store-to-load forwarding logic）
当store指令执行完成后，它把地址和值写到ROB或SQ中
当后续的load指令计算出地址后，它将：
用它的地址在SQ中搜索
用它的地址访问内存
从写入该地址的比它老的、最年轻的指令获取值（从ROB或内存二选一，预测器决定）
在第二篇文章中，讲到了控制依赖性，并且提到了后续指令总是和前面的指令存在控制依赖性的。实际上，在取指时，我们怎么知道一条指令是分支类型指令，就算当前取指指令是分支指令，我们如何获取下一条指令的PC呢？这篇文章将介绍分支预测的必要性、分支预测要预测的三大内容、静态与动态分支预测。
1. 控制依赖性与分支
1.1 分支类型
对于条件分支，它有跳转、不跳转两个选择，通过第二篇文章，我们知道对于条件分支可以做分支提前解析（如beq），但是对于众多的指令如果都采用提前分支解析，硬件开销非常大，因此这篇文章将介绍分支预测来决定其是否跳转。
1.2 如何处理控制依赖性
停顿流水线，知道计算出下一条指令的取指地址（慢，总是等待）
分支预测，猜测下一条指令的取指地址
分支延迟槽，使用延迟的分支，总是先执行分支的下一条指令，再跳转（损失，往往要插入nop）
多路径执行，两个可能的方向同时执行（硬件开销大）
其他如细粒度多线程
1.3 分支问题
控制流指令（分支指令）是很频繁出现的，大概占总指令数的15%~25%
在流水线中，分支指令的下一条指令地址，需要在N个周期后才能确定
N指分支的最小解析周期数
如果流水线的宽度为W（一次取W条指令），那么一次分支预测错误会造成N×W的指令槽损失
1.4 分支预测准确率对性能的影响
假设N=20（流水线级数为20）、W=5（取指宽度为5），每5条指令有一条为分支指令，每 5 条指令以一个分支结束，我们来计算取指500条指令消耗的时间：
准确率100%
100 cycles
IPC = 500/100
准确率99%
100 + 20*1 = 120 cycles
IPC = 500/120，多取了20%的指令
准确率90%
100 + 20*10 = 300 cycles
IPC = 500/300，多取了200%的指令
准确率90%
100 + 20*40 = 900 cycles
IPC = 500/900，多取了800%的指令
由此可以看出提高分支预测的准确率，对提升性能（IPC，instruction per cycle）有很大的帮助。
2. 分支预测
基本思想：预测下一条指令的取指地址，使在下一个周期取指模块能够用上。
2.1 在取指阶段需要预测3个内容
取出的指令是否是一个分支指令
对于条件指令来说，还要预测分支跳转方向（跳or不跳）
如果分支跳转，需要预测分支跳转的目标地址
2.2 分支目标缓存（BTB）
在动态实例中，很多条件分支指令跳转的目标地址总是保持不变的，于是我们可以把前一条指令的目标地址保持下来，从这条指令的PC来访问它对应的跳转目标地址，这个存储空间就叫做分支目标缓存（Branch Target Buffer, BTB）。
如下图，根据当前指令的PC：
通过方向预测器，预测是否跳转
通过BTB查询是否有历史跳转记录、跳转的目标地址
如果预测为跳转、且在BTB中能查到历史跳转地址，则跳转到BTB所指定的跳转地址；否则不跳转，执行下一条指令，即NextPC=PC+指令长度。
使用BTB对2.1中问题的解决：
可以预测指令是否为分支，只要能在BTB查到当前PC对应的历史跳转情况，这条指令就是分支
不能预测跳转方向（跳or不跳）
可以预测指令的跳转地址，只要能在BTB查到当前PC对应的历史跳转情况，就预测这条指令的跳转地址为BTB中的跳转记录
BTB不能预测跳转方向，那我们应该如何预测方向呢？
2.3 分支方向预测方法
编译时/静态预测：
总是预测为不跳
总是预测为跳
BTFN，向后则跳、向前不跳
基于已知资料（Profile based）
基于程序分析
运行时/动态预测：
根据上次的预测（single-bit）
基于2位计数器的预测（two-bit）
两级预测（全局+局部）
混合预测
更先进的算法（如：感知机）
3. 静态分支预测
3.1 总是不跳转
实现简单：无需BTB、跳转方向预测
准确率低：对于条件分支来说，准确率大概为30%~40%
3.2 总是跳转
无需跳转方向预测
对于条件分支来说，准确率大概为60~70%
比如循环分支，除了最后一次其他都跳转
3.3 BTFN (Backward taken, forward not taken)
如果目标地址比当前分支指令PC小，即往前跳，则跳转（如循环），
如果目标地址比当前分支指令PC大，即往后跳，则不跳。
4. 动态分支预测
基于运行时的动态执行信息，自适应地对分支预测情况做动态调整，但相应地硬件开销更大。
4.1 Last time predictor
以上一次的跳转情况作为这一次是否跳转的预测。
用状态机来描述跳转状态的更新情况：
硬件实现：
设置一个分支历史表BHT（Branch History Table），每个分支在BHT中分配1bit的空间，1代表跳转、0代表不跳，每个分支执行后更新BHT中对应的entry，当下一次遇到同一个分支时，查询BHB，以查询结果作为预测的跳转方向。
如下图，以PC[2+BHT_ENTRIES_WIDTH : 2] 作为index，并检查tag一致，来访问BHT对应的entry，取指时查询BHT预测跳转方向，执行后以正确的跳转情况更新BHT。
问题在于：预测器在跳与不跳之间切换地太快了，而分支可能是大多数都跳、或者大多数都不跳。
4.2 Two-Bit Counter Based Predictor（2BC）
更充分考虑过去的跳转情况，使BHT的每个entry为2 bit的，这样强预测方向就不会因为一个不一样的情况而改变。另外，也可以通过初始化BHT，为跳转情况提供先验信息。
用状态机来描述跳转状态的更新情况：
在实现上，也只是将BHT拓展成2 bit。
实际上，对于大多数程序，基于2位计数器的预测器在准确率上能达到85%~90%，但我们需要回忆1.4中分析的准确率与性能间的关系，进一步提高准确率对性能帮助很大。
另外，4.1和4.2中的预测器都属于 One-Level Branch Predictor：
4.3 Two-Level Predictor
前面两种预测期只是利用一条指令前几次的执行结果，而两级预测期的考虑为：
一条分支的结果和其他分支的结果有关系（全局分支相关性）
一条分支的结果和它前几次的执行结果有关（局部分支相关性）
两级的实现：
第一级：全局分支历史寄存器 GHR
存储着过去N个分支的跳转方向
第二级：每个分支的历史跳转表 PHT/BHT
存储着同一个分支前几次的跳转状态（常用2BC）
以更完全的角度看这个预测器：
提高全局预测期的准确性 —— Gshare predictor
基本思想：向全局预测器加入更多的上下文信息，考虑预测的是哪个分支的信息。
Gshare预测器是让GHR和分支对应PC的异或结果作为index，映射到PHT：
以更完全的角度看这个预测器：
提高局部预测器的准确性 —— Local History Register
基本思想：更加充分地考虑某一条指令的历史执行情况，以历史情况做映射查询。
每个分支指令PC映射到局部历史寄存器的一个entry，里面存储着这个分支的N为历史执行情况，再将这N位作为映射到PHT的index，查询预测结果：
以更完全的角度看这个预测器：
4.4 混合分支预测期
使用多个预测器，从中选一个最优预测结果。比如说：2BC和全局预测器的混合，根据指令只从中选一个结果作为预测结果。
优点是有更高的准确率，不同类型的分支可以用不同的预测器；
缺点是需要一个选择器来选择用那个预测器，另外访问延迟也更大了。
例如Alpha 21264中使用的预测器，自动选择局部预测或者全局预测：
4.5 感知机分支预测器
基本思想是，用一个感知机来学习分支历史寄存器与跳转结果之间的关系。
如下图，用 x1...xn 来表示历史跳转情况，自动学习感知机权重 w0...wn ，权重 wi 表示 xi 对结果的影响程度（大小、方向），将它们加权相加后，得到一个输出 y ，如果 y>0 则跳转，否则不跳。
实现框架如下图，根据分支PC选择对应的感知机，在取指阶段根据训练的权重判断当前是否跳转，在执行后根据分支真实的跳转情况更新感知机。
优点是增加了学习机制、支持考虑长历史分支情况，准确性更高；
缺点是硬件实现困难，而且一个感知机只能学到线性的函数。
4.6 TAGE
实际上，为了更高的准确率，不同的分支可能需要不同的历史长度。因此，TAGE（TAgged GEometric）预测器用不同长度的GHRs去映射PHTs，并且自适应地选择一个最合适的PHT。
TAGE预测器大大增加硬件开销，但同时也提升了预测准确性。
TAGE也是一个非常成功的想法，被用在很多现代处理器中。
存储是计算系统的重要组成之一，从应用角度，现在计算系统需要处理的数据是非常庞大的；从性能角度，提升内存的访问速度对流水线停顿等有着极大的改善；从能耗角度，内存访问消耗的能量大约是一次复杂加法的几百倍，大部分的性能能耗其实用在了移动数据上；从安全角度，研究存储系统可以提升安全性与可靠性。
这篇文章我们将介绍存储器基础，并介绍banking技术。
1. 存储组织
1.1 虚拟 -> 物理内存
从程序员的角度看内存是：
程序员看到的是虚拟内存，可以认定虚拟内存的容量是无限的。
实际上，物理内存的大小是十分有限的，通过系统软件与硬件协同，会将虚拟内存地址映射到物理内存，系统自动管理物理内存空间，且对程序员是不可见的。
虚拟内存的好处是，程序员无需关心内存大小，一个小小的物理空间可以对外表现为很大的内存，但是系统软件架构会更难设计。
不过现在我们先忽略虚拟到物理内存的映射，先只考虑物理内存，后续的文章会更详细地介绍虚拟内存。
1.2 存储单元
常用的存储单元有：
Register
在与非门构成的DFF中，主从锁存都需要４个与非门，一共就是８个与非，每个与非门需要４个mos管，也就是说一个DFF需要32个mos管，存储密度低
在同步电路中，通常使用DFF缓存数据，几乎不需要响应时间，速度最快，是整个存储系统层次的最顶层
通常用于做CPU内部寄存器，保存指令执行过程中临时存放的操作数和中间(或最终)的操作结果
SRAM（Static Random Access Memory）
用两个交叉耦合的反相器存储1bit数据（4个晶体管）
用2个晶体管实现访问
组成为：6个晶体管
贵、快、存储密度较低
DRAM（Dynamic Random Access Memory）
用电容的充电情况表示存储的数据，如果是充满电的则存储的是1，反之存的为0
通过对电容充放电，实现写数据
从DRAM读数据是破坏性的，需要刷新
组成为：1个电容+1个晶体管
慢、便宜、存储密度较高
1.3 内存阵列
一个有N位地址线、M位数据的内存，有 2N 行、M列数据，内存容量为 2N×M ：
一个4*3的内存阵列如下图，根据地址译码，驱动相应行，读出这一行存储的数据：
其中的存储单元常采用DRAM、SRAM：
2. 搭建更大容量的内存
大容量的内存需要更多的存储单元，但是存储器越大，也意味着访问越慢，那么如何做到大内存、且访问不是特别慢呢？
一个思路是，把内存分成更小的阵列，并将它们互连到输入/输出总线上。
2.1 Banking
问题：一个单片的大内存阵列访问耗时很长，并且不能并行进行多个访问
目标：减小内存阵列访问的延迟，并且使能够并行访问内存
基本思想：把一个大阵列分成多个banks，使它们在同一个周期/连续周期内能够独立地访问
例如，将内存分成16个banks，这样就可以在每个周期完成一个bank的访问，也可以一次访问N个banks（要访问的数据在不同的bank中）：
广义的内存结构为：
2.2 DRAM子系统
自上而下地看DRAM内存系统：
Channel DIMM (Dual in-line memory module):
DIMM Rank:
