计组习题的那些事（5）

今天起床，感觉十分通透啊，是个不错的日子！！！

流水线其实还是有点意思的，出现问题了，不断的去寻找方案解决，要么调整做的方式，要么做一些其他的事情，想的都是怎么更有效率的达到最后的目标。

这一章节的解答会选择图片比较多，流水线如果要出大题，也一定会出一道转发题的。

问题

考虑以下指令序列的流水线执行：

1
2
3
1. Add R4, R3, R2  
2. Or R7, R6, R5  
3. Subtract R8, R7, R4

假设

  1. 寄存器初始值：
    • R2 = 4, R3 = 8
    • R5 = 128, R6 = 2
  2. 流水线特性：
    • 提供从寄存器 RY 和 RZ 到 ALU 的操作数转发。
    • 在第1个时钟周期提取第1条指令，每个周期提取一条新指令。

要求

  1. 画出类似于图6-1的流水线执行图。
  2. 描述第4到第7个时钟周期中，寄存器 RY 和 RZ 的内容。

答案与解释

1. 流水线执行图

image-20241207161721066

2. 第4到第7个时钟周期中，寄存器 RY 和 RZ 的内容

  1. 第4个周期
    • RY: 之前未指定指令的结果（假设流水线中仍保留历史值）。
    • RZ: Add R4, R3, R2 的结果，4 + 8 = 12。
  2. 第5个周期
    • RY: Add 指令的结果，12。
    • RZ: Or R7, R6, R5 的结果，128 | 2 = 130。
  3. 第6个周期
    • RY: Or 指令的结果，130。
    • RZ: Subtract R8, R7, R4 的结果，130 - 12 = 118。
  4. 第7个周期
    • RY: Subtract 指令的结果，118。
    • RZ: 后续未指定指令的结果。

总结

  • 流水线的操作数转发特性确保在 Subtract 指令执行阶段能够获取所需的最新操作数，尽管依赖数据尚未写回寄存器文件。
  • 寄存器 RY 和 RZ 的内容在每个周期对应当前流水线阶段的计算结果，为流水线执行提供支持。

问题

  1. 假设条件：
    • 程序动态指令中 20% 为转移指令。
    • 无数据依赖性导致的流水线延迟。
    • 使用静态转移预测，假设不会发生转移。
  2. 问题要求：
    • (a) 当 30% 的转移发生和 70% 的转移发生时，分别计算执行时间。
    • (b) 比较两种情况，计算加速比并表示为百分比。

解答与解释

(a) 执行时间计算

  1. 定义公式
    转移误预测的比例（转移代价影响）为： $ S_{mispredict} = P_{branch} P_{mispredict} $
    • $ P_{branch} = 0.20 $（转移指令的比例）
    • $ P_{mispredict} $ 为误预测的比例（即预测错误的概率）。
    根据 6.8.1 节公式，程序总执行时间为： $ T = $
    • $ N $: 动态指令数量
    • $ R $: 执行速率（指令每秒）
  2. 两种情况下的计算

    • 情况 1：发生 30% 的转移
      $ S_{mispredict} = 0.20 = 0.06 $ 总执行时间： $ T_1 = = $

    • 情况 2：发生 70% 的转移
      $ S_{mispredict} = 0.20 = 0.14 $ 总执行时间： $ T_2 = = $

(b) 加速比计算

加速比（Speedup）定义为较慢情况相对于较快情况的性能提升： $ = = = $

相对于 1 的百分比加速： $ = (1.075 - 1) % = 7.5% $

总结

  1. 执行时间：
    • 情况 1（30% 转移发生）：\(\frac{1.06 \cdot N}{R}\)
    • 情况 2（70% 转移发生）：\(\frac{1.14 \cdot N}{R}\)
  2. 加速比：
    • 情况 1 比情况 2 的加速比为 7.5%。

问题

  1. 问题背景：
    • 在存储器中有四条指令，起始地址为 1000，每条指令占 4 个字节。
    • 依次为：
      • Add R3, R2, #20
      • Subtract R5, R4, #3
      • And R6, R4, #0x3A
      • Add R7, R2, R4
    • 指令在流水线中执行，流水线具有 5 个阶段（取指 F、译码 D、计算 C、访存 M、写回 W）。
    • 假设在第 1 个周期提取第一条指令，随后每个周期提取一条新指令。
  2. 要求：
    • (a) 绘制流水线的执行图，描述每个时钟周期中流水线的活动。
    • (b) 依据流水线寄存器（IR, PC, RA, RB, RY, RZ）在每个周期中的内容，分析其数据流。

(a) 流水线执行图与描述

流水线执行图

image-20241207162341089

