# 习题（Diana Franklin 修订） ### 习题 C.1 {#exercise-c-1} **[15/15/15/15/25/10/15]〈A.2〉** 使用下面的代码片段： ~~~asm Loop: ld x1,0(x2) ; 从地址 0+x2 加载到 x1 addi x1,x1,1 ; x1=x1+1 sd x1,0,(x2) ; 将 x1 存入地址 0+x2 addi x2,x2,4 ; x2=x2+4 sub x4,x3,x2 ; x4=x3-x2 bnez x4,Loop ; 若 x4!=0，则跳转到 Loop ~~~ 假定 `x3` 的初值等于 `x2+396`。 > 译注：题首的章节引用 `A.2`、`sd x1,0,(x2)` 中多出的逗号，以及 64 位加载、存储配合步长 4 的组合，均为原题所写，未在译文中静默改动。 a. **[15]〈C.2〉** 数据冒险源于代码中的数据依赖。依赖关系是否构成冒险，取决于机器实现，例如流水线级数。列出上述代码中的所有数据依赖，记录寄存器、产生数据的指令和使用数据的指令。例如，`ld` 与 `addi` 之间存在关于 `x1` 的数据依赖。 b. **[15]〈C.2〉** 给出该序列在五级 RISC 流水线上的时序。假定没有任何转发或旁路硬件，但同一周期内的寄存器写入与读取可以经寄存器堆实现“转发”，如图 C.5 中 `add` 与 `or` 的关系。使用类似图 C.8 的时序表。假定通过清空流水线处理分支，所有存储器访问都需一周期。整个循环执行需要多少周期？ c. **[15]〈C.2〉** 给出该序列在具有完整转发与旁路硬件的五级 RISC 流水线上的时序，使用类似图 C.8 的表。假定预测分支不跳转，所有存储器访问都需一周期。整个循环执行需要多少周期？ d. **[15]〈C.2〉** 给出该序列在图 C.6 所示、具有完整转发与旁路硬件的五级 RISC 流水线上的时序，使用类似图 C.8 的表。假定预测分支跳转，所有存储器访问都需一周期。整个循环执行需要多少周期？ e. **[25]〈C.2〉** 高性能处理器的流水线很深，可以超过 15 级。设想一条十级流水线，将原五级流水线的每一级拆成两级。唯一需要注意的是：转发从一对阶段的末端，送到需要该数据的另一对阶段的开头。例如，从第二个执行阶段的输出转发到第一个执行阶段的输入，仍会造成一周期延迟。给出该序列在具有完整转发与旁路硬件的十级 RISC 流水线上的时序，使用类似图 C.8 的表，但各级标作 IF1、IF2、ID1 等。假定预测分支跳转，所有存储器访问都需一周期。整个循环执行需要多少周期？ f. **[10]〈C.2〉** 假定五级流水线中最慢的阶段需要 0.8 ns，流水线寄存器延迟为 0.1 ns。五级流水线的时钟周期是多少？如果十级流水线将每一级的逻辑均分为两半，它的时钟周期是多少？ g. **[15]〈C.2〉** 利用 (d)、(e) 的答案，求五级与十级流水线执行该循环时的 CPI。只从第一条指令到达写回阶段时开始计数，直到循环结束；不计第一条指令启动流水线的时间。再利用 (f) 求得的时钟周期，计算两台机器的平均指令执行时间。 ### 习题 C.2 {#exercise-c-2} **[15/15]〈C.2〉** 假定分支频率如下，前两项按全部指令计： | 类型 | 频率 | |---|---:| | 条件分支 | 15% | | 跳转与调用 | 1% | | 条件分支中实际跳转的比例 | 60% | a. **[15]〈C.2〉** 考察四级流水线：无条件分支在第二周期末确定，条件分支在第三周期末确定。假定只有第一级总能在不知道分支是否跳转的情况下完成，忽略其他停顿。如果完全没有分支冒险，机器的性能会提高到原来的多少倍？ b. **[15]〈C.2〉** 现在考虑高性能处理器的十五级流水线：无条件分支在第五周期末确定，条件分支在第十周期末确定。仍假定只有第一级总能独立于分支是否跳转而完成，并忽略其他停顿。如果完全没有分支冒险，性能会提高到原来的多少倍？ ### 习题 C.3 {#exercise-c-3} **[5/15/10/10]〈C.2〉** 从一台单周期实现的计算机出发，按功能拆分阶段时，各阶段所需时间并不完全相同。原机器的时钟周期为 7 ns；拆分后的测量值为：IF 1 ns、ID 1.5 ns、EX 1 ns、MEM 2 ns、WB 1.5 ns。流水线寄存器延迟为 0.1 ns。 a. **[5]〈C.2〉** 五级流水线机器的时钟周期是多少？ b. **[15]〈C.2〉** 如果每四条指令发生一次停顿，新机器的 CPI 是多少？ c. **[10]〈C.2〉** 流水线机器相对于单周期机器的加速比是多少？ d. **[10]〈C.2〉** 如果流水线有无限多个阶段，相对于单周期机器的加速比是多少？ ### 习题 C.4 {#exercise-c-4} **[15]〈C.1、C.2〉** 经典五级 RISC 流水线的一种精简硬件实现，可以使用 EX 阶段硬件完成分支比较，并且直到分支指令到达 MEM 的那个周期，才把目标 PC 送到 IF。在 ID 中解析分支能够减少控制冒险停顿，但某一方面的改进可能损害其他情况下的性能。写出一小段代码，说明即使具有数据转发，在 ID 中计算分支仍会造成数据冒险。 ### 习题 C.5 {#exercise-c-5} **[12/13/20/20/15/15]〈C.2、C.3〉** 本题考察寄存器—存储器体系结构的流水线。该体系结构有寄存器—寄存器和寄存器—存储器两种格式，存储器寻址方式只有一种：偏移量加基址寄存器。ALU 操作格式如下： ~~~text ALUop Rdest, Rsrc1, Rsrc2 ~~~ 或 ~~~text ALUop Rdest, Rsrc1, MEM ~~~ `ALUop` 可以是加、减、AND、OR、加载（忽略 `Rsrc1`）或存储；`Rsrc`、`Rdest` 是寄存器，`MEM` 是基址寄存器与偏移量的组合。分支对两个寄存器进行完整比较，并采用 PC 相对寻址。假定机器每周期启动一条新指令，其流水线与 VAX 8700 微流水线相似（Clark，1987）： | 指令 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |---|---|---|---|---|---|---|---|---|---|---|---| | 1 | IF | RF | ALU1 | MEM | ALU2 | WB | | | | | | | 2 | | IF | RF | ALU1 | MEM | ALU2 | WB | | | | | | 3 | | | IF | RF | ALU1 | MEM | ALU2 | WB | | | | | 4 | | | | IF | RF | ALU1 | MEM | ALU2 | WB | | | | 5 | | | | | IF | RF | ALU1 | MEM | ALU2 | WB | | | 6 | | | | | | IF | RF | ALU1 | MEM | ALU2 | WB | 第一个 ALU 阶段用于访存和分支的有效地址计算；第二个用于运算和分支比较。RF 同时完成译码与寄存器读取。假定同一时钟周期内对同一寄存器的读写，可以把写入数据转发给读取方。 a. **[12]〈C.2〉** 求所需加法器总数，包括任何加法器或递增器。给出指令与流水级的组合以证明答案；只需给出一种使加法器需求达到最大的组合。 b. **[13]〈C.2〉** 求所需寄存器读、写端口和存储器读、写端口数。给出指令与流水级的组合，并标明各条指令所需读、写端口数，以证明答案正确。 c. **[20]〈C.3〉** 找出 ALU 所需的全部数据转发。假定 ALU1 与 ALU2 使用不同的 ALU，补齐为避免或减少停顿所需的 ALU 间转发。用图 C.23 的表格格式，但忽略最后两列，描述参与转发的两条指令之间的关系。注意考虑中间隔有另一条指令的情况，例如： ~~~text add x1, … 任意指令 add …, x1, … ~~~ d. **[20]〈C.3〉** 当源单元或目的单元不是 ALU 时，列出避免或减少停顿所需的全部转发。仍采用图 C.23 的格式，忽略最后两列。不要漏掉传向访存操作及由访存操作传出的转发。 e. **[15]〈C.3〉** 列出所有剩余冒险，其中至少一个源或目的单元不是 ALU。使用类似图 C.25 的表，但把最后一列改为冒险持续长度。 f. **[15]〈C.2〉** 用例子列出全部控制冒险，并说明停顿长度。采用类似图 C.11 的格式，为每个例子加上标签。 ### 习题 C.6 {#exercise-c-6} **[12/13/13/15/15]〈C.1、C.2、C.3〉** 现在为经典五级 RISC 流水线加入寄存器—存储器 ALU 操作。为抵消复杂度增加，将所有存储器寻址限制为寄存器间接寻址：地址就是某个寄存器的值，不允许再加偏移或位移。例如，`add x4,x5,(x1)` 将 `x5` 的内容与地址等于 `x1` 的存储单元内容相加，并把结果放入 `x4`。寄存器—寄存器 ALU 操作不变。以下问题均针对整数 RISC 流水线。 a. **[12]〈C.1〉** 重新排列传统五个阶段，使之支持仅通过寄存器间接寻址实现的寄存器—存储器操作，写出阶段次序。 b. **[13]〈C.2、C.3〉** 说明重排后需要哪些新的转发路径，并给出每条路径的源、目的和所传输的信息。 c. **[13]〈C.2、C.3〉** 阶段重排后，这种寻址方式产生哪些新的数据冒险？为每种新冒险给出一段指令序列。 d. **[15]〈C.3〉** 对于同一程序，支持寄存器—存储器 ALU 操作的流水线，可能通过哪些方式改变相对于原流水线的指令数？逐项列出，并各给一对具体序列：一段用于原流水线，一段用于重排后的流水线。 e. **[15]〈C.3〉** 假定所有指令在每个阶段都耗费一周期。对于同一程序，这种寄存器—存储器 RISC-V 相对于原流水线，可能通过哪些方式产生不同的 CPI？全部列出。 ### 习题 C.7 {#exercise-c-7} **[10/10]〈C.3〉** 本题研究加深流水线影响性能的两个方面：时钟周期缩短，以及数据、控制冒险停顿增加。原机器采用五级流水线，时钟周期 1 ns；第二台机器采用十二级流水线，时钟周期 0.6 ns。五级流水线每五条指令因数据冒险发生一次停顿，十二级流水线每八条发生三次。此外，分支占指令的 20%，两台机器的分支误预测率均为 5%。 a. **[10]〈C.3〉** 仅考虑数据冒险，十二级流水线相对于五级的加速比是多少？ b. **[10]〈C.3〉** 若第一台机器的分支误预测代价为两周期，第二台为五周期，计入误预测停顿后，两台机器各自的 CPI 是多少？ ### 习题 C.8 {#exercise-c-8} **[15]〈C.5〉** 构造类似图 C.21 的表，用于检查图 C.30 的 RISC-V 浮点流水线中的 WAW 停顿。不考虑浮点除法。 ### 习题 C.9 {#exercise-c-9} **[20/22/22]〈C.4、C.6〉** 本题考察一个常见向量循环在静态和动态调度的 RISC-V 流水线上的运行。它就是附录 G 详细讨论的 DAXPY 循环，也是高斯消元的核心操作。对于长度为 100 的向量，循环实现 \(Y=aX+Y\)。原题给出的代码如下，并称其为 MIPS 代码： ~~~asm foo: fld f2,0(x1) ; 加载 X(i) fmul.d f4,f2,f0 ; 计算 a*X(i) fld f6,0(x2) ; 加载 Y(i) fadd.d f6,f4,f6 ; 计算 a*X(i)+Y(i) fsd 0(x2),f6 ; 存储 Y(i) addi x1,x1,8 ; 递增 X 的下标 addi x2,x2,8 ; 递增 Y 的下标 sltiu x3,x1,done ; 检查是否完成 bnez x3,foo ; 若未完成则循环 ~~~ > 译注：原题混用了 MIPS 名称与 RISC-V 风格记号；`fsd` 的操作数次序也与前文 `fsd f2,0(x2)` 不同。题首分值为 `[20/22/22]`，各小题实际均标 `[20]`，也照录。 对 (a)–(c)，假定整数操作（包括加载）在一周期内发射并完成，其结果具有完整旁路。浮点运算只采用图 C.29 中的延迟值，但假定浮点单元完全流水线化。对于记分牌，假定等待另一个功能单元结果的指令，可在结果写入的同一周期通过读操作数阶段；另外，一条指令完成 WB 的同一周期，也允许正在等待该功能单元的另一条活动指令发射。 a. **[20]〈C.5〉** 使用 C.5 节的 RISC-V 流水线，延迟取图 C.29 的值，但浮点单元完全流水线化，启动间隔为 1。绘制类似图 C.32 的时序图，显示每条指令的执行。每次循环迭代，从第一条指令进入 WB 到最后一条进入 WB，需要多少时钟周期？ b. **[20]〈C.8〉** 静态重排指令，使该循环的停顿最少；必要时重命名寄存器。其余假定同 (a)。绘制类似图 C.32 的时序图。每次迭代从第一条指令进入 WB 到最后一条进入 WB，需要多少周期？ c. **[20]〈C.8〉** 使用上面的原始代码，考虑通过动态调度的一种形式——记分牌——执行。绘制类似图 C.32 的图，显示指令经过 IF、IS（发射）、RO（读操作数）、EX（执行）、WR（写结果）的时序。每次迭代从第一条指令进入 WB 到最后一条进入 WB，需要多少周期？题目最后的 WB 与本小题列出的 WR 对应。 ### 习题 C.10 {#exercise-c-10} **[25]〈C.8〉** 记分牌必须能够区分 RAW 与 WAR 冒险，这一点至关重要：WAR 冒险要求暂停写入指令，直到读取操作数的指令开始执行；RAW 冒险则相反，要求延迟读取指令，直到写入指令完成。例如： ~~~asm fmul.d f0,f6,f4 fsub.d f8,f0,f2 fadd.d f2,f10,f2 ~~~ `fsub.d` 依赖 `fmul.d`，构成 RAW 冒险，所以必须允许 `fmul.d` 先于 `fsub.d` 完成。如果不能区分 RAW 与 WAR，而让 `fmul.d` 等待 `fsub.d`，处理器就会死锁。这一序列中，`fadd.d` 与 `fsub.d` 之间又有 WAR 冒险，因此在 `fsub.d` 开始执行之前，不能允许 `fadd.d` 完成。难点在于区分 `fmul.d` 与 `fsub.d` 之间的 RAW，以及 `fsub.d` 与 `fadd.d` 之间的 WAR。 为了理解为什么这个三指令场景很重要，请逐步跟踪每条指令的发射、读操作数、执行和写结果。假定除执行外，记分牌每步都耗费一周期；`fmul.d` 执行需三周期，`fsub.d` 和 `fadd.d` 各需一周期。处理器有两个乘法功能单元、两个加法功能单元。按如下方法给出跟踪结果： 1. 建立表格，列名为“指令、发射、读操作数、执行、写结果、说明”。第一列按程序顺序列指令，行间多留空间，较大的单元格便于填写分析结果。在 `fmul.d` 行的“发射”列填 1，表示它在周期 1 完成发射。继续填写各阶段，直到记分牌第一次让某条指令停顿的周期。 2. 对停顿指令，在相应列写“在时钟周期 X 等待”，X 为当前周期号，表示记分牌通过暂停该阶段来处理 RAW 或 WAR 冒险。在“说明”列写明冒险类型，以及哪条相关指令造成等待。 3. 在“等待”单元格中补上“于时钟周期 Y 完成”，填完余下表格，直到所有指令完成。对发生过停顿的指令，在“说明”中解释等待为何在那个时刻结束，以及如何避免死锁。提示：思考如何防止 WAW 冒险，以及这对活动指令序列意味着什么。比较三条指令的完成次序与程序次序。 ### 习题 C.11 {#exercise-c-11} **[10/10/10]〈C.5〉** 编写若干短代码片段，说明使用不同延迟的功能单元会遇到的问题。每种情况都绘制类似图 C.32 的时序图，展示相应概念，并清楚指出问题。 a. **[10]〈C.5〉** 使用不同于图 C.32 的代码，说明只有一份 MEM 和 WB 阶段硬件时产生的结构冒险。 b. **[10]〈C.5〉** 给出一个必须停顿的 WAW 冒险例子。 > 译注：原题题首列出三项分值 `[10/10/10]`，但原书附录 C 的最后一页只列出 (a)、(b) 两问；下一页已进入附录 D。题内章节引用中，C.8 被用于记分牌相关题目，虽然正文记分牌实际在 C.7；这些引用保留原题写法。