第四章家庭作业

前言

CSAPP 的第四章通过 Y86-64 处理器来讲解处理器体系结构，因为其内容非常偏向于硬件，所以内容多且杂，只看书很难把握关键点，通过作者留给我们的 HCL 代码和 Y86-64 模拟器来学习会更好。其实本章内容都比较无趣和繁琐，最大的难点是处理好各种细节。

HCL 代码分为 2 部分，分别用于家庭作业和实验，以下是部分家庭作业的个人答案。

参考这篇博客可以获得测试自己代码的教程

4.53

简要题意：

需要我们为基于PIPE - 的，不使用旁路逻辑的流水线处理器避免所有可能的控制和数据冒险。

可以通过修改 pipe-nobypass.hcl 文件结尾处的流水线控制逻辑实现。

思路分析：

没有旁路逻辑的情况我们的冒险还是可以分为 3 类（其实就是添加了数据冒险无法通过旁路解决的情况）：

数据冒险，也就是在译码阶段发现取出的寄存器中有尚未完成写回的，这就要我们暂停取值和译码阶段，同时不断往执行阶段插入气泡直到完成写回为止。发生条件为 (d_srcA != RNONE && d_srcA in{ e_dstE, E_dstM, M_dstM, M_dstE, W_dstM, W_dstE }) || (d_srcB != RNONE && d_srcB in{ e_dstE, E_dstM, M_dstM, M_dstE, W_dstM, W_dstE }) 。一个易错点就是忽略了 d_srcA 和集合中的信号同时为 RNONE 的情况，所以需要加上 d_srcA != RNONE 的判断。
ret 指令，同书上的处理方法，暂停取指阶段同时往译码阶段插入气泡直到能确定下一条指令的地址为止。发生条件为 IRET in{ D_icode, E_icode, M_icode 。值得一提就是当 IRET == W_icode 时，我们就可以通过 W_valM 来获取下一条指令地址了，所以不会引起冒险。
预测错误，同书上的处理方法，往译码阶段和执行阶段分别插入一个气泡即可。发生条件为 E_icode == IJXX && !e_Cnd 。同样值得指出的是我们只需要分别插入一个气泡，然后通过 M_valA 获得下一条指令地址。

然后需要考虑以上情况的组合，仔细分析的只有如下的几种情况。

第一种就是 ret 指令在译码阶段发现 %rsp 还尚未写回。

    irmovq $0x100,%rsp
    ret

这种会同时对译码阶段暂停和插入气泡，分析可知只需要暂停译码阶段。

第二种是预测错误和数据冒险在一个时钟周期同时发生。

    movq $0x0,%rax
    jne test
    halt
test:
    rrmovq %rax,%rbx

这种会同时对译码阶段暂停和插入气泡，分析可知只需要在译码阶段插入气泡。

分析以上 2 种可以得知，预测错误的有限级应该是最高的，其次是数据冒险，最后是 ret 。

大致按照这个逻辑去写 HCL 代码就没问题。

参考答案

bool F_bubble = 0;

bool F_stall =
(d_srcA != RNONE && d_srcA in{ e_dstE, E_dstM, M_dstE, M_dstM, W_dstE, W_dstM }) ||
(d_srcB != RNONE && d_srcB in{ e_dstE, E_dstM, M_dstE, M_dstM, W_dstE ,W_dstM }) ||
IRET in{ D_icode, E_icode, M_icode };

bool D_stall = 
!(E_icode == IJXX && !e_Cnd) &&
((d_srcA != RNONE && d_srcA in{ e_dstE, E_dstM, M_dstM, M_dstE, W_dstM, W_dstE }) ||
(d_srcB != RNONE && d_srcB in{ e_dstE, E_dstM, M_dstM, M_dstE, W_dstM, W_dstE }));

bool D_bubble =
(E_icode == IJXX && !e_Cnd) ||
(IRET in{ D_icode, E_icode, M_icode } && !((d_srcA != RNONE && d_srcA in{ e_dstE, E_dstM, M_dstM, M_dstE, W_dstM, W_dstE }) || (d_srcB != RNONE && d_srcB in{ e_dstE, E_dstM, M_dstM, M_dstE, W_dstM, W_dstE })));

bool E_stall = 0;

bool E_bubble =
(E_icode == IJXX && !e_Cnd) ||
(d_srcA != RNONE && d_srcA in{ e_dstE, E_dstM, M_dstM, M_dstE, W_dstM, W_dstE }) ||
(d_srcB != RNONE && d_srcB in{ e_dstE, E_dstM, M_dstM, M_dstE, W_dstM, W_dstE });

注：有一些暂停有没有都行，比如上面的第二种组合，或者是 ret 和预测错误组合，预测错误不会对取指阶段有操作，但另一种情况会暂停取指阶段，这时你暂停或者不暂停都可以，参考答案中选择了不暂停，代码好写一点。

4.55

简要题意：

文件 pipe-nt.hcl 包含一份 PIPE 的 HCL 描述，要求修改分支预测逻辑，使之对条件转移预测为不选择分支，而对无条件转移和 call 预测为选择分支。

思路分析：

总体难度没有 4.53 大，对比原本的实现分析一下就会了，但是有很多细微之处都需要改动，接下来会一一分析。

分支预测，按照要求直接修改即可。

word f_predPC = [
-       f_icode in { IJXX, ICALL } : f_valC;
+       f_icode == IJXX && f_ifun == 0 : f_valC;
+       f_icode in { ICALL } : f_valC;
        1 : f_valP;
];

预测错误时，需要能转发正确的地址给分支选择。因为正确地址放在指令的常数字段，所以我们需要修改执行阶段的加法来保留正确地址。

word aluA = [
        E_icode in { IRRMOVQ, IOPQ } : E_valA;
-       E_icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ} : E_valC;
+       E_icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX } : E_valC;
        E_icode in { ICALL, IPUSHQ } : -8;
        E_icode in { IRET, IPOPQ } : 8;
];

