习题（Diana Franklin 修订）

习题 C.1

[15/15/15/15/25/10/15]〈A.2〉 使用下面的代码片段：

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

[15/15]〈C.2〉 假定分支频率如下，前两项按全部指令计：

类型	频率
条件分支	15%
跳转与调用	1%
条件分支中实际跳转的比例	60%

a. [15]〈C.2〉 考察四级流水线：无条件分支在第二周期末确定，条件分支在第三周期末确定。假定只有第一级总能在不知道分支是否跳转的情况下完成，忽略其他停顿。如果完全没有分支冒险，机器的性能会提高到原来的多少倍？

b. [15]〈C.2〉 现在考虑高性能处理器的十五级流水线：无条件分支在第五周期末确定，条件分支在第十周期末确定。仍假定只有第一级总能独立于分支是否跳转而完成，并忽略其他停顿。如果完全没有分支冒险，性能会提高到原来的多少倍？

习题 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

[15]〈C.1、C.2〉 经典五级 RISC 流水线的一种精简硬件实现，可以使用 EX 阶段硬件完成分支比较，并且直到分支指令到达 MEM 的那个周期，才把目标 PC 送到 IF。在 ID 中解析分支能够减少控制冒险停顿，但某一方面的改进可能损害其他情况下的性能。写出一小段代码，说明即使具有数据转发，在 ID 中计算分支仍会造成数据冒险。

习题 C.5

[12/13/20/20/15/15]〈C.2、C.3〉 本题考察寄存器—存储器体系结构的流水线。该体系结构有寄存器—寄存器和寄存器—存储器两种格式，存储器寻址方式只有一种：偏移量加基址寄存器。ALU 操作格式如下：

ALUop Rdest, Rsrc1, Rsrc2

或

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 的表格格式，但忽略最后两列，描述参与转发的两条指令之间的关系。注意考虑中间隔有另一条指令的情况，例如：

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

[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

[10/10]〈C.3〉 本题研究加深流水线影响性能的两个方面：时钟周期缩短，以及数据、控制冒险停顿增加。原机器采用五级流水线，时钟周期 1 ns；第二台机器采用十二级流水线，时钟周期 0.6 ns。五级流水线每五条指令因数据冒险发生一次停顿，十二级流水线每八条发生三次。此外，分支占指令的 20%，两台机器的分支误预测率均为 5%。

a. [10]〈C.3〉 仅考虑数据冒险，十二级流水线相对于五级的加速比是多少？

b. [10]〈C.3〉 若第一台机器的分支误预测代价为两周期，第二台为五周期，计入误预测停顿后，两台机器各自的 CPI 是多少？

习题 C.8

[15]〈C.5〉 构造类似图 C.21 的表，用于检查图 C.30 的 RISC-V 浮点流水线中的 WAW 停顿。不考虑浮点除法。

习题 C.9

[20/22/22]〈C.4、C.6〉 本题考察一个常见向量循环在静态和动态调度的 RISC-V 流水线上的运行。它就是附录 G 详细讨论的 DAXPY 循环，也是高斯消元的核心操作。对于长度为 100 的向量，循环实现 $Y=aX+Y$ 。原题给出的代码如下，并称其为 MIPS 代码：

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

[25]〈C.8〉 记分牌必须能够区分 RAW 与 WAR 冒险，这一点至关重要：WAR 冒险要求暂停写入指令，直到读取操作数的指令开始执行；RAW 冒险则相反，要求延迟读取指令，直到写入指令完成。例如：

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 各需一周期。处理器有两个乘法功能单元、两个加法功能单元。按如下方法给出跟踪结果：

建立表格，列名为“指令、发射、读操作数、执行、写结果、说明”。第一列按程序顺序列指令，行间多留空间，较大的单元格便于填写分析结果。在 fmul.d 行的“发射”列填 1，表示它在周期 1 完成发射。继续填写各阶段，直到记分牌第一次让某条指令停顿的周期。

对停顿指令，在相应列写“在时钟周期 X 等待”，X 为当前周期号，表示记分牌通过暂停该阶段来处理 RAW 或 WAR 冒险。在“说明”列写明冒险类型，以及哪条相关指令造成等待。
在“等待”单元格中补上“于时钟周期 Y 完成”，填完余下表格，直到所有指令完成。对发生过停顿的指令，在“说明”中解释等待为何在那个时刻结束，以及如何避免死锁。提示：思考如何防止 WAW 冒险，以及这对活动指令序列意味着什么。比较三条指令的完成次序与程序次序。

习题 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；这些引用保留原题写法。