# 习题（Amr Zaky 编写）
<!-- source: p0783 -->

### 习题 B.1 {#exercise-b-1}

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

<!-- source: p0784 -->

各种访问的延迟以 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 {#exercise-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 问。

<!-- source: p0785 -->

| 缓存块 | 组 | 路 | 可能存放的主存块 |
|---:|---:|---:|---|
| 0 | 0 | 0 | M0、M8、M16、M24 |
| 1 | 1 | 0 | M1、M9、M17、M25 |
| 2 | 2 | 0 | M2、M10、M18、M26 |
| 3 | 3 | 0 | …… |
| 4 | 4 | 0 | …… |
| 5 | 5 | 0 | …… |
| 6 | 6 | 0 | …… |
| 7 | 7 | 0 | M7、M15、M23、M31 |
{#fig-B.30 .wide .expand num="B.30" caption="主存块到直接映射缓存的分配。"}

### 习题 B.3 {#exercise-b-3}

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

| 阵列或操作 | 功耗权重（每访问一路） |
|---|---:|
| 数据阵列 | 20 单位 |
| 标签阵列 | 5 单位 |
| 其他信息阵列（Miscellaneous array） | 1 单位 |
| 主存访问 | 200 单位 |
{#fig-B.31 .wide .expand num="B.31" caption="不同操作的功耗代价。"}

估算以下各配置下存储系统（缓存＋主存）的功耗，单位为上述功耗单位。假设缓存为四路组相联，分别给出采用 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 问。预测失败会增加一个额外周期，在此期间访问全部标签子阵列。假设路预测器未命中之后，缓存读命中。

<!-- source: p0786 -->

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

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

### 习题 B.4 {#exercise-b-4}

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

$$
10+5\left\lceil\frac{B}{8}-1\right\rceil
$$

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

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

```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 周期数反而少于写回缓存。[^b4-parts]

### 习题 B.5 {#exercise-b-5}

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

<!-- source: p0787 -->

只有 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 {#exercise-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 {#exercise-b-7}

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

<!-- source: p0788 -->

### 习题 B.8 {#exercise-b-8}

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

$$
d_i=a_i+b_i\times c_i,\qquad i=0,\ldots,511
$$

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

| 内存字节地址范围 | 内容 |
|---|---|
| 0–2047 | 数组 \(a\) |
| 2048–4095 | 数组 \(b\) |
| 4096–6143 | 数组 \(c\) |
| 6144–8191 | 数组 \(d\) |
{#fig-B.32 .wide .expand num="B.32" caption="数组在内存中的布局。"}

上述计算通过迭代 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 字节，每次迭代平均需要多少周期？[^b8-parts]

### 习题 B.9 {#exercise-b-9}

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

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

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

### 习题 B.10 {#exercise-b-10}

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

<!-- source: p0789 -->

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

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

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

### 习题 B.11 {#exercise-b-11}

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

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

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

### 习题 B.12 {#exercise-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 问。总结什么时候采用较小的缓存可能更有利。[^b12-units]

### 习题 B.13 {#exercise-b-13}

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

| 虚拟页号 VP# | 物理页号 PP# | 表项有效位 |
|---:|---:|---:|
| 5 | 30 | 1 |
| 7 | 1 | 0 |
| 10 | 10 | 1 |
| 15 | 25 | 1 |
{#fig-B.33 .wide .expand num="B.33" caption="TLB 的内容（原图注写作“习题 B.12”，实际用于本题 B.13）。"}

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

<!-- source: p0790 -->

| 虚拟页索引 | 物理页号 | 存在（Y＝是，N＝否） |
|---:|---:|:---:|
| 0 | 3 | Y |
| 1 | 7 | N |
| 2 | 6 | N |
| 3 | 5 | Y |
| 4 | 14 | Y |
| 5 | 30 | Y |
| 6 | 26 | Y |
| 7 | 11 | Y |
| 8 | 13 | N |
| 9 | 18 | N |
| 10 | 10 | Y |
| 11 | 56 | Y |
| 12 | 110 | Y |
| 13 | 33 | Y |
| 14 | 12 | N |
| 15 | 25 | Y |
{#fig-B.34 .wide .expand num="B.34" caption="页表的内容。"}

| 访问的虚拟页 | TLB（命中或未命中） | 页表（命中或缺页） |
|---:|---|---|
| 1 | | |
| 5 | | |
| 9 | | |
| 14 | | |
| 10 | | |
| 6 | | |
| 15 | | |
| 12 | | |
| 7 | | |
| 2 | | |
{#fig-B.35 .wide .expand num="B.35" caption="页面访问轨迹。"}

### 习题 B.14 {#exercise-b-14}

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

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

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

<!-- source: p0791 -->

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

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

### 习题 B.15 {#exercise-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，可能有什么好处？提示：这是否更便于进程之间共享数据和代码？

[^b3-position]: 译注：B.3 的题干位于原书 B-61 页，图 B.31 位于 B-62 页，关于四路相联、三种替换策略的统一要求则排在 B-63 页 h 问之后。这里将统一要求移到各小问之前，使题意连贯。图 B.31 把“Tag Array”拆排成左栏 Tag、右栏 Array 5 units；此处按上下文排为“标签阵列，5 单位”，未改变数值。

[^b4-parts]: 译注：B.4 题首列出六个分值，但原书实际只印出 a–e 五个小问，没有 f 问。

[^b8-parts]: 译注：原书 B.8 题首仅列三个分值，但确实包含 d 问，且 d 问没有分值和节号。

[^b12-units]: 译注：原书 a 问用 ns，b 问则写“周期”，但未提供周期长度。