Skip to content

计算机体系结构 - lab5 Scoreboard

Abstract

介绍一下实验中 Scoreboard 设计的思想，包括一些运行的原则和对各种 hazard 的处理。在一些具体的细节上均按照实验给予的框架进行解释。包括功能单元的安排和表的设计等，详情请看 实验指导。

基本原则

在 Scoreboard 算法中，我们主要维护的是两张表，FUS (1) 和 RRS(2)。我们用 issue(3)一词来指代我们将取到的指令放入 FUS 和 RRS 的过程

  1. Functional Unit Status，记录了正在每个功能单元上运行或等待运行的指令的状态
  2. Register Result Status，记录了每个寄存器正在被 FUS 中哪个单元作为目的寄存器，或者不被任何单元作为目的寄存器
  3. 发射

以下是一些算法执行的基本原则：

  • 我们不会将错误取址(1)的指令发射
  • 从指令被发射的那一个周期到执行结束的那一个周期，指令都会存在于上述两张表中
  • 在本 lab 的设计实现中，当前 IS 指令被阻塞会导致后续指令也被阻塞，直至当前 IS 指令被成功发射或者被 flush
  • 在 IF 阶段我们取得一条指令，该指令下一周期会进入 IS 阶段被决定发射或是阻塞
  1. 错误取址就是指跳转的过程中取得的其实不应被执行的指令

发射原则(IS)

我们通过以下两条规则来在一般情况下决定一条指令是否可以被发射：

  • 如果当前 IS 指令的目的寄存器同时也是表中某条指令的目的寄存器，那么阻塞该指令的发射直到不再存在冲突
  • 如果当前 IS 指令需要使用的运行单元已经被表中的指令占据，那么阻塞该指令直到不在存在该冲突

以上两个要求可以通过检测

  • RRS 中目的寄存器是否为空
  • FUS 中运行单元是否 busy

来决定。

可以看出上述两条原则是无论如何要被满足的，否则的话

  • RRS 对应状态会被新发射的指令覆盖
  • FUS 中的指令会被新发射的指令覆盖

以上就是关于发射的一般原则，但是为了满足只有正确取址的指令才会被发射的原则，我们需要一些额外的检测，这些检测主要跟跳转指令有关，一般来说：

  • 如果当前 FUS 中没有跳转指令
    • 无阻塞
  • 如果当前 FUS 中有跳转指令
    • 如果该跳转指令还未 done
      • 目前 IS 和 IF 阶段指令正确性未知，阻塞其发射
    • 如果跳转指令 done 并且
      • 不需要跳转
        • 当前 IS 和 IF 中顺序取址的是对的指令，不再阻塞
      • 需要跳转
        • 当前 IS 和 IF 中顺序取址的是错的，刷新错误 IF 和 IS，下一周期 IF 中会取上正确的指令

如果一条指令通过了跳转的发射检测和一般的发射检测，那么就可以发射了。并且我们应当注意到一般原则的第一条就阻止了 WAW hazard 的发生

执行原则(EX)

所有刚进入 FUS 的指令都要等待源寄存器均就位(1)，而后可以发送信号和数据给功能单元开始执行。

  1. 这里的就位就是 FUS 中的 Ready 位均置 1

具体而言，FUS 的 Ready 位的设置遵循以下原则：

  • 指令被发射进入 FUS 时，表内已有的指令都必然是先于该指令的(1)，如果这些先前的指令需要写新指令的源寄存器，那么我们就应该等，初始 Ready 置 0
  • 若无先前指令要写当前的源寄存器，其初始 Ready 置 1
  • 一条指令完写后，要回来把表中所有在他的目的寄存器上等待的指令的对应 Ready 位置 1，以通知这些指令新数据已就位(2)
  1. 发射上先于一定意味着指令顺序上先于，因为在本实验中只有一个发射口，前面的指令发射完了才能轮到后面的
  2. 由于发射的第一条一般原则，对某一目标寄存器写的指令同时在表中只会有一条

一条指令把数据和使能信号给功能单元后，执行开始，就只需要等执行结束而不再要读寄存器了，此时我们需要把 Ready 全置 0 并且清零 Q 位来表明这一点(1)。另外等待数据就位的过程也是在解决 RAW hazard

  1. 来表明我不再需要渡这个寄存器了，你们想要写的话可以写了，不必阻塞

Tip

由于一条指令写完后，回头进行通知可能同时令多条指令就位。我们要多个周期依次把这些指令的 Ready 位清 0 并开始执行。为了做到这一点，我们需要加上 else 保证一周期只有一条指令开始执行，并且我们的设计需要保证未被执行的指令保持当前状态到下一周期

写回原则(WB)

像执行原则中提到的一样，我们可能有多个功能单元在同一周期同时结束，我们需要多个周期让他们逐一写回。除此以外，我们还需要解决 WAR hazard，具体来说，如果我们发现某个 FUS 中的指令的 Ready 位仍然是 1，那么就意味着：

  • 该寄存器当前值就是它需要拿去运算的源寄存器的值
  • 该指令还未读取该源寄存器值并拿给功能单元执行(1)
  1. 这就解释了为什么执行原则中把数据读走执行后要把 Ready 置 0 了，这是告诉那些等 WAR 的指令说，我已经读完了，现在你把新数据覆盖上去也没关系

所以显然这些寄存器我们现在是不能写的，否则 FUS 中的寄存器就没法拿正确的值去执行了

总的来说，我们需要以下的检测：

  • 对于所有 FUS 中的指令，如果其源寄存器跟我的目标寄存器不一样，那么不构成 WAR hazard
  • 对于所有 FUS 中的指令，如果其源寄存器跟我的目标寄存器一样，那么如果其 Ready 位为 0，那么不构成 WAR hazard
  • 一旦存在某一 FUS 中的指令其源寄存器跟我的目标寄存器一样，且其 Ready 位为 1，那么构成 WAR hazard，阻塞写回
证明 WAR 存在 \(\iff\) FUS 中存在源寄存器跟写回指令目的寄存器一样且 Ready 位为 1 的指令

(\(\Rightarrow\)) WAR 存在，也就是说 C 指令要写回的话会把 B 指令还未读取的源寄存器的值给覆盖掉，那么 C 的目的寄存器一定和 B 的某一源寄存器相等，前半部分证毕。

因为发射的第一条一般原则，C 一定是 FUS 中唯一一条以此寄存器为目的寄存器的。那么 B 的 Ready 位一定为 1 而不是 0，因为想要 B 的 Ready 位为 0，我们需要：

  • B 之前存在 A 指令要写同一目的寄存器
  • A 还没写

但是此时 C 已经发射了，这意味着 A 一定写完了，否则 AC 的目的寄存器相同 C 是发不出来的。所以 B 的 Ready 位一定位为 1

(\(\Leftarrow\)) Trivial，可以参考写回原则中的表述

Comments