各周期流水线阶段的活动描述

  1. 第 1 周期：
    • F：取指 Add 指令。
  2. 第 2 周期：
    • D：译码 Add 指令，读取寄存器 R2 的值（2000）。
    • F：取指 Subtract 指令。
  3. 第 3 周期：
    • C：计算 Add 指令的结果（2000 + 20 = 2020）。
    • D：译码 Subtract 指令，读取寄存器 R4 的值（50）。
    • F：取指 And 指令。
  4. 第 4 周期：
    • M：访存阶段，无操作需要。
    • C：计算 Subtract 指令的结果（50 − 3 = 47）。
    • D：译码 And 指令，读取寄存器 R4 的值（50）。
    • F：取指 Add (R7, R2, R4) 指令。
  5. 第 5 周期：
    • W：写回 Add 指令结果（2020 到寄存器 R3）。
    • M：访存阶段，无操作需要。
    • C：计算 And 指令的结果（50 AND 0x3A = 50）。
    • D：译码 Add (R7, R2, R4) 指令，读取 R2 和 R4 的值（2000 和 50）。
  6. 第 6 周期：
    • W：写回 Subtract 指令结果（47 到寄存器 R5）。
    • M：访存阶段，无操作需要。
    • C：计算 Add (R7, R2, R4) 指令的结果（2000 + 50 = 2050）。
  7. 第 7 周期：
    • W：写回 And 指令结果（50 到寄存器 R6）。
    • M：访存阶段，无操作需要。
  8. 第 8 周期：
    • W：写回 Add (R7, R2, R4) 指令结果（2050 到寄存器 R7）。

(b) 流水线寄存器内容分析

image-20241207162547421

总结

  • 流水线图清晰描述了每条指令在流水线中的活动。
  • 寄存器内容表展示了各时钟周期中关键流水线寄存器的状态变化。

问题

  1. 问题背景：
    • 本问题的指令序列与 6.1 类似，但在 And R6, R3, #0x3A 指令中，寄存器 R3 的值依赖于 Add R3, R2, #20 指令的计算结果，因此引入了操作数转发。
    • 假设处理器流水线支持从 RY 和 RZ 到 ALU 的操作数转发机制。
  2. 要求：
    • (a) 绘制流水线的执行图，描述每个时钟周期流水线阶段的活动，说明操作数转发的影响。
    • (b) 描述流水线寄存器 (IR, PC, RA, RB, RY, RZ) 在各周期的内容，并分析转发路径的作用。

(a) 流水线执行图与描述

流水线执行图

image-20241207163046628

各周期流水线阶段活动

  1. 第 1 周期：
    • F：取指 Add R3, R2, #20。
  2. 第 2 周期：
    • D：译码 Add R3, R2, #20，读取寄存器 R2（值为 2000）。
    • F：取指 Subtract R5, R4, #3。
  3. 第 3 周期：
    • C：计算 Add R3, R2, #20，结果为 2020。
    • D：译码 Subtract R5, R4, #3，读取寄存器 R4（值为 50）。
    • F：取指 And R6, R3, #0x3A。
  4. 第 4 周期：
    • M：访存阶段无操作（对于 Add R3, R2, #20）。
    • C：计算 Subtract R5, R4, #3，结果为 47。
    • D：译码 And R6, R3, #0x3A，读取寄存器 R3，此时 R3 的值由转发机制提供（2020）。
    • F：取指 Add R7, R2, R4。
  5. 第 5 周期：
    • W：将 Add R3, R2, #20 的结果写入寄存器 R3（值为 2020）。
    • M：访存阶段无操作（对于 Subtract R5, R4, #3）。
    • C：计算 And R6, R3, #0x3A，结果为 32（2020 AND 0x3A = 32）。
    • D：译码 Add R7, R2, R4，读取寄存器 R2（值为 2000）和 R4（值为 50）。
  6. 第 6 周期：
    • W：将 Subtract R5, R4, #3 的结果写入寄存器 R5（值为 47）。
    • M：访存阶段无操作（对于 And R6, R3, #0x3A）。
    • C：计算 Add R7, R2, R4，结果为 2050（2000 + 50）。
  7. 第 7 周期：
    • W：将 And R6, R3, #0x3A 的结果写入寄存器 R6（值为 32）。
    • M：访存阶段无操作（对于 Add R7, R2, R4）。
  8. 第 8 周期：
    • W：将 Add R7, R2, R4 的结果写入寄存器 R7（值为 2050）。

(b) 流水线寄存器内容与转发

image-20241207163243654

这个图的答案应该错了，RA应该是50先出现，之后才是R3的值出现，不要被答案误导了。

总结

  • 流水线执行图准确描述了指令在流水线中的活动，尤其是操作数转发的作用。
  • 寄存器内容表清楚展示了数据在流水线寄存器中的传递和转发路径：
    • 在第 4、5 周期中，R3 的值（2020）通过转发路径被直接提供给 ALU，用于计算 And 指令的结果。

问题

本问题涉及图 2-8 所示循环程序在 5 段流水线上的执行，其中： 1. 转发机制允许从寄存器 RY 和 RZ 到 ALU 转发数据。 2. 静态转移预测假设分支不会发生转移。 3. 循环程序中存在 数据相关性 和 控制相关性，会引入流水线停顿。

需要： - (a) 绘制流水线的执行图，显示连续两次迭代。 - (b) 分析流水线的停顿和转发路径的作用。

程序代码及指令说明

循环程序如下： 

