习题（Amr Zaky 编写）

习题 B.1

[10/10/10/15]〈B.1〉 为了体会局部性原理对于论证使用缓存的合理性有多重要，你在一台具有 L1 数据缓存和主存的计算机上做实验，只考察数据访问。

各种访问的延迟以 CPU 周期计，分别为：缓存命中 1 个周期；缓存未命中 110 个周期；禁用缓存后访问主存 105 个周期。

a. [10]〈B.1〉 运行一个总体未命中率为 3% 的程序时，平均访存时间是多少个 CPU 周期？

b. [10]〈B.1〉 接下来，运行一个专门生成完全随机数据地址、毫无局部性的程序。为此，使用大小为 1 GB 的数组，整个数组都能放进主存。程序不断访问数组中的随机元素，用均匀随机数发生器生成元素下标。若数据缓存为 64 KB，平均访存时间是多少？

c. [10]〈B.1〉 把 b 问的结果与禁用缓存时的主存访问时间比较，对于局部性原理在论证使用缓存的合理性中所起的作用，你能得出什么结论？

d. [15]〈B.1〉 你观察到，缓存命中带来 104 个周期的收益（1 个周期对 105 个周期），但未命中会损失 5 个周期（110 个周期对 105 个周期）。一般地，用 $G$ 表示收益（gain），$L$ 表示损失（loss）。用 $G$ 和 $L$ 求出未命中率的临界上限，超过它之后，使用缓存反而不利。

习题 B.2

[15/15]〈B.1〉 假设缓存容量为 512 字节，块大小为 64 字节，主存容量为 2 KB。可以把主存看作由 64 字节块组成的数组：M0、M1、……、M31。图 B.30 列出采用直接映射时，各缓存块可能容纳的主存块。

a. [15]〈B.1〉 若缓存改为全相联，给出相应表格。

b. [15]〈B.1〉 若缓存改为四路组相联，重做 a 问。

习题 B.3

[10/10/10/10/15/10/15/20]〈B.1〉 降低功耗的需求经常会影响缓存的组织方式。本题假设缓存在物理上分为数据阵列、标签阵列和替换阵列，分别存放数据、标签以及替换策略所需的信息。每种阵列又在物理上分成多个可单独访问的子阵列，每路一个。例如，一个采用最近最少使用（LRU）替换的四路组相联缓存，有四个数据子阵列、四个标签子阵列和四个替换子阵列。采用 LRU 时，每次访问都要访问一次替换子阵列；采用先进先出（FIFO）时，每次未命中才访问一次；采用随机替换时则不需要访问。某个具体缓存的各阵列访问功耗权重如图 B.31。¹

估算以下各配置下存储系统（缓存＋主存）的功耗，单位为上述功耗单位。假设缓存为四路组相联，分别给出采用 LRU、FIFO 和随机替换策略时的答案。

a. [10]〈B.1〉 缓存读命中，所有阵列同时读取。

b. [10]〈B.1〉 缓存读未命中时，重做 a 问。

c. [10]〈B.1〉 假设缓存访问分成两个周期，重做 a 问。第一周期访问所有标签子阵列，第二周期只访问标签匹配的那个数据子阵列。

d. [10]〈B.1〉 缓存读未命中时，重做 c 问；第二周期不访问数据阵列。

e. [15]〈B.1〉 增加预测将要访问哪一路的逻辑，重做 c 问。第一周期只访问预测路的标签子阵列。路命中，即预测路中的地址匹配，意味着缓存命中；路未命中则需要在第二周期检查全部标签子阵列。若路命中，第二周期只访问一个数据子阵列，即标签匹配的那一路。假设路预测器命中。

f. [10]〈B.1〉 假设路预测器未命中，即选错了路，重做 e 问。预测失败会增加一个额外周期，在此期间访问全部标签子阵列。假设路预测器未命中之后，缓存读命中。

g. [15]〈B.1〉 假设缓存读未命中，重做 f 问。

h. [20]〈B.1〉 运用 e、f、g 问的结果，处理一般情况：工作负载的路预测器未命中率为 5%，缓存未命中率为 3%。考虑不同的替换策略。

习题 B.4

[10/10/15/15/15/20]〈B.1〉 用一个具体例子比较直写和写回缓存对写带宽的需求。假设缓存为 64 KB，行大小为 32 字节，写未命中时分配一行。若配置为写回缓存，则在需要替换脏行时写回整行。缓存通过一条 64 位宽、即 8 字节宽的总线连接下一级存储器。通过这条总线写入 $B$ 字节需要的 CPU 周期数为：

