系统结构作业2
系统结构作业2
系统结构作业2
3.1 解释下列名词（任选5个）
根据课件内容，选择以下5个常见名词进行解释：
- 流水线技术 (Pipelining)：把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，这样每个子过程就可以与其他的子过程并行进行。
- 吞吐率 (Throughput)：在单位时间内流水线所完成的任务数量或输出结果的数量。
- 数据冲突 (Data Hazard)：当相关的指令靠得足够近时，它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序，使之不同于它们非流水实现时的顺序，从而发生的冲突（对应真数据相关）。
- 结构冲突 (Structural Hazard)：因硬件资源满足不了指令重叠执行的要求而发生的冲突。例如功能部件不是完全流水或资源份数不够。
- 换名技术 (Register Renaming)：通过改变指令中操作数的名来消除名相关（反相关和输出相关）的技术。对于寄存器操作数进行换名称为寄存器换名。
3.3 简述通过软件（编译器）来减少分支延迟的三种方法，这些方法的共同特点是什么？
三种方法：
- 消除分支：用条件执行指令（或flag条件判断）替换分支指令，从而在根本上消除分支带来的延迟。
- 预测执行——预测分支失败（Predict Not Taken）：允许分支指令后的指令继续在流水线中流动，就像没发生分支一样。若确定分支失败，则流水线正常流动；若确定分支成功，则把分支指令后取出的指令转化为空操作，并按分支目标重新取指。
- 延迟分支 (Delayed Branch)：在分支指令后面加上若干条指令（即延迟槽），把它们看成一个整体。不管分支是否成功，都顺序执行这些延迟槽中的指令，以此来掩盖分支延迟。
共同特点： 这几种方法对分支的处理策略在程序的执行过程中始终是不变的，是静态的（由编译器在编译时决定）。要么总是预测分支成功，要么总是预测分支失败。
3.4 简述延迟分支方法中的三种调度策略的优缺点。
在延迟槽中放入有用指令的三种调度策略及其优缺点（或适用条件/效果）如下：
- 从前调度（首选策略）：
- 要求：被调度的指令必须与分支指令的条件判定无关。
- 优缺点：最理想的策略，无论分支成功与否都能起作用，不会增加额外开销。
- 从目标处调度：
- 要求：必须保证在分支失败时，执行被调度的指令不会导致错误（相当于静态预测分支成功）。
- 优缺点：在分支成功时起作用；缺点是可能需要复制指令，有可能会增大程序代码的空间。
- 从失败处调度：
- 要求：必须保证在分支成功时，执行被调度的指令不会导致错误（相当于静态预测分支失败）。
- 优缺点：只有在分支失败时才起作用，适用于大概率不发生跳转的条件分支。
3.11 在 MIPS 流水线上运行代码序列
循环次数分析： R3的初值是R2 + 396，每次循环R2递增4。退出条件是DSUB R4, R3, R2产生的R4 == 0。 共需执行 $396 \div 4 = 99$ 次循环。
(1) 无定向硬件，排空流水线处理分支（即必须等到写回才读取，分支在MEM段修改PC）
LW到DADDIU R1：发生RAW，无定向需停顿2拍。DADDIU R1到SW：发生RAW，需停顿2拍。DADDIU R2到DSUB：发生RAW，需停顿2拍。DSUB到BNEZ：发生RAW，需停顿2拍。BNEZ采用排空流水线，在 MEM 段更新 PC，产生3拍的分支延迟。 时钟周期计算：单次循环的间隔为 $1(\text{基础}) + 2\times4(\text{四个RAW停顿}) + 3(\text{排空分支延迟}) + 5(\text{指令数}) = 17$ 个周期。 执行 99 次循环，前 98 次每次启动间隔 17 个周期。第 99 次最后一条指令(BNEZ)写回完成需要 $1 + 98 \times 17 + 17$ (即最后一次本身需要的17拍执行完加排空) $- 1 = 1684$ 个时钟周期。
(2) 正常定向路径，预测分支失败（条件测试在 ID 段进行）
LW到DADDIU R1：Load-use 冲突，利用定向仍需停顿1拍。DADDIU R1到SW：EX 到 EX 定向，无需停顿。DADDIU R2到DSUB：EX 到 EX 定向，无需停顿。DSUB到BNEZ：BNEZ在 ID 段需要判断条件，DSUB在 EX 段产生结果，EX 到 ID 定向需停顿1拍。BNEZ预测失败，但实际跳转成功。在 ID 段(第2拍)解析出目标，清除后面错取的1条指令，产生1拍延迟。 时钟周期计算：单次循环的间隔为 $6(\text{指令}) + 1(\text{Load-use}) + 1(\text{DSUB至ID}) + 1(\text{预测失败冲刷}) = 9$ 个周期。 共需 $98 \times 9 + 12(\text{最后一次循环BNEZ写回所需总拍数}) = 894$ 个时钟周期。
(3) 正常定向路径 + 1个延迟分支槽，重新组织指令 采用从前调度，将 SW R1, 0(R2) 移动到延迟槽中（注意此时 R2 已经提前加了4，所以偏移量需改为 -4），并将不会引发停顿的指令穿插以消除数据相关： 调度后的代码：
LOOP: LW R1, 0(R2)
DADDIU R2, R2, #4 ; 提前执行，避免与DSUB产生停顿
DSUB R4, R3, R2
DADDIU R1, R1, #1 ; 插入LW和SW之间，且距离LW足够远，消除Load-use停顿
BNEZ R4, LOOP ; 分支判断
SW R1, -4(R2) ; 延迟槽指令，偏移量修正为-4
时钟周期计算：调度后所有数据冲突均被定向机制完美消除（Load-use 距离被拉开，DSUB到BNEZ的距离也被拉开），且延迟槽吸收了分支延迟，全程无任何停顿。 每次循环耗时刚好是指令条数，即 6 个周期。 共需 $98 \times 6 + 10 (\text{最后一次SW写回完毕}) = 598$ 个时钟周期。
3.12 加速比计算
题意解析：
- 理想情况（无控制相关）：每周期执行一条指令，理想 $\text{CPI} = 1$。
- 实际情况（有控制相关）：流水线段数为 4 段。
- 条件分支 (CB) 占 20%，其中 60% 成功 (Taken)，40% 失败 (Not Taken)。条件分支在第 3 周期（EX段结束）解析，若采用默认的预测失败机制（题干给出成功率即暗示预测失败策略），失败时无惩罚，成功时需冲刷已取出的指令，惩罚为 2 个时钟周期。
- 无条件跳转 (UB) 占 5%，在第 2 周期（ID段结束）解析，因必然跳转，冲刷已取出的指令，惩罚为 1 个时钟周期。
计算过程：
- 分支指令带来的平均停顿周期（Penalty）： \(\text{Penalty} = (20\% \times 60\%) \times 2 + 5\% \times 1 = 0.12 \times 2 + 0.05 = 0.24 + 0.05 = 0.29\)
- 存在控制相关情况下的实际 $\text{CPI}$： \(\text{CPI}_{\text{实际}} = \text{CPI}_{\text{理想}} + \text{Penalty} = 1 + 0.29 = 1.29\)
- 无控制相关相对于有控制相关的加速比： \(\text{Speedup} = \frac{\text{CPI}_{\text{实际}}}{\text{CPI}_{\text{理想}}} = \frac{1.29}{1} = 1.29\)
答： 在没有任何控制相关的情况下，该流水线相对于存在上述控制相关情况下的加速比是 1.29。
3.11
针对3.11，我们需要详细分析代码在不同流水线策略下的执行情况，并结合课件中的原理（数据冲突、控制冲突及其解决机制）来画出时空图并进行计算。
题目基础分析
循环次数分析： 指令
DSUB R4, R3, R2用于判断循环是否结束，初始时R3 = R2 + 396。 每次循环R2增加 4，因此需要循环 $396 \div 4 = 99$ 次。 前 98 次分支预测（或实际执行）为跳转（分支成功），第 99 次分支不跳转（退出循环）。寄存器读写约定： 课件约定“在前半个时钟周期写操作，后半个时钟周期读操作”，这意味着如果在同一个周期内 WB 段写回寄存器，ID 段可以成功读到最新值，这一特性可以消除部分由于 WB 导致的数据冲突。
(1) 没有任何定向硬件，排空流水线处理分支
规则分析：
- 无定向（无旁路）：任何数据相关（RAW）必须严格等到产生该数据的指令进入 WB 段，读取该数据的指令才能在 ID 段顺利读出。
- 排空流水线处理分支：课件（Slide 101/102）指出，在不提前计算的情况下，分支指令在 EX 段进行条件测试，在 MEM 段 更新 PC。这会给流水线带来 3 个周期的延迟。
第 1 次循环的时空图（稳态）： 注：s 表示 stall（停顿）。根据课件，ID 段停顿时，IF 段也会随之停顿。
| 指令 / 周期 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
LW R1, 0(R2) | IF | ID | EX | ME | WB | ||||||||||||||
DADDIU R1, R1, 1 | IF | ID | ID | ID | EX | ME | WB | ||||||||||||
SW R1, 0(R2) | IF | IF | IF | ID | ID | ID | EX | ME | WB | ||||||||||
DADDIU R2, R2, 4 | IF | IF | IF | ID | EX | ME | WB | ||||||||||||
DSUB R4, R3, R2 | IF | ID | ID | ID | EX | ME | WB | ||||||||||||
BNEZ R4, LOOP | IF | IF | IF | ID | ID | ID | EX | ME | WB | ||||||||||
下一循环的 LW | IF | ID |
逐周期详细解释：
- 周期 1-5：
LW正常流过流水线，在周期 5 写回。 - 周期 3-5：
DADDIU R1在周期 3 进入 ID 段，发现需要LW产生的R1，由于无定向，必须等LW在周期 5 的前半拍写回，因此在周期 3、4 停顿，周期 5 成功读出，此时SW在 IF 段一并被阻塞。 - 周期 6-8：
SW R1在周期 6 进入 ID 段，需要DADDIU R1的结果。等它在周期 8 写回后，才能在周期 8 读出。停顿 2 拍。 - 周期 9-12：
DADDIU R2与前面的指令无数据相关，正常流过（但前期被SW的停顿堵在 IF 段）。它在周期 12 完毕写回。 - 周期 10-12：
DSUB R4需要R2，在周期 10 进入 ID 段，停顿 2 拍，直到周期 12 读出DADDIU R2写回的结果。 - 周期 13-17：
BNEZ需要R4，在周期 13 进入 ID 段，停顿 2 拍等DSUB写回。周期 15 读出数据，周期 16 在 EX 段评估条件，周期 17 在 MEM 段更新 PC（排空分支的惩罚）。 - 周期 18：新的 PC 生效，下一轮循环的
LW从周期 18 开始 IF。
计算过程：
- 单次循环的启动间隔为 $18 - 1 = 17$ 个时钟周期。
- 前 98 次循环，每次间隔 17 个周期：$98 \times 17 = 1666$ 周期。
- 第 99 次循环（最后一次）从周期 1667 开始，其最后一条指令
BNEZ完成 WB 还需要 18 个周期，即在 $1667 + 18 - 1 = 1684$ 周期结束。 答：执行上述循环需要 1684 个时钟周期。
(2) 正常的定向路径，预测分支失败策略处理分支
规则分析：
- 定向（旁路）：EX->EX, MEM->EX 等可以直接传递数据。只有 Load-Use 冲突（如
LW后紧跟用到该数据的 ALU 指令）无法完全通过定向消除，需要停顿 1 拍。 - 预测分支失败：课件（Slide 104、107）指出，硬件把条件测试和目标计算移到了 ID 段。预测失败意味着紧跟着分支指令继续取下一条顺序指令。如果预测错误（实际发生跳转），则在 ID 段测出跳转后，将已取出的 1 条顺序指令（Fall-through）清除（冲刷），带来 1 拍的惩罚。
第 1 次循环的时空图（稳态）：
| 指令 / 周期 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
LW R1, 0(R2) | IF | ID | EX | ME | WB | |||||||
DADDIU R1, R1, 1 | IF | ID | ID | EX | ME | WB | ||||||
SW R1, 0(R2) | IF | IF | ID | EX | ME | WB | ||||||
DADDIU R2, R2, 4 | IF | ID | EX | ME | WB | |||||||
DSUB R4, R3, R2 | IF | ID | EX | ME | WB | |||||||
BNEZ R4, LOOP | IF | ID | ID | EX | ME | WB | ||||||
顺序下一条 (预测) | IF | IF | 清除 | |||||||||
下一循环的 LW | IF | ID | EX |
逐周期详细解释：
- 周期 3-4：
DADDIU R1在 ID 段检测到需要LW在 EX 段的数据，发生 Load-Use 冲突，停顿 1 拍。周期 4 从LW的 MEM 段取得定向数据。 - 周期 5-7：
SW、DADDIU R2、DSUB的相关均可以通过 EX->EX 定向解决，无需停顿。 - 周期 8-9：
BNEZ在 ID 段（周期 8）进行条件判断，需要DSUB产生的R4，但此时DSUB刚在 EX 段算完。因此BNEZ必须停顿 1 拍，在周期 9 利用 MEM->ID 的定向路径拿到R4完成判断。 - 周期 9-10：周期 9 时，
BNEZ确定跳转（分支预测错误）。在周期 9 取出的顺序指令在周期 10 被清除（Flush），新的LW在周期 10 开始 IF。
计算过程：
- 单次循环的启动间隔为 $10 - 1 = 9$ 个时钟周期。
- 前 98 次循环：$98 \times 9 = 882$ 周期。
- 第 99 次循环从周期 883 开始取指，
BNEZ在它的第 12 个周期（即相对该轮循环 IF 的第 12 拍）完成 WB，结束时间为 $883 + 12 - 1 = 894$ 周期。 答：执行上述循环需要 894 个时钟周期。
(3) 正常定向路径 + 1个延迟分支槽，指令调度
规则分析：
- 延迟分支：分支指令后的 1 个延迟槽指令必定会被执行，相当于利用这个时钟周期掩盖了分支的 1 拍延迟惩罚。
- 指令调度：改变指令顺序，但不改变语义，以消除 Load-Use 和 ALU-Branch 等数据冲突停顿。 我们采用从前调度（首选策略），将循环体中与分支判断无关的
SW R1, 0(R2)移入延迟槽。注意：因为DADDIU R2, R2, 4被提前执行了，所以SW的偏移量必须减去 4，修正为-4(R2)。同时拉开LW与DADDIU R1、DSUB与BNEZ的距离。
调度后的代码：
LOOP: LW R1, 0(R2)
DADDIU R2, R2, #4 ; 提前执行，不依赖 R1
DSUB R4, R3, R2 ; 提前执行，拉开与 BNEZ 的距离
DADDIU R1, R1, #1 ; 插入在 LW 和 SW 之间，距离 LW 足够远，消除 Load-Use 停顿
BNEZ R4, LOOP ; 此时 R4 早已由 DSUB 算出
SW R1, -4(R2) ; 延迟槽指令，偏移修正为 -4
第 1 次循环的时空图（稳态）：
| 指令 / 周期 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
LW R1, 0(R2) | IF | ID | EX | ME | WB | ||||||
DADDIU R2, R2, 4 | IF | ID | EX | ME | WB | ||||||
DSUB R4, R3, R2 | IF | ID | EX | ME | WB | ||||||
DADDIU R1, R1, 1 | IF | ID | EX | ME | WB | ||||||
BNEZ R4, LOOP | IF | ID | EX | ME | WB | ||||||
SW R1, -4(R2) | IF | ID | EX | ME | WB | ||||||
下一循环的 LW | IF | ID | EX | ME | WB |
逐周期详细解释：
- 整个调度完美避开了所有流水线停顿：
LW和DADDIU R1之间隔了 2 条指令，DADDIU R1在 EX 段时，LW已经到了 WB 段，完全没有 Load-Use 停顿。DSUB和BNEZ之间隔了 1 条指令，BNEZ在 ID 段（周期 6）测条件时，DSUB正处于 MEM 段，可以通过 MEM->ID 定向直接拿到R4，无需停顿。SW被置于延迟槽中，在BNEZ解析出目标地址并改变 PC 期间无缝流入流水线，完全掩盖了 1 拍的分支延迟。
计算过程：
- 因为没有停顿也没有冲刷，每轮循环的启动间隔严格等于指令条数，即 6 个时钟周期。
- 前 98 次循环：$98 \times 6 = 588$ 周期。
- 第 99 次循环（最后一次）从周期 589 开始取指，它的最后一条指令（延迟槽的
SW）在它的第 10 个周期完成 WB。因此总周期为 $589 + 10 - 1 = 598$ 周期。 答：重新组织如上所示，执行上述循环需要 598 个时钟周期。
本文由作者按照 CC BY 4.0 进行授权