1
2
3
4
5
6
7
LOOP:
  Load  R5, (R4)       # 从内存中加载到寄存器 R5
  Add   R3, R3, R5     # R3 += R5
  Add   R4, R4, #4     # R4 += 4
  Sub   R2, R2, #1     # R2 -= 1
  Store R3, SUM        # 将 R3 存储到 SUM
  Br_[R2>0] LOOP       # 如果 R2 > 0 则跳转到 LOOP

  • 假设初始时 R2 > 0，所以分支预测为“未转移”。
  • 每次迭代从第 1 条指令开始重新执行，间隔为 8 个时钟周期。

(a) 流水线执行图

问题陈述指出了从寄存器RY和RZ到算术逻辑单元（ALU）的转发路径。正如在6.6.1节和6.6.2节中所讨论的那样，要使分支指令仅产生一个时钟周期的延迟，还需要有通往译码阶段专用比较器的额外转发路径。给定代码对应的流水线执行示意图如下所示。

也就是比较器要有\(C->D\)

循环迭代 1 和 2 的流水线执行图

image-20241207164325366

(b) 停顿与转发分析

关键数据相关性

  • Load → Add R3, R3, R5：
    • R5 在第 4 周期的访存阶段产生，在第 5 周期通过 转发 提供给 Add R3, R3, R5 的计算阶段。
    • 如果没有转发机制，需要插入停顿周期。
  • Sub → Br_[R2>0]：
    • R2 的结果在第 8 周期的写回阶段产生，而分支指令需要在第 8 周期的 D 阶段使用。
    • 转发路径直接将 R2 的值送到分支比较器，减少停顿周期。

在循环连续执行各轮次的起始点之间存在8个时钟周期。为了能正确转发加载（Load）指令和减法（Subtract）指令的结果，每种情况下都需要插入一个暂停周期，以确保紧随其后的指令使用正确的操作数数值。如果没有上文所述的通往译码阶段的额外转发路径，那么每条分支（Branch）指令都将不得不暂停总共三个周期，以便减法运算的结果能被存入寄存器R2中。

## 问题
与习题 6.3 不同，习题 6.4 要求对循环中的指令重新排列，像编译器优化一样减少流水线停顿，提高性能。优化后的流水线有以下特点： 1. 指令重排后，能更好地填补因数据相关性导致的停顿周期。 2. 每次循环的启动间隔减少到 6 个时钟周期。 3. 转发机制继续起作用以避免延迟。

(a) 优化后的指令序列

假设循环的原始指令如下： 

1
2
3
4
5
6
7
LOOP:
  Load  R5, (R4)       # 从内存中加载到寄存器 R5
  Add   R3, R3, R5     # R3 += R5
  Add   R4, R4, #4     # R4 += 4
  Sub   R2, R2, #1     # R2 -= 1
  Store R3, SUM        # 将 R3 存储到 SUM
  Br_[R2>0] LOOP       # 如果 R2 > 0 则跳转到 LOOP

优化后的指令序列可重排为： 

1
2
3
4
5
6
7
LOOP:
  Load   R5, (R4)       # 从内存加载数据到 R5
  Add    R4, R4, #4     # R4 += 4（提到前面）
  Sub    R2, R2, #1     # R2 -= 1（提到前面）
  Add    R3, R3, R5     # R3 += R5（调整到后面）
  Store  R3, SUM        # 将 R3 存储到 SUM
  Br_[R2>0] LOOP        # 如果 R2 > 0 则跳转到 LOOP

此优化主要是： 1. 减少数据相关性停顿：尽量延后使用 Load 指令的结果。 2. 减少控制相关性停顿：尽早执行与 Br_[R2>0] 相关的计算。

(b) 优化后的流水线图

image-20241207165012522

(c) 结果与优化效果

性能提升

  • 优化前，每次循环的启动间隔为 8 个周期。
  • 优化后，循环的启动间隔为 6 个周期。

总结

  1. 数据相关性停顿：通过重排指令和转发机制，避免了额外的流水线停顿。
  2. 控制相关性停顿：利用转发路径直接解决分支跳转依赖问题，进一步减少延迟。
  3. 性能：每次迭代的启动时间减少 2 个周期，性能提升约 33%。

问题

习题 6.5 假设流水线使用 延迟转移技术，即分支指令后设置一个延迟槽，允许填充一条有用指令。这种技术可以减少分支跳转的性能开销。问题要求我们重新排列循环中的指令以优化性能，同时充分利用延迟槽。

(a) 原始循环指令

假设循环的指令如下： 

1
2
3
4
5
6
7
LOOP:
  Load  R5, (R4)       # 从内存中加载到寄存器 R5
  Add   R3, R3, R5     # R3 += R5
  Add   R4, R4, #4     # R4 += 4
  Sub   R2, R2, #1     # R2 -= 1
  Store R3, SUM        # 将 R3 存储到 SUM
  Br_[R2>0] LOOP       # 如果 R2 > 0 则跳转到 LOOP

挑战：在分支指令的延迟槽中放置一条指令，同时避免数据相关性和控制相关性的停顿。

(b) 优化后的指令序列

