流水线中的相关

什么是相关?
流水线中的相关是指相邻或相近的两条指令因存在某种关联,后一条指令不能在原先指定的时钟周期开始执行

三种不同类型的相关

  • 结构相关:当指令在重叠执行过程中,硬件资源满足不了指令重叠执行的要求,发生资源冲突时将产生“结构相关”。
  • 数据相关:因一条指令需要用到前面指令的结果,而无法与产生结果的指令重叠执行时,就发生了数据相关。
  • 控制相关:当流水线遇到分支指令和其它会改变PC值的指令时就发生控制相关。

结构相关

我们可以发现指令1和指令3在第四周期时同时有访存需求,这就是一种常见的结构相关

解决办法:

  • 方法一 :Stall,向指令3之前插入“气泡”,即暂停指令3一个周期
  • 方法二:将指令Cache与数据Cache分离

数据相关

考虑下列指令在流水线中的执行情况

ADD    R1, R2,R3
SUB    R4, R1,R5
AND    R6, R1,R7
OR    R8, R1,R9
XOR    R10,R1,R11

对应的时空图

分析

  • SUB、AND指令在使用寄存器R1前,ADD指令还未对R1执行写回操作,所以此时得到的数据是错误数据,这就发生了数据相关。
  • XOR指令使用R1时,ADD指令已完成写回操作,正常执行
  • OR指令则比较复杂,因为在很多机器中,可以约定在时钟周期前半部分进行写操作,后半部分进行读操作,所以OR指令也可以正常实行

解决方法:

  • 使用Stall暂停技术
  • 使用定向/旁路技术

定向技术

主要思路:将计算结果从其产生的地方直接送到真正需要它的地方,就可以避免暂停

我们先来考虑两条指令A和B(A在B之前进入流水线)对寄存器读写顺序造成的数据相关

  • 写后读相关RAW(read after write)B在A未完成写之前读,会读入一个错误的数据,如上图ADD指令和SUB指令就属于RAW相关
  • 写后写相关WAW(write after write)B在A未完成写之前,尝试写入,从而导致写入顺序错误(MIPS指令中不会出现这种相关)
  • 读后写相关WAR(write after read)B在A读取某个源操作数之前写入错误的值,导致A读入值错误

上述相关均可通关定向技术解决

Load/Use类型相关

考虑以下指令

LW    R1,0(R2)
SUB    R4,R1,R5
AND    R6,R1,R7
OR    R8,R1,R9


我们可以看到如果仅仅只是插入一个暂停周期并不能使数据相关消除,对于Load/Use类型的指令我们有两种解决办法

  • 两个暂停周期
  • 一个暂停+定向技术

流水线调度

通过编译器优化我们可以消除很多数据相关

举例来说

数据相关总结

控制相关

首先我们要关注分支指令是如何实现的

  • 一旦分支转移成功,正确的地址要在Mem段的末尾才会被写入PC
  • 一旦ID段检测到分支指令,就暂停执行其后的指令,直到分支指令达到Mem段,确定新的PC为止
  • 分支转移成功就将导致MIPS流水线暂停3个周期

如何减少分支开销?

两个基本途径

  • 在流水线中尽早判断分支转移是否成功
    改进:对于分支指令中的BEQZ和BNEZ需要测试分支条件寄存器的操作,我们将其提前到ID段进行
  • 转移成功时,尽早计算出转移目标地址
    改进:为了尽早计算出连个PC值(分支成功和失败时的PC值),我们将其提前到ID段(为此要给ID段增设一个加法器)

再优化

  • 预测分支失败法
    流水线继续照常流动,如果分支转移成功,将分支指令后的指令转换为空操作,并从分支目标处开始取指令执行;否则照常执行

  • 预测分支成功法
    始终假设分支成功,直接从分支目标处取指令执行
  • “延迟分支“法
    分支开销为n的分支指令后紧跟有n个延迟槽,流水线遇到分支指令时,按正常方式处理,顺带执行延迟槽中的指令,从而减少分支开销。

延迟分支法详解

什么是延迟槽?

即使分支开销已经优化到最小,但开销也不可能为0。我们可以借鉴处理数据相关时的指令调度策略,把一些可能会用到的或者一定会用到的指令放在分支指令之后,这样分支开销时间我们处理的也是有用的指令。分支开销有多大,延迟槽就有多长。

指令的调度策略也分为三种

调度策略对调度指令的要求结果
从前调度分支必须不依赖于被调度的指令总是可以有效提高流水线性能
从目标处调度如果分支转移失败,必须保证被调度的指令对程序的执行没有影响,可能需要复制被调度指令分支转移成功时,可以提高流水线性能。但由于复制指令,可能加大程序空间
从失败初调度如果分支转移成功,必须保证被调度的指令对程序的执行没有影响分支转移失败时,可以提高流水线性能

作废/取消分支

为了进一步降低流水线分支损失,当分支方向与预测方向不一致时,将延迟槽中的指令作废掉,否则正常执行。

分支处理性能

假设理想CPI=1,则加速比

$$ S = \frac{D}{1+C} $$

又因为

$$ C = f \times P_{分支} $$

固有

$$ S=\frac{D}{1+f \times P_{\text {分支 }}} $$

这里,D为流水线的深度,p分支为分支开销,C为分支引起的流水线暂停时钟周期数(每条指令的平均值),f为分支的出现频度。

Last modification:April 24th, 2020 at 05:53 pm
如果觉得我的文章对你有用,请随意赞赏