word aluB = [
        E_icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL,
                     IPUSHQ, IRET, IPOPQ } : E_valB;
-       E_icode in { IRRMOVQ, IIRMOVQ} : 0;
+       E_icode in { IRRMOVQ, IIRMOVQ, IJXX } : 0;
];

这样修改之后，正确指令地址就会存放在 M_valE 中。

预测错误选择指令时，根据上面确定的正确指令地址修改即可，注意此时预测错误的条件是 M_icode == IJXX && M_ifun != 0 && M_Cnd 。

word f_pc = [
-       M_icode == IJXX && !M_Cnd : M_valA;
+       M_icode == IJXX && M_ifun != 0 && M_Cnd : M_valE;
        W_icode == IRET : W_valM;
        1 : F_predPC;
];

对于气泡和暂停，我们也只需要修改预测错误的条件即可。

bool D_bubble =
-        (E_icode == IJXX && !e_Cnd) ||
+        (E_icode == IJXX && E_ifun != 0 && e_Cnd) ||
        !(E_icode in { IMRMOVQ, IPOPQ } && E_dstM in { d_srcA, d_srcB }) &&
          IRET in { D_icode, E_icode, M_icode };

bool E_bubble =
-       (E_icode == IJXX && !e_Cnd) ||  
+       (E_icode == IJXX && E_ifun != 0 && e_Cnd) ||
         E_icode in { IMRMOVQ, IPOPQ } &&
         E_dstM in { d_srcA, d_srcB};

PS：因为学艺不精，4.53 我前前后后 2 天花了 10 小时，而 4.55 只花了 30 分钟。

4.56

简要题意：

文件 pipe-btfnt.hcl 包含一份 PIPE 的 HCL 描述，要求修改分支预测逻辑，对于条件转移，当 \(ValC < ValP\) 时，预测为选择分支，当 \(ValC \geq ValP\) 时，预测为不选择分支，而对无条件转移和 call ，预测为选择分支。

思路分析：

需要修改的位置和上一题完全一致，只需要额外增加一些分类讨论即可。

分支预测，额外增加一种情况。

word f_predPC = [
-       f_icode in { IJXX, ICALL } : f_valC;
+       f_icode == IJXX && f_ifun == 0 : f_valC;
+       f_icode == IJXX && f_valC < f_valP : f_valC;
+       f_icode == ICALL : f_valC;
        1 : f_valP;
];

同上题完全一致。

word aluA = [
        E_icode in { IRRMOVQ, IOPQ } : E_valA;
-       E_icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ} : E_valC;
+       E_icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX } : E_valC;
        E_icode in { ICALL, IPUSHQ } : -8;
        E_icode in { IRET, IPOPQ } : 8;
];

word aluB = [
        E_icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL,
                     IPUSHQ, IRET, IPOPQ } : E_valB;
-       E_icode in { IRRMOVQ, IIRMOVQ} : 0;
+       E_icode in { IRRMOVQ, IIRMOVQ, IJXX } : 0;
];

预测错误选择指令时，分两类即可，注意 M_valE 中是 valC ，M_valA 中是 valP 。

