数据依赖RAW WAW WAR

本文是作者在学习过程中的理解，所以很可能存在不全面或者错误

本文参考了自己动手写CPU之第五阶段（1）——流水线数据相关问题和cpu乱序原理

CPU指令中的相关性包括数据相关性，结构（资源）相关性和控制相关性。

数据相关性：CPU基于流水线执行，在执行指令时，上一条指令没有执行完就要开始接下来指令的执行，如果当前指令中的操作数来源于上一条指令的执行结果，那么就会产生数据依赖。

资源相关性：CPU内的硬件资源是有限的。所谓资源相关，是指多条指令进入流水线后在同一机器周期内争用同一个功能部件所发生的冲突。

控制相关性：由于跳转指令引起指令跳转。CPU遇到跳转指令可能不跳转接着执行吓一跳指令；但如果跳转到其他的指令，PC值会由跳转指令执行结果而定，这会冲刷流水线。

这里只整理数据相关性内容。

---

数据依赖性主要有三种RAW（写后读依赖）、WAR（读后写依赖）、WAW（写后写依赖）。

RAW：Read After Write，假设指令j是在指令i后面执行的指令，RAW表示指令i将数据写入寄存器后，指令j才能从这个寄存器读取数据。如果指令j在指令i写入寄存器前尝试读出该寄存器的内容，将得到不正确的数据。

** WAR**：Write After Read，假设指令j是在指令i后面执行的指令，WAR表示指令i读出数据后，指令j才能写这个寄存器。如果指令j在指令i读出数据前就写该寄存器，将使得指令i读出的数据不正确。

 WAW：Write After Write，假设指令j是在指令i后面执行的指令，WAW表示指令i将数据写入寄存器后，指令j才能将数据写入这个寄存器。如果指令j在指令i之前写该寄存器，将使得该寄存器的值不是最新值。

顺序执行

对于5级流水线结构的CPU，取址、译码、执行、访存和写回。顺序执行的指令写寄存器实在写回阶段，后续的指令也是在写回阶段写寄存器，所以不存在WAW依赖。读寄存器实在译码阶段进行，而写寄存器实在写回阶段，所以不存在WAR依赖。只存在RAW依赖，这是因为读的数据是写操作执行完成写回寄存器操作后读的数据，必须等到前面的数据写回。

ADD r1,r2,r3
SUB r4,r5,r1     指令需要读取上一条指令的结果

流水线：
ADD       取指 译码 执行 访存 写回
SUB            取指 译码 执行 访存 写回

SUB指令在“译码”阶段读取r1寄存器的值，但这时ADD指令还没有写回。

解决RAW方法

1. 添加空的周期

   流水线：
   ADD       取指 译码  执行  访存  写回
   SUB            取指 empty empty 译码 执行 访存 写回

2. 编译器对指令进行调度

编译器将SUB指令之后的不与ADD、SUB两条指令存在相关性的指令添加到ADD和SUB这两条存在数据依赖的指令中间。这样执行效率不高。

 编译器调度后的指令：
ADD r1,r2,r3
指令1
指令2
SUB r4,r5,r1     指令需要读取上一条指令的结果

编译器调度之后的流水线：
ADD       取指 译码 执行 访存 写回
指令1          取指 译码 执行 访存 写回
指令2               取指 译码 执行 访存 写回
SUB                     取指 译码 执行 访存 写回

3. 数据前推（数据旁路缓冲器）

（假设在执行阶段就能得到计算结果）。通过旁路缓冲器将执行阶段的结果直接给到下一条指令的译码阶段。这样就不需要等到写回寄存器。这要效率高，但是需要额外的复杂逻辑。

流水线：
ADD       取指 译码 执行 访存 写回
SUB

---

乱序执行

由于访存、浮点运算等指令时间长，会阻塞流水线。乱序执行就是不必等前面的指令执行完就开始执行接下来的指令。乱序执行中的数据依赖三种都有：WAW,RAW,WAR

乱序执行采用了如下图所示的保留站（Reservation Station ）这种类似于接待室的设施。

