# 习题 作者：Jason D. Bakos。 ### 习题 3.12 {#exercise-3-12} **[25] 〈3.11〉** 本题探讨三种采用不同多线程（MT）方式的处理器之间的性能取舍。它们都是超标量处理器，采用顺序流水线，所有加载与分支之后都必须固定停顿 3 个周期，且具有相同的 L1 缓存。同一线程在同一周期发射的指令，按程序顺序读取，彼此不能存在任何数据依赖或控制依赖。 应用是一个列表搜索程序，在 x16 与 x17 指定的地址范围内扫描内存区域，寻找保存在 x9 中的特定值。将搜索空间均分为四个大小相等、各自连续的块，每块分配一个搜索线程，从而并行化为四个线程。每个线程的大部分运行时间都花在以下展开后的循环体中： ~~~asm loop: lw x1,0(x16) lw x2,8(x16) lw x3,16(x16) lw x4,24(x16) lw x5,32(x16) lw x6,40(x16) lw x7,48(x16) lw x8,56(x16) beq x9,x1,match0 beq x9,x2,match1 beq x9,x3,match2 beq x9,x4,match3 beq x9,x5,match4 beq x9,x6,match5 beq x9,x7,match6 beq x9,x8,match7 daddiu x16,x16,#64 blt x16,x17,loop ~~~ 假定： - 用屏障保证所有线程同时开始。 - 第一次 L1 缓存未命中发生在循环完成两次迭代之后。 - 所有 BEQAL 分支都不跳转。 - BLT 总是跳转。 - 三种处理器都按轮转方式调度线程。 - 处理器 A 是超标量同时多线程体系结构，每周期最多发射来自两个线程的合计两条指令。 - 处理器 B 是细粒度多线程体系结构，每周期最多从单个线程发射四条指令，遇到任何流水线停顿就切换线程。 - 处理器 C 是粗粒度多线程体系结构，每周期最多从单个线程发射八条指令，在 L1 缓存未命中时切换线程。 求各处理器完成循环前两次迭代所需的周期数。 > 译注：原题假设中的“BEQAL”与代码的 `beq` 不一致，`daddiu` 及 `#64` 写法也是原页内容，均未改写为另一套指令。本题对细粒度切换时机的定义也按题设保留。 ### 习题 3.13 {#exercise-3-13} **[25/25/25] 〈3.1, 3.2, 3.9〉** 本题考察软件技术如何从常见向量循环中开发指令级并行性（ILP）。以下循环称为 DAXPY 循环，即双精度 \(aX+Y\)，是 Gauss 消元中的核心操作。代码对长度为 100 的向量执行 DAXPY：\(Y=aX+Y\)。初始时，R1 设为数组 X 的基地址，R2 设为 Y 的基地址： ~~~asm addi x4,x1,#800 ; x1 = X 的上界 foo: fld F2,0(x1) ; (F2) = X(i) fmul.d F4,F2,F0 ; (F4) = a*X(i) fld F6,0(x2) ; (F6) = Y(i) fadd.d F6,F4,F6 ; (F6) = a*X(i) + Y(i) fsd F6,0(x2) ; Y(i) = a*X(i) + Y(i) addi x1,x1,#8 ; 递增 X 索引 addi x2,x2,#8 ; 递增 Y 索引 sltu x3,x1,x4 ; 测试：是否继续循环？ bnez x3,foo ; 需要时循环 ~~~ > 译注：正文使用 R1、R2，代码使用 x1、x2；第一条指令写入 x4，原注释却写“x1 = 上界”。均按原书保留。 假定功能单元延迟如下表。采用一个周期的延迟分支，在 ID 阶段确定分支结果。所有结果都支持完全旁路。 | 产生结果的指令 | 使用结果的指令 | 延迟（时钟周期） | | --- | --- | ---: | | 浮点乘法 | 浮点 ALU 操作 | 6 | | 浮点加法 | 浮点 ALU 操作 | 4 | | 浮点乘法 | 浮点存储 | 5 | | 浮点加法 | 浮点存储 | 4 | | 整数操作及所有加载 | 任意 | 2 | {.wide .expand} a. **[25]〈3.1〉** 假定单发射流水线。给出未经编译器调度的循环，以及由编译器针对浮点操作延迟和分支延迟进行调度后的循环，标出所有停顿或空闲时钟周期。未经调度和调度后，结果向量 Y 的每个元素分别需要多少执行周期？如果只依靠处理器硬件，时钟需要快多少，才能达到调度编译器带来的性能提升？忽略提高时钟速度对存储系统性能可能产生的影响。 b. **[25]〈3.2〉** 假定单发射流水线。充分展开循环并合并循环开销指令，使其能够在没有任何停顿的情况下调度。必须展开多少次？给出指令调度。每个结果元素的执行时间是多少？ c. **[25]〈3.9〉** 假定 VLIW 处理器的每条指令包含五个操作，如图 3.28 所示。比较两种循环展开程度：先将循环展开 6 次，以开发 ILP，合并循环开销指令，调度到没有任何停顿，即没有发射周期完全空闲；然后重复这一过程，但改为展开 10 次。忽略分支延迟槽。给出两种调度。每种调度下，结果向量每个元素的执行时间是多少？操作槽位的利用率各是多少？两种调度的代码大小相差多少？各自总共需要多少寄存器？ ### 习题 3.14 {#exercise-3-14} **[20/20] 〈3.3, 3.6〉** 本题考察动态调度处理器运行习题 3.13 中循环时的表现。功能单元如下表： | 功能单元类型 | EX 周期数 | 功能单元数量 | 保留站数量 | | --- | ---: | ---: | ---: | | 整数 | 1 | 1 | 5 | | 浮点加法器 | 10 | 1 | 3 | | 浮点乘法器 | 15 | 1 | 2 | {.wide .expand} 假定： - 功能单元没有流水化。 - 功能单元之间没有转发，结果在指令完成时传递。 - 执行阶段 EX 同时完成加载、存储的有效地址计算与内存访问，因此流水线为 IF/ID/DIS/EX/WB。 - 加载需要一个时钟周期。 - 派发阶段 DIS 和结果写回阶段 WB，各需要一个时钟周期。 - 有五个加载缓冲槽位和五个存储缓冲槽位。 - 非零分支指令 BNEZ 需要一个时钟周期。 a. **[20]〈3.3, 3.6〉** 使用单发射流水线，流水线延迟取上表数值。对于循环的三次迭代，给出每条指令的停顿周期数，以及开始执行、即进入第一个 EX 周期的时钟周期。每次循环迭代需要多少个周期？请用包含以下各列的表格回答： - 迭代：循环迭代编号。 - 指令。 - 派发：指令派发的周期。 - 执行：指令执行的周期。 - 内存访问：访问内存的周期。 - 完成：结果可供其他指令使用的周期。 - 说明：描述该指令正在等待的事件。 表格应展示三次循环迭代。可以忽略第一条指令。 b. **[20]〈3.3, 3.6〉** 重做 a，但改为双发射处理器，并假定浮点单元（FPU）完全流水化。 ### 习题 3.15 {#exercise-3-15} **[10] 〈3.6〉** 假定动态调度处理器每周期只能向等待中的指令广播、即转发一个功能单元的结果。使用上一题 3.14 的硬件配置和延迟，找出一个不超过 10 条指令的代码序列，使处理器必须因这一限制产生的结构冒险而停顿。指出停顿发生在序列中的什么位置。 ### 习题 3.16 {#exercise-3-16} **[20] 〈3.4〉** 一个 \((m,n)\) 相关分支预测器，用最近执行的 \(m\) 个分支的行为，从 \(2^m\) 个预测器中选择一个；每个预测器都是 \(n\) 位预测器。两级局部预测器的工作方式相似，但只跟踪各个分支自身的历史行为，用来预测其未来行为。 这类预测器存在设计取舍：相关预测器只需要很少的存储空间保存历史，因此可以为大量独立分支维护 2 位预测器，降低不同分支指令复用同一预测器的概率；局部预测器则需要更多空间保存历史，因此只能跟踪相对较少的分支指令。 本题比较一个可跟踪四个分支的 \((1,2)\) 相关预测器，需要 16 位，与一个使用相同存储空间、可跟踪两个分支的 \((1,2)\) 局部预测器。对于下面给出的分支结果序列，列出每次预测、所用表项、预测结果导致的所有表项更新，以及每个预测器最终的错误预测率。假定截至此时，所有分支都已跳转。按以下状态初始化预测器。 **相关预测器** | 表项 | 分支 | 上次结果 | 预测 | | ---: | ---: | --- | --- | | 0 | 0 | T | T，已有一次错误预测 | | 1 | 0 | NT | NT | | 2 | 1 | T | NT | | 3 | 1 | NT | T | | 4 | 2 | T | T | | 5 | 2 | NT | T | | 6 | 3 | T | NT，已有一次错误预测 | | 7 | 3 | NT | NT | {.wide .expand} **局部预测器** | 表项 | 分支 | 最近两次结果（右侧为最近一次） | 预测 | | ---: | ---: | --- | --- | | 0 | 0 | T,T | T，已有一次错误预测 | | 1 | 0 | T,NT | NT | | 2 | 0 | NT,T | NT | | 3 | 0 | NT | T | | 4 | 1 | T,T | T | | 5 | 1 | T,NT | T，已有一次错误预测 | | 6 | 1 | NT,T | NT | | 7 | 1 | NT,NT | NT | {.wide .expand} > 译注：T 表示跳转，NT 表示不跳转。原题将局部预测器写为 \((1,2)\)，但表中记录最近两次结果；表项 3 又只写一个 NT，均为原页内容。题设“16 位”与是否计入历史位的口径也未进一步说明，译文不补造假设。 | 分支 PC（字地址） | 结果 | | ---: | --- | | 454 | T | | 543 | NT | | 777 | NT | | 543 | NT | | 777 | NT | | 454 | T | | 777 | NT | | 454 | T | | 543 | T | ### 习题 3.17 {#exercise-3-17} **[10] 〈3.4〉** 假定有一个深流水线处理器，只为条件分支实现分支目标缓冲区。错误预测代价始终为 4 个周期，缓冲区未命中代价始终为 3 个周期。假定命中率 90%、预测准确率 90%、分支频率 15%。与分支代价固定为两个周期的处理器相比，采用分支目标缓冲区的处理器快多少？假定不含分支停顿的基础 CPI 为 1。 ### 习题 3.18 {#exercise-3-18} **[10/5] 〈3.4〉** 考虑一个分支目标缓冲区：正确预测条件分支、错误预测、缓冲区未命中的代价，分别为 0、2、2 个时钟周期。考虑一种区分条件与无条件分支的设计：对条件分支保存目标地址，对无条件分支保存目标指令。 a. **[10]〈3.9〉** 在缓冲区中找到一个无条件分支时，其代价是多少个时钟周期？ b. **[10]〈3.9〉** 求对无条件分支采用分支折叠（branch folding）带来的改进。假定命中率 90%，无条件分支频率 5%，缓冲区未命中代价为两个周期。这项增强带来多少性能改善？命中率至少需要多高，才能获得性能收益？ > 译注：题首难度标注为 [10/5]，b 小问却标为 [10]；子问指向 3.9，而题首指向 3.4。编号及难度均照原书保留。 ### 习题 3.19 {#exercise-3-19} **[10] 〈3.2, 3.7〉** 考虑以下代码，它计算稀疏矩阵 A 与稠密向量 x 的乘积。稀疏矩阵采用压缩稀疏行（Compressed Sparse Row，CSR）格式：所有非零元素按行优先顺序保存在连续内存块中，第 \(i\) 个非零元素保存在 `val[i]`，对应列保存在 `col[i]`，其所在行为 \(n\)，满足 \(\text{ptr}[n]\le i<\text{ptr}[n+1]\)。也就是说，`ptr` 数组保存各行第一个元素的索引。 ~~~asm loop: fld f0,0(x1) # 加载 val[i] lw x3,0(x2) # 加载 col[i] slli x3,x3,3 # temp = col[i] * 8 add x4,x10,x3 # 计算有效地址（&x[0]+temp） fld f2,0(x4) # 加载 x[col[i]] fmac.d f4,f0,f2 # 乘加累积 addi x1,x1,8 # 递增 &val[i] addi x2,x2,8 # 递增 &col[i] addi x5,x5,1 # 递增 i bne x5,x11,skip # 检查行尾（i!=ptr[i]） fsd f4,0(x6) # 存储点积 addi x7,x7,8 # 递增 &ptr[row] beq x7,x12,done # 检查是否已处理最后一行 addi x6,x6,8 # 递增 &x[row] lw x11,(x7) # 加载 ptr[row] fli f4,0 # 清空累加器 skip: b loop ~~~ a. **[5]〈3.7〉** 哪些加载指令可能需要推测式内存消歧？是否可能通过内存存在 RAW 依赖？ b. **[5]〈3.2〉** 你预计分支预测器对第 10 条指令中的分支，预测效果如何？ > 译注：原代码的行尾注释写 `i!=ptr[i]`，输出指针递增注释写 `&x[row]`；`lw` 后的索引步长为 8，且使用 `fmac.d`、`fli`、`b` 等写法。 ### 习题 3.20 {#exercise-3-20} **[10] 〈3.2, 3.5〉** 考虑以下代码，它用 Horner 法，对保存在寄存器 f6、f8 中的两个输入值计算多项式。 ~~~asm loop: fld f0,0(x1) # 加载系数 fmul.d f2,f6,f10 # temp = x1 * accum fadd.d f10,f2,f0 # accum = temp+coeff（f10 有循环携带依赖） fmul.d f2,f8,f12 # temp = x2 * accum fadd.d f12,f2,f0 # accum = temp2+coeff（f12 有循环携带依赖） addi x1,x1,8 bne x1,x2,loop ~~~ 将循环展开为原来的两倍，并给浮点寄存器使用其他名称进行重命名，避免名依赖引起的性能损失。然后给出最终的寄存器映射。 > 译注：乘法注释中的 `x1`、`x2`，以及第二个乘法仍写 `temp` 而后续使用 `temp2`，均为原书注释；指令本身的输入是 f6、f8。 ### 习题 3.21 {#exercise-3-21} **[5] 〈3.7〉** 对于以下代码片段，分别求两种 CPU 执行它所需的周期数：一种不支持加载旁路与推测式内存消歧，另一种同时支持这两项功能。假定存储与加载指令之间没有依赖。 假定使用单发射乱序流水线，包含一个延迟为 3 个周期的整数单元，以及一个延迟为 4 个周期的加载 / 存储单元。指令可以在最后一条产生其依赖结果的指令完成的同一周期发射。请说明你所做的其他假设。 ~~~asm add x8,x10,x11 add x6,x8,x9 add x3,x6,x7 sw x2,0(x3) lw x4,0(x5) ~~~