word f_pc = [
-       M_icode == IJXX && !M_Cnd : M_valA;
+       M_icode == IJXX && !M_Cnd && M_valE < M_valA : M_valA;
+       M_icode == IJXX && M_ifun != 0 && M_Cnd && M_valE >= M_valA : M_valE;
        W_icode == IRET : W_valM;
        1 : F_predPC;
];

修改预测错误的条件为 E_icode == IJXX && !e_Cnd && E_valC < E_valA || E_icode == IJXX && E_ifun != 0 && e_Cnd && E_valC >= E_valA 即可。

bool D_bubble =
-        (E_icode == IJXX && !e_Cnd) ||
+         E_icode == IJXX && !e_Cnd && E_valC < E_valA || 
+         E_icode == IJXX && E_ifun != 0 && e_Cnd && E_valC >= E_valA ||
        !(E_icode in { IMRMOVQ, IPOPQ } && E_dstM in { d_srcA, d_srcB }) &&
          IRET in { D_icode, E_icode, M_icode };

bool E_bubble =
-       (E_icode == IJXX && !e_Cnd) ||  
+         E_icode == IJXX && !e_Cnd && E_valC < E_valA || 
+         E_icode == IJXX && E_ifun != 0 && e_Cnd && E_valC >= E_valA ||
         E_icode in { IMRMOVQ, IPOPQ } &&
         E_dstM in { d_srcA, d_srcB};

4.57

简要题意：

修改 pipe-lf.hcl 的 HCL 描述以实现加载转发。加载转发的定义见原题干。

思路分析：

根据加载转发的定义，只有 mrmovq 或 popq 指令后接 pushq 或 rmmovq 才有可能使用加载转发来避免加载/使用冒险，而且要保证被赋值的寄存器在 rmmovq 中不用来寻址，只是单纯地写入内存。

因为 mrmovq 用来寻址的寄存器是 rB ，所以使用加载转发后，加载/使用冒险的条件为 E_icode in { IMRMOVQ, IPOPQ } && (d_srcB == E_dstM || d_srcA == E_dstM && !(D_icode in {IRMMOVQ, IPUSHQ}))。

代码很好写，只需要完成执行阶段的 e_valA 的逻辑，同时修改暂停和气泡处的加载/使用冒险条件即可。

参考答案

word e_valA = [
        M_icode in {IMRMOVQ, IPUSHQ} && M_dstM == E_srcA : m_valM;
        1 : E_valA;  
];

bool F_stall =
        E_icode in { IMRMOVQ, IPOPQ } &&
       (d_srcB == E_dstM || d_srcA == E_dstM && !(D_icode in {IRMMOVQ, IPUSHQ})) ||
        IRET in { D_icode, E_icode, M_icode };

 bool D_stall =
        E_icode in { IMRMOVQ, IPOPQ } &&
       (d_srcB == E_dstM || d_srcA == E_dstM && !(D_icode in {IRMMOVQ, IPUSHQ}));

bool E_bubble =
        (E_icode == IJXX && !e_Cnd) ||
        E_icode in { IMRMOVQ, IPOPQ } &&
        (d_srcB == E_dstM || d_srcA == E_dstM && !(D_icode in {IRMMOVQ, IPUSHQ}));

注：因为 ret 指令需要使用寄存器 %rsp 寻址，所以加载转发不会对加载/使用冒险和 ret 的组合有影响。

4.58

简要题意：

寄存器文件的两写入端口在大多数情况会闲置一个，所以我们将 2 种写入合并为 1 种，只使用一个写入端口，对于指令 popq 的处理，采用拆成如下 2 个指令的思路。

iaddq $8, %rsp
mrmovq -8(%rsp), rA

修改 pipe-1w.hcl 的控制逻辑，使之按照要求处理 popq 指令。

思路分析：

对于 iaddq 指令的实现，在实验 4 中有所涉及，这里不赘述。

按照题目给的提示，实现上，第一次取出 popq 指令，预测下一个 PC 和下一个 PC 相等，第二次取出 popq 指令需要将指令修改为 IPOP2 。就相当于先完成 POPQ 的解析，然后再分别重新实现两条指令。第一点的实现，可以选择暂停取指寄存器或者直接让 f_predPC 多一个 f_pc 的选项，第二点的实现直接当 D_icode == IPOPQ 时对 f_icode 特判即可。

要改的地方很多，但都不难理解，直接放对比图了，唯一可能会遗漏就是加载/使用冒险条件的 IPOPQ 得改为 IPOP2。

参考答案

word f_icode = [
        imem_error : INOP;
+       D_icode == IPOPQ : IPOP2;
        1: imem_icode;
];