解码单元解码后的指令不是直接送到流水线，而是根据各自的指令种类，将解码后的指令送往各自的保留站中保存下来。如果操作数位于寄存器中，就把操作数从寄存器中读出来，和指令一起放入保留站。相反，如果操作数还在由前面的指令进行计算，那么就把那条指令的识别信息保存下来。

然后，保留站把操作数齐备、可执行的指令依次送到流水线进行运算。即使指令位于前面，如果操作数没准备好，也不能开始执行，所以保留站中的指令执行顺序与程序不一致（乱序）。另外，保留站会监视执行流水线输出的结果，如果产生的结果正好是等待中的指令的操作数，就将其读入，这样操作数齐备后，等待中的指令就可以执行了。

此外，上图给每种指令都设置了保留站，而有的处理器用一个保留站控制所有流水线。

乱序执行中的反向依赖

LD r1，［a］; ←将内存的变量a 读入到寄存器r1（加载）

ADD r2，r1，r5; ←r1与r5相加，保存到r2

SUB r1，r5，r4; ←r5减去 r4，保存到 r1

LD指令需要较长时钟周期，ADD与LD有r1寄存器的依赖关系，所以ADD也被阻塞不能执行。而SUB指令中的r4,r5都已知，根据乱序执行，SUB指令先执行。而SUB指令的保存结果位置是ADD指令的操作数r1，这样就产生的了反向依赖（anti-dependency)。SUB指令先于ADD执行，那么ADD指令执行时的r1值就不是LD指令的结果，而是SUB执行后保存在r1的值，程序执行如下图：

寄存器重命名消除反向依赖

逻辑寄存器和物理寄存器 :
编译器或者汇编器生成的机器语言程序读写有限数量的指令集体系结构（ISA）寄存器。例如，Alpha ISA使用32个64位宽整数寄存器，32个64位宽浮点寄存器。这些体系结构寄存器，是程序可以直接访问的逻辑上的寄存器。如果程序员在调试器中把这个程序暂停，可以观察到这64个寄存器与一些状态寄存器当前存储的值。
一款特定的处理器，实现了这种处理器体系结构。例如Alpha 21264有80个整数寄存器、72个浮点寄存器，作为处理器内物理实现的寄存器。也就是说，Alpha 21264处理器有80个物理存在的位置存储整数运算的结果，72个位置存放浮点运算的结果。实际上，该款处理器有更多的物理存在的存储位置，但与寄存器重名关系不大。

重命名处理将程序中记载的寄存器编号（称为“逻辑寄存器”）对应到物理寄存器编号上。各指令写入结果的逻辑寄存器一定要分配到空闲的物理寄存器上。

LD p11，［a］; ←将内存的变量读入寄存器p11 （r1）

ADD p12，p11，r5; ←p11 （r1）与 r5相加，保存到p12 （r2）

SUB p13，r5，r4; ←r5减去 r4，保存到 p13 （r1）

如图3 所示，LD指令要将结果保存到r1 ，而实际上被重命名，结果保存到了物理寄存器p11。解码下一条 ADD指令时，对应表中记载了 r1 = p11 ，因此将使用 r1 的部分改变为使用p11。此外，存放 ADD指令结果的r2 寄存器对应到空闲物理寄存器p12。而SUB 指令的结果也要保存到r1 ，此时要将r1对应到空闲的物理寄存器p13 上。

这样，尽管逻辑寄存器都是r1 ，但保存LD指令结果和SUB指令结果的实际物理寄存器编号并不相同，因此即使SUB 指令比LD指令早完成，也不会发生任何问题。这种处理叫做寄存器重命名。

图3 重命名之后的情况

寄存器重命名原理

为了实现寄存器重命名，乱序执行的处理器要有物理寄存器池，以及逻辑寄存器和物理寄存器的对应表。在译码时给逻辑寄存器分配物理寄存器，并且记录到对应表中。在解码的时候也要查找对应表中的对应关系，将后续指令中使用的逻辑寄存器转换成对应的物理寄存器。并且在指令执行结束后要释放物理寄存器到空闲物理寄存器池中。