流水线

命令执行方式

シングルサイクル

  • CPI = 1
  • Clock按照以执行最慢的命令为准

可変長クロックサイクル

  • CPI = 1
  • Clock自动根据命令长度缩放
  • 电路复杂，难以实现

マルチサイクル

  • CPU時間 = 实行命令数 CPI 钟周期时间
  • 一条命令在多个时钟周期内网

流水线

每个命令可以大体分为五个步骤：

  • IF: 取命令(命令フェッチ)
  • ID: 译码，解析指令，生成控制信号(デコード)
  • EX：执行
  • MEM：访问内存
  • WB：写回寄存器

上述五个步骤使用的资源互不干扰，为了让CPU的所有步骤同时使用，我们可以使用流水线：

1 2 3 4 5 6 7 8
1 IF ID EX MA WB
2 IF ID EX MA WB
3 IF ID EX MA WB
4 IF ID EX MA WB

$$ 理想CPI =
\frac{总CLOCK}{总命令} = \frac{n+4 } {n} $$

$$ \lim\limits {n \to \infty} CPI = 1 $$

冒泡 / Bubble / バブル

流水线有时可能需要暂停等待。

这时候会产生冒泡(空过clock)。

由于CPU同时只能执行IF、ID、EX、MAM、WB中的一条命令，因此当某条命令产生了冒泡后，后续命令也需要添加冒泡停顿，使得bubble

1 2 3 4 5 6 7 8 9
1 IF ID EX MA WB
2 IF ID EX MA WB
3 IF ID EX MA WB
4 IF ID EX MA WB

ストール

オーバヘッド / Overhead

在流水线中，我们必须要使得每一步用时相同。也就是clock相同

冒险 / ハザード

流水线在某一个时间不能正常工作，叫做ハザード。

结构冒险 / 构造ハザード

出现原因

上述假设，一条命令的五个步骤互相完全独立，不会抢占资源。

但两条命令的不同步骤，可能会使用同一个资源：

比如一条命令的ID读取的寄存器正好被另一条命令的WB读取时。

解决构造ハザード

由于WB和ID命令都是对寄存器进行的操作，而对寄存器的操作非常快，WB和ID命令加起来的运行时间也比一个时钟周期长，因此可以安排WB在一个时钟周期的前半段，ID在一个时钟周期的后半段

控制冒险

当执行分歧命令，直到执行完毕之前，无法得知下一条执行的将是什么命令。

解决控制冒险
  • 添加气泡：
时间 1 2 3 4 5 6 7 8 9
beq $1, $2, label IF ID EX MA WB
and $4, $2, $5 IF ID EX MA WB

注：如果命令和数据存储在同一个MEMARY中，有可能出现MAM操作和IF操作的资源抢占，因此需要在MAM后面执行下一条操作。

  • 延迟分歧：

    • 将分歧延迟，先执行数条与分歧无关的命令，直到分歧执行完毕后执行分歧后的命令。
    • 思想很好，但是实现困难，难以判定哪些是分歧无关的命令

  • 分歧预测: 预测分歧是否发生，先执行某一条路线，如果预测正确，则顺序，如果预测错误，则需要回滚，再执行另一个预测。

    • 静的预测: 永远只预测一种结果
      • 在循环中，可能会出现大部分判定都支持调转的情况，在这种情况下很可能全部预测错误，造成大量浪费。
    • 饱和计数器 / 饱和カウンター
      • 每次产生分歧则升一级，未产生分歧则降一级，最高四级。
      • 是第0级则预测不分歧，其他情况预测分歧。
      • 分支指令必须连续选择某条分支两次，才能从强状态翻转，从而改变了预测的分支。
    • 2级自适应预测器 / 2レベル适应型分歧预测：
      • 对于不同类型的分支预测不同结果。

数据冒险

考虑下列情况：

1
2
3
sub $2, $1, $3
and $4, $2, $5
and $8, $7, $8

注：上述情况ID和WB做了冒险防止。

简单的解决方法：冒泡。

时间 1 2 3 4 5 6 7 8 9 10
sub $2, $1, $3 IF ID EX MA WB
and $4, $2, $5 IF - - - ID EX MA WB
and $8, $7, $8 IF - - - ID EX MA WB
寄存器直通 / 数据前递（register forwarding）

逻辑电路实现：

  • 相邻：EX->EX
    • 上一条命令的EX和这一条命令的ID在同一个CLOCK执行完毕。
    • 上一条命令的EX里有真实的数据，ID取到的是过期的数据。
    • 将上条命令的EX结果也传入这条命令的EX，加一个选择电路选择正确的值。
  • 隔一行: MAM->EX

不能完美解决load命令的冲突问题

乱序执行 / Out Of Order
  • 数据依存：强顺序相关
    • フロー依存： RAW
    • 逆依存： WAR
    • 出力依存： WAW
W R R
1 r1 r4 r7
2 r8 r5 1
3 r6 r6 r3
4 r4 r5 r6
5 r7 r8 r4

命令 x 与命令 x 关于 r 有 x 依存

例：

命令２と命令４はｒ６に関してフロー依存がある。

上述：

フロー依存：24，34，45，56
逆依存：14，51
出力依存：無し

寄存器重命名

扩展寄存器的空间

流水线为什么不分得特别细？

分歧预测会变多，从而产生延迟。