其中括号表示向上取整。例如，写入 8 字节需要 $10+5\lceil8/8-1\rceil=10$ 个周期；用同一公式计算，写入 12 字节需要 15 个周期。

参考下面的 C 代码片段回答问题：

...
#define PORTION 1
...
base = 8*i;
for (unsigned int j = base; j < base + PORTION; j++)
// 假设 j 保存在寄存器中
{
    data[j] = j;
}

a. [10]〈B.1〉 对于直写缓存，j 循环的全部迭代合计要花多少 CPU 周期把写数据传送到主存？

b. [10]〈B.1〉 若配置为写回缓存，写回一个缓存行需要多少 CPU 周期？

c. [15]〈B.1〉 把 PORTION 改为 8，重做 a 问。

d. [15]〈B.1〉 在替换一个缓存行之前，至少对该行内数组元素更新多少次，写回缓存才更有优势？

e. [15]〈B.1〉 设想一种情形：缓存行内所有字都会被写入（不一定使用上述代码），但直写缓存所需的总 CPU 周期数反而少于写回缓存。²

习题 B.5

[10/10/10/10/]〈B.2〉 你正围绕一个顺序执行处理器构建系统。其频率为 1.1 GHz，不计访存时 CPI 为 1.35。

只有 load 和 store 指令会从存储器读写数据，分别占全部指令的 20% 和 10%。系统有分离的 L1 缓存，命中不引入额外代价。指令缓存和数据缓存都采用直接映射，各为 32 KB。指令缓存的未命中率为 2%，块大小为 32 字节；数据缓存采用直写，未命中率为 5%，块大小为 16 字节。数据缓存配有写缓冲，能消除 95% 写操作的停顿。

统一 L2 缓存容量为 512 KB，采用写回，块大小为 64 字节，访问时间为 15 ns。它通过 128 位数据总线连接 L1 缓存，总线运行在 266 MHz，每个总线周期传送一个 128 位字。系统发往 L2 缓存的全部访存请求中，有 80% 无须访问主存就能完成。此外，被替换的块有 50% 是脏块。主存宽 128 位，访问延迟为 60 ns；经过这段延迟之后，可以通过 128 位宽、133 MHz 的主存总线，以每周期一个总线字的速率，传送任意数量的总线字。

a. [10]〈B.2〉 指令访问的平均访存时间是多少？

b. [10]〈B.2〉 数据读的平均访存时间是多少？

c. [10]〈B.2〉 数据写的平均访存时间是多少？

d. [10]〈B.2〉 计入访存后，总体 CPI 是多少？

习题 B.6

[10/15/15]〈B.2〉 把未命中率（每次访问的未命中数）转换为每条指令的未命中数，依赖两个因素：每条取入指令对应的访存次数，以及取入指令中实际提交的比例。

a. [10]〈B.2〉 B-5 页中每条指令未命中数的公式，首先用未命中率、访存次数和指令数三个因素表示。每个因素都对应实际发生的事件。若改写为“未命中率乘以每条指令访存次数”，有什么不同？

b. [15]〈B.2〉 推测执行处理器会取入一些最终不提交的指令。B-5 页公式中的每条指令未命中数，针对的是执行路径上的指令，也就是完成程序实际必须执行的指令。把该公式改写成只使用未命中率、每条取入指令的访存次数，以及取入指令中最终提交的比例。为什么使用这些因素，而不用 B-5 页公式里的因素？

c. [15]〈B.2〉 “每条取入指令的访存次数”这个因素的值，未必等于某条特定指令实际发生的访存次数；因此，b 问的转换可能给出不正确的数值。重新改写 b 问的公式，修正这一缺陷。

习题 B.7

[20]〈B.1，B.3〉 在直写 L1 缓存后面接写回 L2 缓存、而非直接接主存的系统中，合并写缓冲可以简化。解释如何实现这种简化。是否存在某些情形，采用完整的写缓冲而非你提出的简化版本会更有帮助？

习题 B.8

[5/5/5]〈B.3〉 考察以下计算：

数组 $a$、$b$、$c$、$d$ 各有 512 个 4 字节整数元素，内存布局如下。

上述计算通过迭代 512 次的 for 循环完成。假设缓存为 32 Kbyte、四路组相联，访问时间为一个周期，未命中代价为每次访问 100 个 CPU 周期，写回的代价也为 100 个 CPU 周期。缓存在写命中时采用写回，在写未命中时采用写分配。

a. [5]〈B.3〉 若三个 load 和一个 store 全都在数据缓存中未命中，一次迭代需要多少周期？

b. [5]〈B.3〉 若缓存行为 16 字节，每次迭代平均需要多少周期？提示：空间局部性！

