1

我正在学习计算机体系结构课程。我从另一所大学找到了这个网站，该网站有迄今为止对我有帮助的笔记和视频：CS6810，犹他大学。我正在处理该网站上发布的一些旧家庭作业，尤其是这个。我正在尝试理解流水线和相关概念，特别是停顿和分支延迟槽。

我现在正在查看那个旧家庭作业中的第一个问题，并且不确定如何解决这些问题。

问题如下：

考虑以下代码段，其中 30% 的时间使用分支，而 70% 的时间未使用分支。

R1 = R2 + R3

R4 = R5 + R6

R7 = R8 + R9

如果 R10 = 0，则分支到 linex

R11 = R12 + R13

R14 = R11 + R15

R16 = R14 + R17

...

线：R18 = R19 + R20

R21 = R18 + R22

R23 = R18 + R21

...

考虑一个 10 阶段的有序处理器，其中指令在第一阶段被提取，并且分支结果在三个阶段之后是已知的。在以下场景下估计处理器的 CPI（假设处理器中的所有停顿都与分支相关，并且分支占所有执行指令的 15%）：

  1. 在每个分支上，提取都会停止，直到知道分支结果为止。

  2. 每个分支都被预测为不被采用，如果分支被采用，错误获取的指令将被压缩。

  3. 处理器有两个延迟槽，分支后面的两条指令总是被取出并执行，并且

    3.1。您找不到任何说明来填补延迟槽。

    3.2. 您可以在分支到延迟槽之前移动两条指令。

    3.3. 您可以将标签“linex”之后的两条指令移动到延迟槽中。

    3.4. 您可以在分支（在原始代码中）之后立即将一条（注意：一条，而不是两条！）指令移动到延迟槽中。

我什至不确定如何开始看待这个问题。我已经阅读了该网站上的所有笔记并观看了视频，并阅读了 H&P 书中的部分内容，但仍然对这个问题感到困惑。如果有人有时间，我会很感激有人帮助我解决这个问题。我只需要知道如何开始概念化答案。

4

1 回答 1

4

在所描述的流水线中，条件分支的方向和目标直到第三个周期结束才可用，因此直到第四个周期开始才能（确定地）获取分支之后的正确下一条指令。

设计一

处理分支后指令地址的延迟可用性的一个明显方法是简单地等待。这就是设计 1 通过暂停两个周期所做的（这相当于获取两个不属于实际程序的空操作）。这意味着对于采用和未采用的路径都将浪费两个周期，就像编译器插入了两条无操作指令一样。

下面是流水线图（ST是停顿，NO是空操作，XX是取消指令，UU是无用指令，I1，I2，I3是分支前的三个指令[按原程序顺序在填充任何延迟槽之前]，BI 是分支指令，I5、I6 和 I7 是分支后的直通指令，I21、I22 和 I23 是采用路径开始处的指令；IF 是指令fetch阶段，DE是decode，BR是branch resolve，S1是BR之后的stage）：

         Taken                  Not taken
         IF  DE  BR  S1 ...     IF  DE  BR  S1 ...
cycle 1  BI  I3  I2  I1         BI  I3  I2  I1
cycle 2  ST  BI  I3  I2         ST  BI  I3  I2
cycle 3  ST  ST  BI  I3         ST  ST  BI  I3
cycle 4  I21 ST  ST  BI         I5  ST  ST  BI
cycle 5  I22 I21 ST  ST         I6  I5  ST  ST

设计二

为了避免必须在 IF 阶段结束时检测到分支的存在并允许有时完成一些有用的工作（在未采用的情况下），而不是让硬件有效地将无操作插入到管道中（即，在分支之后停止获取）硬件可以将分支视为任何其他指令，直到它在第三个流水线阶段解决。这是预测所有分支都没有被采用。如果分支被执行，那么在分支之后获取的两条指令被取消（实际上变成了无操作）。这是设计2：

         Taken                  Not taken
         IF  DE  BR  S1 ...     IF  DE  BR  S1 ...
cycle 1  BI  I3  I2  I1         BI  I3  I2  I1
cycle 2  I5  BI  I3  I2         I5  BI  I3  I2
cycle 3  I6  I5  BI  I3         I6  I5  BI  I3
cycle 4  I21 XX  XX  BI         I7  I6  I5  BI
cycle 5  I22 I21 XX  XX         I8  I7  I6  I5

设计 3

总是预测一个分支不被采用会在每次采用一个分支时浪费两个周期，因此开发了第三种机制来避免这种浪费——延迟分支。在延迟分支中，硬件总是在分支之后执行（不取消）延迟槽指令（示例中为两条指令）。通过始终执行延迟槽指令，简化了流水线。编译器的工作是尝试用有用的指令填充这些延迟槽。

