bas*_*sil 1 cpu-architecture pipelining branch-prediction
我正在学习计算机体系结构课程。我从另一所大学找到了这个网站，其中的笔记和视频迄今为止对我有帮助：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%）：
在每个分支上，获取都会停止，直到知道分支结果为止。
每个分支都被预测为不被采用，并且如果该分支被采用，则误取的指令将被压缩。
处理器有两个延迟槽，分支后面的两条指令总是被取出并执行，并且
3.1. 您无法找到任何说明来填充延迟槽。
3.2. 您可以将分支之前的两条指令移至延迟槽中。
3.3. 您可以将标签“linex”后的两条指令移至延迟槽中。
3.4. 您可以在分支（在原始代码中）之后立即将一条（注意：一条，而不是两条！）指令移至延迟槽中。
我不确定如何开始看待这个问题。我已经阅读了所有笔记并观看了该网站上的视频，并阅读了 H&P 书中的部分内容，但仍然对这个问题感到困惑。如果有人有时间，我将不胜感激有人帮助我解决这个问题。我只需要知道如何开始概念化答案。
小智 5
在所描述的流水线中，条件分支的方向和目标直到第三周期结束才可用，因此直到第四周期开始才能够（确定地）获取分支之后正确的下一条指令。
处理分支后指令地址的延迟可用性的一个明显方法就是简单地等待。这就是设计 1 通过停止两个周期所做的事情（相当于获取两个不属于实际程序的空操作）。这意味着对于采用和未采用的路径，都会浪费两个周期，就像编译器插入了两条无操作指令一样。
下面是流水线图（ST 是停顿，NO 是无操作，XX 是取消指令，UU 是无用指令，I1、I2 和 I3 是分支之前的三个指令[按原始程序顺序]在填充任何延迟槽之前]，BI是分支指令，I5、I6和I7是分支后的失败指令，I21、I22和I23是所采取路径开始处的指令；IF是指令获取阶段，DE是解码，BR是分支解析，S1是BR之后的阶段）：
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
每当分支被采用时，总是预测不被采用的分支会浪费两个周期，因此开发了第三种机制来避免这种浪费——延迟分支。在延迟分支中，硬件始终执行（不取消）分支之后的延迟槽指令（示例中的两条指令）。通过始终执行延迟槽指令，简化了流水线。编译器的工作是尝试用有用的指令填充这些延迟槽。
无论采用哪条路径，从分支之前（在没有延迟分支的程序中）获取的指令都将很有用（但依赖性可能会阻止编译器在分支之后调度任何此类指令）。编译器可以用来自已采用或未采用路径的指令填充延迟槽，但此类指令不能覆盖另一路径（或路径连接后）使用的状态，因为延迟槽指令不会被取消（与预言）。（如果两条路径都连接——这对于 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
对于所采取的路径，执行了一条无用指令和一条无操作，浪费了两个周期。对于未采取的路径，执行一次空操作，浪费一个周期。
本例中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