c. [5]〈B.3〉 若缓存行为 64 字节，每次迭代平均需要多少周期？

d. 若缓存改为直接映射，且容量缩小到 2048 字节，每次迭代平均需要多少周期？³

习题 B.9

[20]〈B.3〉 在其他参数不变时，提高缓存的相联度，从统计上说能够降低未命中率。但在某些特殊情况下，对特定工作负载提高相联度反而会增大未命中率。

比较容量相同的直接映射缓存与两路组相联缓存，假设组相联缓存采用 LRU 替换。为简化问题，块大小为一个字。构造一个字访问轨迹，使两路组相联缓存的未命中次数更多。

提示：把访问轨迹限定在两路组相联缓存的同一组内，并让同一轨迹在直接映射缓存中只涉及两个块位置。

习题 B.10

[10/10/15]〈B.3〉 考虑由 L1、L2 数据缓存组成的两级存储层次结构。假设两级缓存在写命中时都采用写回策略，且块大小相同。列出响应以下事件时采取的操作。

a. [10]〈B.3〉 缓存构成包含式层次时，发生 L1 缓存未命中。

b. [10]〈B.3〉 缓存构成互斥式层次时，发生 L1 缓存未命中。

c. [15]〈B.3〉 在 a、b 两问中，分别考虑被逐出的行是干净行和脏行的情况。

习题 B.11

[15/20]〈B.2，B.3〉 不让某些指令进入缓存，可以减少冲突未命中。

a. [15]〈B.3〉 画出一个程序的层次结构，使其中部分程序最好不要进入指令缓存。提示：考虑某些代码块处在比其他块更深的嵌套循环中的程序。

b. [20]〈B.2，B.3〉 提出软件或硬件技术，强制把某些块排除在指令缓存之外。

习题 B.12

[5/15]〈B.3〉 较大的缓存虽然未命中率较低，但命中时间往往更长。假设直接映射的 8 KB 缓存命中时间为 0.22 ns，未命中率为 $m_1$；四路组相联的 64 KB 缓存命中时间为 0.52 ns，未命中率为 $m_2$。

a. [5]〈B.3〉 若未命中代价为 100 ns，在什么条件下使用较小的缓存能降低总体访存时间？

b. [15]〈B.3〉 分别假设未命中代价为 10 和 1000 个周期，重做 a 问。总结什么时候采用较小的缓存可能更有利。⁴

习题 B.13

[15]〈B.4〉 程序运行在一台具有四表项、全相联微型 TLB 的计算机上（图 B.33）。

以下给出程序访问的虚拟页号轨迹。对每次访问，指出 TLB 命中还是未命中；若需要访问页表，再指出页面命中还是缺页。如果未访问页表，在页表列填写 X（图 B.34、图 B.35）。

习题 B.14

[15/15/15/15/]〈B.4〉 有些存储系统用软件把 TLB 未命中作为异常处理，另一些系统则由硬件处理 TLB 未命中。

a. [15]〈B.4〉 两种 TLB 未命中处理方式之间有哪些权衡？

b. [15]〈B.4〉 软件处理 TLB 未命中是否总比硬件处理慢？解释原因。

c. [15]〈B.4〉 是否存在硬件难以处理、软件却能处理的页表结构？是否也存在软件难以处理、硬件却容易管理的页表结构？

d. [15]〈B.4〉 为什么浮点程序的 TLB 未命中率一般高于整数程序？

习题 B.15

[20/20]〈B.5〉 采用类似 Hewlett-Packard Precision Architecture（HP/PA）的保护方案，可以提供比 Intel Pentium 体系结构更灵活的保护。该方案中，每个页表项除了页面访问权限，还包含一个“保护 ID”（钥匙）。每次访存时，CPU 将页表项中的保护 ID，与四个保护 ID 寄存器中的值分别比较；访问这些寄存器要求 CPU 处于管理模式。如果没有匹配的保护 ID，或者此次访问不被允许，例如写入只读页，就产生异常。

a. [20]〈B.5〉 说明如何利用这个模型，方便地将操作系统构造为若干相对较小、彼此不能覆盖写入的代码块，即微内核。与操作系统内任何代码都能写任意内存位置的单体操作系统相比，这种操作系统可能有哪些优点？

b. [20]〈B.5〉 对系统作一个简单修改，就能让每个页表项拥有两个保护 ID：一个用于读访问，另一个用于写或执行访问；如果可写位和可执行位都未置位，后一个字段就不用。为读和写能力使用不同的保护 ID，可能有什么好处？提示：这是否更便于进程之间共享数据和代码？