冲突

  • 结构冲突： 由于硬件资源争夺导致的冲突，例如同时两条指令产生访问请求，或者ICache和DCache同时对L2 Cache产生访问请求。
  • 数据冲突： 数据冲突分为写后读冲突(RAW)，写后写冲突(WAW)，读后写冲突(WAR)。写后读可以认为写在读之后
  • 控制冲突： 主要是分支指令导致的冲突

其中结构冲突和控制冲突无法避免，我们需要想办法消除数据冲突

WAR
ADD F2, F0, F1
SUB F3, F2, F4
其中F2存在读后写相关
RAW
ADD F2, F0, F1
SUB F1, F3, F4
其中F1存在写后读相关
WAW
ADD F2, F0, F1
SUB F2, F3, F4
其中F2存在写后写相关

其中写后读相关是无法避免的，在乱序执行中必须要等待写完成才可以读，在顺序处理器中使用前推解决。而写后读相关和写后写相关在顺序处理器中是不存在的，但是在乱序处理器中可能存在问题。

例如写后写相关，本来存储器中最终保存的是SUB的数据，但是现在保存的是ADD的数据。而读后写相关调换位置就变成了写后读相关。

Tomasulo算法

大致步骤：

  1. 流水线前端的指令信息保存在指令队列中
  2. 根据指令类型的不同发送给不同部件的保留站中，如果保留站满则不能发送。
  3. 发送到保留站时，需要进行寄存器重命名
  4. 运算后通过公共数据总线发送给保留站，寄存器状态队列，寄存器堆

保留站中字段信息：

  • busy： 当前保留站是否被使用
  • op: 操作类型
  • $v_j ， v_k$: 源操作数值
  • $q_j , q_k$: 源操作数编号，也就是rs，rt。如果不需要该操作数或者操作数准备完毕则设为0，否则设为register result status中的编号

寄存器结果状态表中的信息：

它表示当前寄存器结果的位置，可以为保留站编号或者是0(表示当前最新值在寄存器堆中)

指令存入保留站过程:

  1. 检查源操作数在寄存器结果状态表中的值，如果不为0表示当前值还等待计算，因此将$q_j , q_k$置为相应保留站编号。否则将$q_j ，q_k$置为0并且从寄存器堆中取出值放到$v_j , v_k$中
  2. 如果当前需要写入目的寄存器，则将当前分配的保留站编号写入寄存器结果状态表的rd位置。如果是load或store命令，则还需要判断写入地址是否相同，如果相同也要添加保留站编号(例如先读后写，如果不判断地址冲突，那么写命令可能先执行，读出来的就是未来的数据了)

例：

前面两条读指令结束后如图

第三条指令来的时候由于F2还在由上一条指令获取，因此此时qj嵌入load2(保留站编号)。因此此时mult1不能执行

sub同理，由于load2没有执行完毕,f2无法获得，需要暂存在保留站中

这一周期写入div指令，并且load2执行完毕，因此register result status表项释放，并且保留站中标号为load2的表项都释放并且填入对应值，此时sub可以执行

之后按照上面所述步骤执行下去

重排序缓冲器（ROB）

前面说的tomasulo算法特点是顺序发射，乱序执行，乱序提交。但是这种方式给精确异常带来了极大的挑战。精确异常也就是处理完异常后可以恢复原来的状态，即处理完当前指令异常后可以无障碍执行下一条指令。但是在乱序提交的情况下，下一条指令可能先于当前指令提交。为了解决这个问题，提出了ROB。

添加ROB的tomasulo算法特点是顺序发射，乱序执行，顺序提交。

每次从指令队列发送到保留站时同时在ROB中申请一个编号，此时寄存器结果状态表中存放的ROB的编号而不是保留站编号。

执行完毕后先将结果写入重排序缓冲器中，然后从队首开始将结果依次写入寄存器堆中。如果遇到分支预测错误或者精确异常，只需要清空他们后面的指令即可，也就是说如果在退休时遇到这两种情况清空ROB重新取指。如果遇到中断，则还需要获得当前最后一条未退休的指令地址，然后再清空ROB。

ROB字段：

  • busy： 是否使用
  • instruction: 指令
  • destination: 结果
  • value: 值

此外ROB还需要一个开始和结束指针，他是一个队列的结构