通过重新排列指令，充分利用延迟槽，我们得到以下优化版本： 

1
2
3
4
5
6
LOOP:
  Load   R5, (R4)       # 从内存加载数据到 R5
  Add    R3, R3, R5     # R3 += R5
  Sub    R2, R2, #1     # R2 -= 1
  Br_[R2>0] LOOP        # 如果 R2 > 0 则跳转到 LOOP
  Add    R4, R4, #4     # 延迟槽中执行 R4 += 4

优化思路： 1. Add R4, R4, #4 放入延迟槽：该指令与分支无直接依赖，可以安全填充延迟槽。 2. 避免了指令间的数据相关性停顿（例如 Load → Add 和 Sub → Br）。

(c) 流水线图

优化后的流水线执行情况如下：

image-20241207165337728

(c) 性能分析

优化效果

  • 优化前：每次循环启动间隔为 8 个周期。
  • 优化后：每次循环启动间隔减少到 5 个周期。

性能提升

性能提升率： $ = % = % = 37.5% $

总结

通过重新排列指令并利用延迟转移槽： 1. 避免了数据相关性导致的停顿。 2. 消除了分支跳转的延迟周期。 3. 循环性能提升 37.5%，每次迭代仅需 5 个时钟周期。

问题

我们分析程序执行时间，假设程序执行的动态指令中 20% 是转移指令，并且每个转移指令都有一个延迟槽：

  1. 如果延迟槽中填充的是 NOP 指令，延迟槽不做任何有用工作。
  2. 如果编译器优化了 70% 的延迟槽，将它们填充为有用指令，可以节省执行时间。

我们需要： 1. 推导两个执行时间的表达式。 2. 计算编译器优化的性能提升百分比。

推导过程

符号说明

  • $ N $：程序执行的总动态指令数。
  • 分支指令数量：$ 0.2N $，即 $ 20% $ 的指令是分支。
  • 延迟槽数：等于分支指令数 $ 0.2N $。
  • 基本执行时间：每条指令完成需要一个周期。

1. 所有延迟槽填充 NOP 指令

如果所有的延迟槽都用 NOP 填充： - 每条分支指令增加 1 个周期。 - 总周期数： $ T_{} = N + 0.2N = 1.2N $

2. 70% 延迟槽被优化填充有用指令

优化填充 $ 70% $ 的延迟槽，即 $ 0.7 0.2N = 0.14N $ 被填充有用指令： - 剩下 $ 0.3 0.2N = 0.06N $ 的延迟槽填充 NOP 指令。

此时的总周期数为： - 原始指令执行时间 $ N $。 - 延迟槽增加的有效指令和 NOP 指令占用时间： $ T_{} = N + 0.06N = 1.06N $

问题

假设有两个不同的处理器，一个有一个转移延迟槽，另一个有两个转移延迟槽，要求推导有两个转移延迟槽的处理器延迟槽优化后的执行时间表达式，与有一个转移延迟槽的处理器优化后的执行时间进行比较，确定哪个处理器/编译器组合速度更快并计算加速百分比，已知总指令数为 $ N $ ，转移指令占总指令的 $ 20% $（即 $ 0.2N $ ），对于有两个延迟槽的处理器，第一个延迟槽 $ 70% $ 的时间填充有用指令，第二个延迟槽 $ 10% $ 的时间填充有用指令。

答案

  • 有两个转移延迟槽的处理器，若所有延迟槽都用空操作（NOP）指令填充时，总周期数为 $ 1.4N $；若按给定的有用指令填充概率来填充延迟槽，总周期数为 $ 1.25N $ 。
  • 与有一个转移延迟槽的处理器（在6.7问题中结果为 $ 1.06N $ ）比较，有一个转移延迟槽的处理器优化后的执行时间结果更好。
  • 速度提升百分比为 $ 18% $（计算方式为 \((\frac{1.25}{1.06} - 1)× 100\) ），即有一个转移延迟槽的处理器/编译器组合速度更快。

解释

  1. 计算有两个转移延迟槽且全用NOP填充时的总周期数： 总指令数为 $ N $ ，转移指令数是 $ 0.2N $ ，每个转移指令有两个延迟槽，若都用NOP填充，相当于每个转移指令额外增加2个周期，所以总周期数就是原本的 $ N $ 加上转移指令带来的额外周期数 $ 2(0.2N) $ ，结果为 $ N + 2(0.2N) = 1.4N $ 。
  2. 计算有两个转移延迟槽且按概率填充有用指令时的总周期数： 总周期数的表达式为 $ N + 0.2((2 × 0.3)N + (0.7 × 0.9)N) = 1.25N $ 。这里面 $ 2 × 0.3 $ 对应的情况是，有 $ 30% $ 的情况两个延迟槽都没填充有用指令，此时每个转移指令会产生2个周期的惩罚（相当于多花费2个周期）；对于 $ 70% $ 的情况第一个延迟槽填充了有用指令，在这 $ 70% $ 里面又有 $ 90% $ 的情况第二个延迟槽是NOP（也就是只填充了第一个延迟槽有用指令），此时只产生1个周期的惩罚，对应 $ 0.7 × 0.9 $ 这一项，把这些不同情况综合起来计算得到总周期数为 $ 1.25N $ 。
  3. 比较两个处理器并计算加速百分比： 已知两个处理器时钟频率相同，比较总周期数就行，6.7问题中有一个转移延迟槽的处理器结果是 $ 1.06N $ ，本题中有两个转移延迟槽的处理器按优化填充后是 $ 1.25N $ ，所以有一个转移延迟槽的处理器执行时间更短，速度更快。加速百分比通过公式 \((\frac{1.25}{1.06} - 1)× 100\) 来计算，得出 $ 18% $ ，意思是有一个转移延迟槽的处理器相对有两个转移延迟槽的处理器速度提升了 $ 18% $ 。