bool instr_valid = f_icode in
        { INOP, IHALT, IRRMOVQ, IIRMOVQ, IRMMOVQ, IMRMOVQ,
-         IOPQ, IJXX, ICALL, IRET, IPUSHQ, IPOPQ };
+         IOPQ, IJXX, ICALL, IRET, IPUSHQ, IPOPQ, IPOP2 };

bool need_regids =
        f_icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ,
-                    IIRMOVQ, IRMMOVQ, IMRMOVQ };
+                    IIRMOVQ, IRMMOVQ, IMRMOVQ, IPOP2 };

word f_predPC = [
        f_icode in { IJXX, ICALL } : f_valC;
+       f_icode == IPOPQ : f_pc;
        1 : f_valP;
];

word d_srcA = [
        D_icode in { IRRMOVQ, IRMMOVQ, IOPQ, IPUSHQ  } : D_rA;
-       D_icode in { IRET, IPOPQ } : RRSP;
+       D_icode in { IRET } : RRSP;
        1 : RNONE; 
];

word d_srcB = [
        D_icode in { IOPQ, IRMMOVQ, IMRMOVQ  } : D_rB;
-       D_icode in { IPUSHQ, IPOPQ, ICALL, IRET, IPOPQ } : RRSP;
+       D_icode in { IPUSHQ, IPOPQ, ICALL, IRET, IPOPQ, IPOP2 } : RRSP;
        1 : RNONE; 
];

word d_dstM = [
-   D_icode in { IMRMOVQ, IPOPQ } : D_rA;
+   D_icode in { IMRMOVQ, IPOP2 } : D_rA;
    1 : RNONE;  # Don't write any register
];

word aluA = [
        E_icode in { IRRMOVQ, IOPQ } : E_valA;
        E_icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ } : E_valC;
-       E_icode in { ICALL, IPUSHQ } : -8;
+       E_icode in { ICALL, IPUSHQ, IPOP2 } : -8;
        E_icode in { IRET, IPOPQ } : 8;
        # Other instructions don't need ALU
];

word aluB = [
        E_icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL,
-                    IPUSHQ, IRET, IPOPQ, IPOPQ } : E_valB;
+                    IPUSHQ, IRET, IPOPQ, IPOP2 } : E_valB;
        E_icode in { IRRMOVQ, IIRMOVQ } : 0;
        # Other instructions don't need ALU
];

word mem_addr = [
-       M_icode in { IRMMOVQ, IPUSHQ, ICALL, IMRMOVQ } : M_valE;
-       M_icode in { IRET, IPOPQ } : M_valA;
+       M_icode in { IRMMOVQ, IPUSHQ, ICALL, IMRMOVQ, IPOP2 } : M_valE;
+       M_icode in { IRET } : M_valA;
        # Other instructions don't need address
];

- bool mem_read = M_icode in { IMRMOVQ, IPOPQ, IRET };
+ bool mem_read = M_icode in { IMRMOVQ, IPOP2, IRET };

bool F_stall =
-       E_icode in { IMRMOVQ, IPOPQ } &&
+       E_icode in { IMRMOVQ, IPOP2 } &&
        E_dstM in { d_srcA, d_srcB } ||
        IRET in { D_icode, E_icode, M_icode };

bool D_stall =
-       E_icode in { IMRMOVQ, IPOPQ } &&
+       E_icode in { IMRMOVQ, IPOP2 } &&
        E_dstM in { d_srcA, d_srcB };

bool D_bubble =
        (E_icode == IJXX && !e_Cnd) ||
-       !(E_icode in { IMRMOVQ, IPOPQ } && E_dstM in { d_srcA, d_srcB }) &&
+       !(E_icode in { IMRMOVQ, IPOP2 } && E_dstM in { d_srcA, d_srcB }) &&
        IRET in { D_icode, E_icode, M_icode };

bool E_bubble =
        (E_icode == IJXX && !e_Cnd) ||
-        E_icode in { IMRMOVQ, IPOPQ } &&
+        E_icode in { IMRMOVQ, IPOP2 } &&
         E_dstM in { d_srcA, d_srcB};

后记

现在是 2024 年 12 月 31 日，我完成了第四章对我有价值的部分作业。本来不想写这玩意，感觉太矫情，不过时间有点特殊，留个纪念也好。自从搭建个人网页以来才感觉找到点有意义的事，此前差不多是半颓废的状态吧，从成都回来，两个月了都，大部分周日我都摊在床上看一整天 ICPC 直播，有些东西确实得靠时间来淡化。