习题

作者：Jason D. Bakos。

习题 3.12

[25] 〈3.11〉 本题探讨三种采用不同多线程（MT）方式的处理器之间的性能取舍。它们都是超标量处理器，采用顺序流水线，所有加载与分支之后都必须固定停顿 3 个周期，且具有相同的 L1 缓存。同一线程在同一周期发射的指令，按程序顺序读取，彼此不能存在任何数据依赖或控制依赖。

应用是一个列表搜索程序，在 x16 与 x17 指定的地址范围内扫描内存区域，寻找保存在 x9 中的特定值。将搜索空间均分为四个大小相等、各自连续的块，每块分配一个搜索线程，从而并行化为四个线程。每个线程的大部分运行时间都花在以下展开后的循环体中：

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

[25/25/25] 〈3.1, 3.2, 3.9〉 本题考察软件技术如何从常见向量循环中开发指令级并行性（ILP）。以下循环称为 DAXPY 循环，即双精度 $aX+Y$，是 Gauss 消元中的核心操作。代码对长度为 100 的向量执行 DAXPY：$Y=aX+Y$。初始时，R1 设为数组 X 的基地址，R2 设为 Y 的基地址：

     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 阶段确定分支结果。所有结果都支持完全旁路。

a. [25]〈3.1〉 假定单发射流水线。给出未经编译器调度的循环，以及由编译器针对浮点操作延迟和分支延迟进行调度后的循环，标出所有停顿或空闲时钟周期。未经调度和调度后，结果向量 Y 的每个元素分别需要多少执行周期？如果只依靠处理器硬件，时钟需要快多少，才能达到调度编译器带来的性能提升？忽略提高时钟速度对存储系统性能可能产生的影响。

b. [25]〈3.2〉 假定单发射流水线。充分展开循环并合并循环开销指令，使其能够在没有任何停顿的情况下调度。必须展开多少次？给出指令调度。每个结果元素的执行时间是多少？

c. [25]〈3.9〉 假定 VLIW 处理器的每条指令包含五个操作，如图 3.28 所示。比较两种循环展开程度：先将循环展开 6 次，以开发 ILP，合并循环开销指令，调度到没有任何停顿，即没有发射周期完全空闲；然后重复这一过程，但改为展开 10 次。忽略分支延迟槽。给出两种调度。每种调度下，结果向量每个元素的执行时间是多少？操作槽位的利用率各是多少？两种调度的代码大小相差多少？各自总共需要多少寄存器？

习题 3.14

[20/20] 〈3.3, 3.6〉 本题考察动态调度处理器运行习题 3.13 中循环时的表现。功能单元如下表：

假定：

• 功能单元没有流水化。
• 功能单元之间没有转发，结果在指令完成时传递。
• 执行阶段 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

[10] 〈3.6〉 假定动态调度处理器每周期只能向等待中的指令广播、即转发一个功能单元的结果。使用上一题 3.14 的硬件配置和延迟，找出一个不超过 10 条指令的代码序列，使处理器必须因这一限制产生的结构冒险而停顿。指出停顿发生在序列中的什么位置。

习题 3.16

[20] 〈3.4〉 一个 $(m,n)$ 相关分支预测器，用最近执行的 $m$ 个分支的行为，从 $2^m$ 个预测器中选择一个；每个预测器都是 $n$ 位预测器。两级局部预测器的工作方式相似，但只跟踪各个分支自身的历史行为，用来预测其未来行为。

这类预测器存在设计取舍：相关预测器只需要很少的存储空间保存历史，因此可以为大量独立分支维护 2 位预测器，降低不同分支指令复用同一预测器的概率；局部预测器则需要更多空间保存历史，因此只能跟踪相对较少的分支指令。

本题比较一个可跟踪四个分支的 $(1,2)$ 相关预测器，需要 16 位，与一个使用相同存储空间、可跟踪两个分支的 $(1,2)$ 局部预测器。对于下面给出的分支结果序列，列出每次预测、所用表项、预测结果导致的所有表项更新，以及每个预测器最终的错误预测率。假定截至此时，所有分支都已跳转。按以下状态初始化预测器。

相关预测器

局部预测器

译注：T 表示跳转，NT 表示不跳转。原题将局部预测器写为 $(1,2)$，但表中记录最近两次结果；表项 3 又只写一个 NT，均为原页内容。题设“16 位”与是否计入历史位的口径也未进一步说明，译文不补造假设。

习题 3.17

[10] 〈3.4〉 假定有一个深流水线处理器，只为条件分支实现分支目标缓冲区。错误预测代价始终为 4 个周期，缓冲区未命中代价始终为 3 个周期。假定命中率 90%、预测准确率 90%、分支频率 15%。与分支代价固定为两个周期的处理器相比，采用分支目标缓冲区的处理器快多少？假定不含分支停顿的基础 CPI 为 1。

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

[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 数组保存各行第一个元素的索引。

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

[10] 〈3.2, 3.5〉 考虑以下代码，它用 Horner 法，对保存在寄存器 f6、f8 中的两个输入值计算多项式。

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

[5] 〈3.7〉 对于以下代码片段，分别求两种 CPU 执行它所需的周期数：一种不支持加载旁路与推测式内存消歧，另一种同时支持这两项功能。假定存储与加载指令之间没有依赖。

假定使用单发射乱序流水线，包含一个延迟为 3 个周期的整数单元，以及一个延迟为 4 个周期的加载 / 存储单元。指令可以在最后一条产生其依赖结果的指令完成的同一周期发射。请说明你所做的其他假设。

add x8,x10,x11
add x6,x8,x9
add x3,x6,x7
sw x2,0(x3)
lw x4,0(x5)