问题

假设一个程序所执行的动态指令中有20%是转移指令，且75%的转移指令实际上发生了转移，该程序在两个具有相同时钟速率的不同处理器上执行，一个处理器使用假设转移不成功方法的静态转移预测，另一个处理器使用基于图6-12a中状态的动态转移预测（以6.6.4节中描述的方式使用转移目标缓冲区），需要解决以下两个问题： (a) 在没有其他原因产生流水线延迟时，使用动态转移预测的处理器与使用静态转移预测的处理器表现相同时，其预测准确率的最小值必须是多少？ (b) 如果动态预测准确率实际为90%，那么相对于使用静态预测的加速比是多少？

答案

  1. 动态转移预测的处理器预测准确率至少要达到25%，才能使其与使用静态转移预测的处理器表现相同。
  2. 当动态预测准确率为90%时，相对于使用静态预测的加速比是13%。

解释

  1. 关于静态转移预测下执行时间的计算及解释： 已知总指令数用 $ N $ 表示，转移指令占总指令的 $ 20% $，即 $ 0.2N $，又因为在静态转移预测中是假设分支（转移指令）不发生转移（假设转移不成功），而实际上有 $ 75% $ 的转移指令是发生转移的，这就意味着每次遇到实际发生转移的情况（也就是预测错误的情况），会产生一个周期的惩罚。所以执行时间就是原本的总指令数 $ N $ 加上因为预测错误带来的额外周期数，也就是 $ N + (0.2×0.75)N = 1.15N $ 。
  2. 关于动态转移预测下执行时间的计算及解释： 设 $ f_{wrong} $ 表示执行的转移指令中预测错误的比例，那么动态转移预测下的执行时间表达式就是 $ N + (0.2×f_{wrong})N = (1 + 0.2×f_{wrong})N $ 。这是因为总的执行时间要考虑原本的指令执行时间 $ N $ ，再加上由于转移指令预测错误而额外产生的周期数，每个预测错误的转移指令会带来一定的周期惩罚，这里用预测错误比例 $ f_{wrong} $ 结合转移指令占比 $ 0.2 $ 来计算额外周期数。
  3. 回答问题(a)的解释： 要让动态转移预测的处理器与静态转移预测的处理器表现相同，也就是要求动态转移预测下的执行时间不多于静态转移预测下的执行时间，即 $ (1 + 0.2×f_{wrong}) ≤ 1.15 $ ，通过对这个不等式进行移项求解（ $ 0.2×f_{wrong} ≤ 1.15 - 1 $ ，进一步得到 $ f_{wrong} ≤ = 0.75 $ ），可以得出 $ f_{wrong} $ 要小于等于 $ 0.75 $ ，这意味着预测错误比例最多是 $ 0.75 $ ，反过来就是说动态预测必须至少有 $ 1 - 0.75 = 0.25 $（即25%）的准确率，才能和静态转移预测表现相同。
  4. 回答问题(b)的解释： 如果动态预测准确率是 $ 90% $ ，那么预测错误的比例 $ f_{wrong} = 0.1 $ ，将其代入动态转移预测执行时间表达式可得此时执行时间为 $ 1.02N $ 。加速比的计算公式是 $ ( - 1)×100% $ ，这里旧的执行时间就是静态转移预测的 $ 1.15N $ ，新的执行时间就是动态转移预测准确率为 $ 90% $ 时的 $ 1.02N $ ，代入公式计算 $ ( - 1)×100 = 13% $ ，所以相对于静态预测的加速比是 $ 13% $ 。

问题

如图6 - 5那样转发寄存器RZ的值需要在流水线中增加额外的控制逻辑。问题是该额外的逻辑必须检查什么具体条件来确定在流水线的计算阶段向ALU输入端提供数据的多路复用器的设置？

image-20241207171125543

答案

额外的控制逻辑需要比较不同级间缓冲器中的寄存器标识符。将送往存储（Memory）阶段的级间缓冲器B3中的目的寄存器标识符与送往计算（Compute）阶段的级间缓冲器B2中的每个源寄存器标识符进行比较。如果目的寄存器和某个源寄存器匹配，则可能存在数据依赖。匹配的源寄存器标识符决定了哪个多路复用器需要合适的控制信号输入设置，以便为相应的ALU输入选择RZ的值。