无论采用哪条路径，从分支之前获取的指令（在没有延迟分支的程序中）都是有用的（但依赖性会阻止编译器在分支之后调度任何此类指令）。编译器可以使用来自已采用或未采用路径的指令填充延迟槽，但这样的指令不能覆盖另一条路径（或在路径加入后）使用的状态，因为延迟槽指令不会被取消（与预言）。（如果两条路径都连接——这对于 if-then-else 结构很常见——那么延迟槽可能会从连接点被填充；但这样的指令通常依赖于连接前至少一条路径的指令, 哪个依赖会阻止它们在延迟槽中使用。

在情况 3.1（延迟分支设计的最坏情况）中，编译器找不到任何有用的指令来填充延迟槽，因此必须用无操作来填充它们：

         Taken                  Not taken
         IF  DE  BR  S1 ...     IF  DE  BR  S1 ...
cycle 1  BI  I3  I2  I1         BI  I3  I2  I1
cycle 2  NO  BI  I3  I2         NO  BI  I3  I2
cycle 3  NO  NO  BI  I3         NO  NO  BI  I3
cycle 4  I21 NO  NO  BI         I5  NO  NO  BI
cycle 5  I22 I21 NO  NO         I6  I5  NO  NO

这在性能上等同于设计 1（停顿两个周期）。

在案例 3.2（延迟分支设计的最佳案例）中，编译器从分支之前找到两条指令来填充延迟槽：

         Taken                  Not taken
         IF  DE  BR  S1 ...     IF  DE  BR  S1 ...
cycle 1  BI  I1  ...            BI  I1  ...
cycle 2  I2  BI  I1  ...        I2  BI  I1 ...
cycle 3  I3  I2  BI  I1         I3  I2  BI  I1
cycle 4  I21 I3  I2  BI         I5  I3  I2  BI
cycle 5  I22 I21 I3  I2         I6  I5  I3  I2

在这种情况下，无论是否采用分支，所有流水线槽都充满了有用的指令。性能 (CPI) 与没有延迟解析分支的理想管道相同。

在案例 3.3 中，编译器使用来自所采用路径的指令填充延迟槽：

         Taken                  Not taken
         IF  DE  BR  S1 ...     IF  DE  BR  S1 ...
cycle 1  BI  I3  I2  I1         BI  I3  I2  I1
cycle 2  I21 BI  I3  I2         I21 BI  I3  I2
cycle 3  I22 I21 BI  I3         I22 I21 BI  I3
cycle 4  I23 I22 I21 BI         I5  UU  UU  BI
cycle 5  I24 I23 I22 I21        I6  I5  UU  UU

在未采用的路径中，I21 和 I22 是无用的。尽管它们实际上已执行（并更新状态），但在未采用的路径中（或在路径的任何连接之后）不使用此状态。对于未采用的路径，就好像延迟槽已被无操作填充。

在情况 3.4 中，编译器只能从未采用的路径中找到一条安全指令，并且必须用空操作填充另一个延迟槽：

         Taken                  Not taken
         IF  DE  BR  S1 ...     IF  DE  BR  S1 ...
cycle 1  BI  I3  I2  I1         BI  I3  I2  I1
cycle 2  I5  BI  I3  I2         I5  BI  I3  I2
cycle 3  NO  I5  BI  I3         NO  I5  BI  I3
cycle 4  I21 NO  UU  BI         I6  NO  I5  BI
cycle 5  I22 I21 NO  UU         I7  I6  NO  I5

对于所采取的路径，执行了一条无用指令和一条无操作，浪费了两个周期。对于未采取的路径，执行一个no-op，浪费一个周期。

计算 CPI

在这种情况下计算CPI的公式是：

%non_branch * CPI_non_branch + %branch * CPI_branch

CPI_branch 的计算方法是考虑分支本身所花费的时间 (baseCPI_branch) 以及分支在被占用时占用了浪费的周期的次数百分比，以及当它被占用时未占用分支的次数的百分比。不采取。所以 CPI_branch 是：

baseCPI_branch + (%taken * wasted_cycles_taken) + 
                 (%not_taken * wasted_cycles_not_taken)

在理想的标量流水线中，每条指令需要一个周期，即每条指令的周期数为 1。在此示例中，非分支指令的行为就像流水线是理想的一样（“处理器中的所有停顿都与分支相关”），因此每个非分支指令的 CPI 为 1。同样，baseCPI_branch（不包括停顿、无操作等浪费的周期）为 1。

根据上面的流水线图，可以确定在采用和未采用路径中浪费的周期数。该示例给出了分支的百分比以及采用和未采用的分支的百分比。

对于设计 1，采用和未采用的路径都浪费了 2 个周期，因此 CPI_branch 为：

1 + (0.3 * 2) + (0.7 *2) = 3

因此，总 CPI 为：

(0.85 * 1) + (0.15 * 3) = 1.3
于 2013-10-02T20:33:23.063 回答