但上述比较只有在送往存储阶段的级间缓冲器B3中用于写目的寄存器的控制信号设置为1时才有意义。这个控制信号设置会导致目的寄存器在写（Write）阶段被修改。在这种情况下，级间缓冲器B3中的目的寄存器标识符和级间缓冲器B2中的某个源寄存器标识符之间的匹配代表真正的数据依赖，需要进行转发。当级间缓冲器B3中的寄存器写控制信号设置为0时，无论寄存器标识符比较的结果如何，都不存在数据依赖。

对于规定寄存器R0的内容始终为常数0的指令集架构，还有一个更微妙的情况。如果R0被指定为一条指令的目的寄存器，且该指令的寄存器写控制信号设置为1，那么任何涉及R0与其他指令的明显数据依赖都应该被忽略。不应该转发任何以R0为目的寄存器的新结果，因为这个结果不会被写入R0。所以，上述控制逻辑必须对目的寄存器标识符和R0寄存器标识符进行额外的比较，以检测这种情况。

解释

  1. 关于寄存器标识符比较的解释
    • 在级间缓冲器中，需要有源操作数的寄存器标识符以及目的寄存器标识符。这些标识符在指令译码时进入流水线，并随着指令在流水线中流动。通过比较送往存储阶段的缓冲器B3中的目的寄存器标识符和送往计算阶段的缓冲器B2中的源寄存器标识符，来发现可能的数据依赖。因为如果一个指令的目的寄存器和另一个指令的源寄存器相同，那么可能存在前一个指令的结果需要被后一个指令使用的情况，这就是数据依赖。
    • 当发现这种匹配时，就知道在计算阶段的ALU输入可能需要使用前一个指令的结果（这里涉及转发寄存器RZ的值），具体由匹配的源寄存器标识符来决定哪个多路复用器需要设置控制信号，以选择正确的RZ值作为ALU输入。
  2. 关于控制信号设置为1的意义解释
    • 仅仅寄存器标识符匹配还不够，还需要考虑在存储阶段的级间缓冲器B3中用于写目的寄存器的控制信号。只有当这个控制信号为1时，才表示目的寄存器会在后续的写阶段被真正修改。在这种情况下，之前提到的寄存器标识符匹配才代表真正的数据依赖，才需要进行转发操作。如果这个控制信号为0，说明目的寄存器不会被修改，那么即使寄存器标识符匹配，也不存在数据依赖，不需要转发。
  3. 关于寄存器R0特殊情况的解释
    • 对于规定寄存器R0内容始终为0的指令集架构，当R0作为目的寄存器且写控制信号为1时，这是一种特殊情况。因为实际上按照规定R0的值不会被新的结果修改，所以即使出现看起来像是R0和其他指令有数据依赖的情况（比如寄存器标识符匹配），也应该忽略这种依赖，不进行转发。这就要求控制逻辑额外检查目的寄存器标识符是否为R0，以此来正确处理这种特殊情况，避免不必要的转发操作。

问题

对于将图5 - 8中寄存器RY的内容转发给向ALU输入端提供数据的多路复用器，需要明确额外的控制逻辑必须检查什么具体条件来确定在流水线的计算阶段向ALU输入端提供数据的多路复用器的设置，此为重复习题6.10中的问题形式。

答案

  1. 首先，要对图6.5中的多路复用器MuxA和MuxB进行扩展，除了原本RZ的值对应的输入外，要为RY的值增加额外输入。
  2. 其次，在习题6.10答案所描述的控制逻辑基础上引入新的寄存器标识符比较操作。为了确定是否应该转发寄存器RY的值，需要将送往写（Write）阶段的级间缓冲器B4中的目的寄存器标识符与送往计算（Compute）阶段的级间缓冲器B2中的源寄存器标识符进行比较。同时，还必须使用级间缓冲器B4中的寄存器写控制信号设置来确定是否真正存在数据依赖。此外，还需要考虑常数寄存器R0作为目的寄存器的这种特殊情况。

解释

  1. 关于多路复用器扩展的解释： 要实现将RY的值转发给ALU输入端的多路复用器，第一步就是要对相关的多路复用器（图6.5中的MuxA和MuxB）进行硬件层面的扩展，给它们增加能够接入RY值的输入端口，这样才具备了从硬件上选择RY值作为ALU输入的可能性。
  2. 关于寄存器标识符比较及控制信号使用的解释：
    • 通过比较送往不同阶段的缓冲器中的寄存器标识符来判断数据依赖情况。把送往写阶段的级间缓冲器B4中的目的寄存器标识符和送往计算阶段的级间缓冲器B2中的源寄存器标识符进行对比，如果两者有匹配，意味着可能存在数据依赖，即写阶段要写入目的寄存器的值可能正是计算阶段某个源寄存器（这里涉及RY）需要使用的值。
    • 但仅仅标识符匹配还不够，还要参考级间缓冲器B4中的寄存器写控制信号设置。只有当这个控制信号为1时，才表明目的寄存器会被实际修改，此时前面提到的标识符匹配所代表的潜在数据依赖才是真正存在的数据依赖，这种情况下才需要进行RY值的转发操作；若控制信号为0，即便标识符匹配，也不存在实际的数据依赖，不需要转发RY的值。
  3. 关于寄存器R0特殊情况的解释： 和之前一样，对于规定寄存器R0内容始终为常数0的指令集架构，当R0作为目的寄存器时是一种特殊情况。即便出现看起来像是和其他指令有数据依赖的情况（比如寄存器标识符匹配且控制信号合适等情况），按照规定R0的值不会被新的结果改变，所以要对这种情况进行额外考虑，避免错误地进行转发操作，也就是要在控制逻辑中对目的寄存器标识符是否为R0进行检测并做相应处理。

问题

作为习题6.10和6.11的延续，给出了“Add R3,R2,R1；Subtract R3,R5,R4；Or R8,R3,#1”这样的指令序列，需要描述在这种情况下处理转发的方式，以及说明应该如何修改习题6.10和习题6.11中的条件。

答案

  • 处理转发的方式： 在这个指令序列中，同时存在着存储器（Memory）阶段和计算（Compute）阶段（“Add → Or”）以及写（Write）阶段和计算阶段（“Subtract → Or”）之间因寄存器标识符匹配而出现的两种看似的数据依赖情况。但实际上，只有存储器阶段和计算阶段之间的依赖才是真正的数据依赖，因为它反映的是相关寄存器最新生成的值。来自存储器阶段的值才是应该被转发的值，写阶段的结果是较早产生的结果，并且会先写入目的寄存器，而存储器阶段的结果是较新的结果，后续才会写入同一个寄存器。计算阶段的指令必须使用较新的结果才能正确反映正在执行的指令序列的语义，所以要优先处理存储器阶段和计算阶段之间的依赖进行转发，只有在计算阶段涉及的相同源寄存器不存在来自存储器阶段的依赖时，才会从写阶段向计算阶段进行转发。

  • 对习题6.10和6.11条件的修改： 与习题6.10和6.11的解决方案类似，对于此处描述的情况，控制逻辑仍然需要考虑存储器阶段和写阶段的寄存器写控制信号设置，以此来验证是否存在真正的数据依赖，同时也要考虑常数寄存器R0作为目的寄存器这种可能情况。

解释

  1. 关于处理转发方式的解释：
    • 从指令执行顺序来看，先是执行“Add”指令，接着是“Subtract”指令，最后是“Or”指令。当考虑“Or”指令在计算阶段时，它需要使用前面指令产生的寄存器R3的值作为操作数。“Add”指令产生的结果在经过一定阶段后处于存储器阶段，“Subtract”指令产生的结果处于写阶段，都与“Or”指令在计算阶段对R3值的需求产生了关联，也就是出现了寄存器标识符匹配带来的数据依赖表象。
    • 然而，“Add”指令后续流程所处的存储器阶段相对“Subtract”指令所处的写阶段来说，其结果是更新的，因为按照指令执行顺序，“Add”指令结果更新在后，所以这个更新的值才是“Or”指令在计算阶段应该使用的正确值，要优先基于这种情况进行转发，保障指令执行的语义正确，即符合先执行加法得到新值，后续其他指令使用这个新值的逻辑顺序。只有当不存在来自存储器阶段针对计算阶段相同源寄存器（这里是R3）的依赖时，才去考虑从写阶段向计算阶段转发，避免使用到旧值而导致指令执行结果不符合预期。
  2. 关于修改条件的解释：
    • 如同之前习题6.10和6.11中所强调的，判断是否真正存在数据依赖不能仅仅依靠寄存器标识符匹配，还要看相应阶段的寄存器写控制信号设置。在当前这个指令序列涉及的情况中同样如此，对于存储器阶段和写阶段，只有对应的寄存器写控制信号为1，表示相应寄存器确实会被写入新值，这种寄存器标识符匹配带来的数据依赖才是真实有效的，才需要按前面说的转发规则进行处理。
    • 另外，考虑到寄存器R0内容始终为常数0这个特殊设定，如果出现R0作为目的寄存器的情况，即便有其他看似的数据依赖表象（比如寄存器标识符匹配等情况），也不能按照常规的转发逻辑来处理，要对这种特殊情况进行识别并避免错误转发，所以仍然要把R0作为目的寄存器这种可能情况纳入控制逻辑的考虑范围之中，以保证整个转发机制在各种情况下都能正确运行。

问题

假设一个程序不包含转移指令，在图6 - 13所示的超标量处理器上执行，程序指令由75%的算术指令和25%的存储器访问指令组成，需要求出预期的最佳执行时间是多少个周期，并且要将这个时间与图6 - 2中简单处理器上的最佳执行时间进行比较（使用相同的时钟）。

答案

  • 预期的最佳执行时间： 在超标量处理器上，预期的最佳执行时间是 $ 0.75N $ 个周期（ $ N $ 为总指令数）。
  • 与简单处理器最佳执行时间的比较及速度提升情况： 在简单的五阶段流水线处理器上，执行时间是 $ N $ 个周期（忽略最后一条指令的最后四个周期）。通过计算可得超标量处理器相对简单处理器的速度提升为 $ 33% $（计算方式为 \((\frac{1}{0.75} - 1)×100\) ）。

解释

  1. 关于超标量处理器最佳执行时间的解释： 在这个超标量处理器中，因为算术指令占比 $ 75% $ ，且算术指令是一个一个依次通过对应的执行单元的，所以整个程序的执行时间基本是由算术指令的执行情况来决定的。由于总指令数假设为 $ N $ ，按照算术指令所占比例来计算，其执行时间就是 $ 0.75N $ 个周期。比如有100条指令（即 $ N = 100 $ ），其中算术指令有75条，那么算术指令依次执行完就大概需要75个周期左右来主导整个程序的执行时长，这里忽略了其他一些细微的并行等复杂情况的影响，取的是预期的最佳情况。
  2. 关于与简单处理器比较及速度提升的解释： 在简单的五阶段流水线处理器上，理想情况下（不考虑其他复杂因素，比如转移指令等带来的停顿等情况），指令就是一条一条按顺序在流水线各个阶段流转执行，总指令数是 $ N $ 条，那执行时间就是 $ N $ 个周期。而在超标量处理器上算出最佳执行时间是 $ 0.75N $ 个周期，速度提升比例的计算公式是 $( - 1)×100% $ ，把简单处理器的执行时间 $ N $ 作为旧的执行时间，超标量处理器的执行时间 $ 0.75N $ 作为新的执行时间，代入公式计算就得到 $( - 1)×100 = 33% $ ，这就表明了超标量处理器相对简单处理器在执行这个程序时的速度提升情况，同时也说明了由于本题中算术指令和存储器访问指令分布不均匀（算术指令占比较大），限制了所能达到的最大速度提升倍数，不像两种指令各占 $ 50% $ 那样能达到理想的2倍（即 $ 100% $ ）速度提升。

问题

假设程序指令由15%永远不会发生转移的转移指令、65%的算术指令和20%的存储器访问指令组成，要为图6 - 2（简单五阶段流水线处理器）和图6 - 13（超标量处理器）中的处理器找出可能的最佳执行时间，并重复习题6.14中的比较相关内容，同时假设所有转移指令的预测准确率为100%。

答案

  • 简单五阶段流水线处理器的最佳执行时间： 对于简单五阶段流水线处理器，理想执行时间为 $ N $ 个周期（ $ N $ 为总指令数）。因为转移指令永远不会发生转移，即便采用静态预测（假设分支不发生转移这种简单的静态预测方式）也不会产生分支惩罚，所以总指令按顺序在流水线流转执行，总执行时间就是 $ N $ 个周期。

  • 超标量处理器的最佳执行时间： 在超标量处理器中，转移指令在取指单元就被处理了，不会被分派到算术单元或者存储单元去执行。由于算术指令占比65%，在假设完美分支预测（也就是这里转移指令预测准确率为100%，不会产生额外惩罚）且忽略其他额外影响的理想情况下，整个程序的执行时间由算术指令的执行情况决定，所以执行时间是 $ 0.65N $ 个周期。

  • 速度提升情况： 超标量处理器相对简单五阶段流水线处理器的速度提升为 $ 54% $，计算方式为 \((\frac{1}{0.65} - 1)×100\) 。

解释

  1. 关于简单五阶段流水线处理器执行时间的解释： 在简单的五阶段流水线架构里，指令依次经过取指、译码、执行、访存、写回等阶段按顺序流转执行。虽然有15%的转移指令，但已知它们永远不会发生转移，所以不管采用何种常规的预测方式（这里提到静态预测），都不会出现因为转移预测错误而导致的流水线停顿、额外周期增加等惩罚情况。那么总指令数是 $ N $ 条时，指令就顺畅地在流水线中流转，执行完所有指令就需要 $ N $ 个周期，这就是其理想的最佳执行时间。
  2. 关于超标量处理器执行时间的解释： 超标量处理器有着不同的执行单元来处理不同类型的指令。转移指令在取指单元就能得到妥善处理（因为预测准确率100%，处理起来很顺利，不会造成后续执行单元的干扰），不会被送到算术单元或者存储单元去执行。而在所有指令类型中，算术指令占比最大，达到65%，并且在没有因为转移等情况产生额外惩罚的理想状态下，整个程序执行的节奏基本是跟着算术指令走的，相当于算术指令依次通过对应的执行单元来主导整个程序的执行时长，所以按照占比计算，执行时间就是 $ 0.65N $ 个周期。
  3. 关于速度提升的解释： 比较两个处理器的速度提升情况，依据的公式是 $( - 1)×100% $ 。在这里，简单五阶段流水线处理器的执行时间 $ N $ 就是旧的执行时间，超标量处理器的执行时间 $ 0.65N $ 就是新的执行时间，代入公式进行计算 \((\frac{1}{0.65} - 1)×100\) ，得出速度提升比例为 $ 54% $ ，意味着在这样的指令组成和预测准确率条件下，超标量处理器相对简单五阶段流水线处理器在执行速度方面有比较明显的提升。