Chapter 8 Cache(6)

这一节是讲解6 Cache Memories的。这一小节的内容很重要，一般大题会考缓存的各种算法，需要掌握。

Lecture Contents 中英对照表

English	Chinese
Purpose of Cache Memory	高速缓存存储器的目的
Organization of Cache/Main Memory System	高速缓存/主存系统的组织
Hit and Miss	命中与未命中
Cache Design Issues	高速缓存设计问题
Mapping Schemes	映射方案
Block Identification	块的标识
Replacement Algorithms	替换算法
Write Policies	写入策略

高速缓存存储器的目的

问题：性能差距

处理器的增长速度实在是太快了！！！

处理器速度增长快于 DRAM 的速度增长
- 处理器速度：年增长率约 60%
- DRAM 速度：年增长率仅约 7%
- 导致 处理器与内存性能差距（每年扩大约 50%）。

解决方案：高速缓存存储器

高速缓存 是基于 SRAM 的小型、快速存储器，由硬件自动管理。
作用：作为 CPU 和主存之间的缓冲区，存储主存中经常访问的数据块。

目的

提高访问速度
- 提供接近最快存储器速度的主存访问性能。
降低成本
- 在维持大容量存储的同时，使用相对廉价的半导体存储技术（如 DRAM）。

高速缓存和主存系统的组织

高速缓存和主存的对应是用行来对应主存中的一个块。

高速缓存与主存的组织结构

主存块数量：
- 主存被分为多个块（Block），每个块的大小为 $ K $，块的总数为 $ 2^n / K $。
高速缓存行：
- 高速缓存存储主存中的部分数据，每一行对应主存的一个块。
- 每一行存储某一部分地址的连续存储单元。
标识存储块：
- 每行高速缓存需要一个标识字段，标明当前行存储的是主存中的哪个具体块。

一图胜千言，看图理解缓存和主存的对应关系。

总结

高速缓存的设计基于块的概念，通过组织块与行之间的对应关系，实现快速定位和访问主存数据，同时缓解主存与处理器间的性能差距。

命中与未命中 (Hit and Miss)

很好理解的概念，注意命中率和为命中率。

命中 (Hit)

高速缓存访问到所需数据，并发现数据已经驻留在高速缓存中。

未命中 (Miss)

高速缓存访问到所需数据，但未发现数据驻留在缓存中，需强制访问主存获取数据。

命中率 (Hit Rate)

定义：表示通过高速缓存满足内存访问的百分比。
要求：命中率高（通常在 0.9 以上）是高性能计算机的必要条件。

未命中率 (Miss Rate)

定义：未命中率等于 $ 1 - $。

总结

高速缓存的性能主要依赖于命中率。命中率越高，数据从缓存中获取的比例越大，减少对慢速主存的访问，从而提高整体系统性能。

高速缓存读取操作 (Cache Read Operation)

这两种处理方式需要记住：一种是先加载到缓存，另外一种是在加载到缓存的同时将字发送给处理器。第二种会更快一点。

缓存读取操作的基本流程

处理器无感知缓存存在
- 处理器无需明确知道缓存的存在。
- 它通过使用内存地址发出读和写请求。
缓存控制电路的作用
- 缓存控制电路判断所请求的数据是否已存在于缓存中。

处理器的读取请求 (Processor: Read Request)

缓存命中 (Cache Read Hit)
- 将请求的数据字直接转发给处理器。
缓存未命中 (Cache Read Miss)
- 两种处理方式：
  1. 块加载 (Block Copy)：
    - 从主存中将包含请求数据字的整个数据块复制到缓存中。
    - 然后将所需的特定数据字转发给处理器。
  2. 提前加载/早启动 (Load Through/Early Restart)：
    - 在将包含请求数据字的整个数据块从主存复制到缓存的同时，直接将所需的数据字立即转发给处理器。

缓存未命中 (Cache Read Miss)

当缓存中未找到所需数据时，现代缓存组织通常使用优化的策略来减少主存访问延迟。

总结

缓存的读取操作分为命中与未命中。命中时直接提供数据，未命中时根据不同策略从主存加载数据块。
早启动策略有助于减少处理器等待时间，提高读取效率。

高速缓存设计问题 (Cache Design Issues)

上一节留下了一些问题，这一节将会解答这些问题。

歌曲总会让人产生思绪，一种名为感动的感觉纷至沓来。

1. 缓存映射方案 (Cache Mapping Schemes)

问题： 数据块（Block）可以放置在缓存中的什么位置？
常见映射方案：
- 直接映射 (Direct Mapping)： 每个主存块只能映射到缓存中的固定位置。
- 全相联映射 (Fully Associative Mapping)： 主存块可以放置到缓存中的任意位置。
- 组相联映射 (Set-Associative Mapping)： 主存块可以映射到一个特定组内的任何位置。

2. 数据块标识 (Block Identification)

问题： 如何判断所请求的数据块是否存在于缓存中？
解决方法：
- 缓存通过标签 (Tag)字段来标识主存中的块。
- 标签存储在缓存行的元数据中，通过地址的高位部分与标签比较来确认命中。

3. 替换算法 (Replacement Algorithms)

问题： 当缓存未命中且缓存已满时，应该替换掉哪个缓存块？
常用算法：
- 最近最少使用 (LRU, Least Recently Used)： 替换最近最少被访问的块。
- 先进先出 (FIFO, First-In-First-Out)： 替换最早进入缓存的块。
- 随机替换 (Random)： 随机选择一个块替换。
- 最少频率使用 (LFU, Least Frequently Used)： 替换访问次数最少的块。

4. 写策略 (Write Policy)

问题： 写操作时，如何处理缓存命中和未命中？
- 写命中 (Write Hit)：
  1. 写直达 (Write-Through)： 同时更新缓存和主存。
  2. 写回 (Write-Back)： 仅更新缓存，主存更新延迟到块被替换时。
- 写未命中 (Write Miss)：
  1. 写分配 (Write-Allocate)： 将缺失块加载到缓存，然后写入缓存。
  2. 非写分配 (No-Write-Allocate)： 直接写入主存，不加载到缓存。

精华所在

高速缓存设计需要解决以下核心问题：块放置位置、块的查找方式、替换策略以及写操作策略。合理的设计能够在性能和成本之间达到良好平衡。

映射方案 (Mapping Scheme)

1. 映射方案的作用

定义：
映射方案决定了当主存中的数据块被复制到缓存时，数据块将被放置在缓存的哪个位置。
地址转换：
缓存映射方案还需将主存地址转换为缓存中的具体位置，因为主存和缓存的结构不同。
- 当 CPU 生成一个主存地址请求时，如果数据存在于缓存中，则需要通过映射方案找到对应的缓存位置。

2. 三种主要映射方案

直接映射 (Direct Mapping)
- 每个主存块只能映射到缓存中的固定位置。
- 优点： 实现简单，查找快速。
- 缺点： 容易发生冲突（两个主存块映射到同一缓存行）。
全相联映射 (Associative Mapping)
- 主存块可以映射到缓存中的任意位置。
- 优点： 最大限度减少冲突。
- 缺点： 查找复杂且时间较长。
组相联映射 (Set-Associative Mapping)
- 主存块可以映射到一个固定组内的任意缓存位置。
- 是直接映射和全相联映射的折中方案。
- 优点： 平衡了实现复杂度和冲突解决能力。

3. 基本假设

缓存行 (Cache Line)：
- 表示为 $ L_i $, $ i = 0, 1, ..., m-1 $
- $ m = 2^r $ 表示缓存中有 $ 2^r $ 个缓存行。
主存块 (Memory Block)：
- 表示为 $ B_j $, $ j = 0, 1, ..., n-1 $
- $ n = 2^s $ 表示主存分为 $ 2^s $ 个块。
数据块大小：
每个块或行由 $ k = 2^w $ 个连续的字组成。
主存地址结构：
主存地址由 $ s + w $ 位组成：
- 高 $ s $ 位： 用于确定数据块所在的主存块。
- 低 $ w $ 位： 用于确定块内偏移。

直接映射 (Direct Mapping)

1. 直接映射概念

每个主存块 (Main Memory Block) 只能映射到缓存中的一个固定缓存行 (Cache Line)。
映射函数：
$ i = j m $
其中：
- $ i $：缓存行号 (Cache Line Number)
- $ j $：主存块号 (Main Memory Block Number)
- $ m $：缓存中的缓存行总数

2. 缓存行分配表

缓存行号 (Cache Line)	分配的主存块号 (Main Memory Blocks Assigned)
0	$ 0, m, 2m, ..., 2^s m $
1	$ 1, m+1, 2m+1, ..., 2^s m+1 $
...	...
$ m-1 $	$ m-1, 2m-1, 3m-1, ..., 2^s m-1 $

3. 主存地址结构

地址分割： 主存地址被划分为三个字段：
- Tag 字段 (s-r bits)： 确定主存块是否在缓存中。
- Line 字段 (r bits)： 确定块所在的缓存行。
- Word 字段 (w bits)： 确定块内的具体字。
地址结构：
$ Tag $ $ Line $ $ Word $

4. 缓存访问过程

从 CPU 生成的地址中提取：
- Tag 字段：用于比较，判断是否命中缓存。
- Line 字段：定位对应的缓存行。
- Word 字段：定位缓存行中的具体字。
匹配过程：
- 如果缓存行中的 Tag 匹配，则命中缓存 (Cache Hit)。
- 如果不匹配，则发生缓存未命中 (Cache Miss)，需要从主存加载数据。

5. 例子分析

条件：
- 缓存行数：128
- 每行大小：16 个字
- 主存大小：64K 个字
- 主存地址为 16 位。
计算：
- 主存块总数：$ 64K / 16 = 4096 $
- 映射公式：$ i = j $
- 地址划分：
  - Word 字段：$ 4 $ 位 ($ _2 16 = 4 $)
  - Line 字段：$ 7 $ 位 ($ _2 128 = 7 $)
  - Tag 字段：$ 16 - 4 - 7 = 5 $ 位。
缓存分配示例：

6. 优缺点分析

优点：
- 实现简单，硬件复杂度低。
- 低成本。
缺点：
- 固定位置映射导致冲突频繁：
  - 如果程序频繁访问映射到同一缓存行的两个主存块，会导致缓存未命中率较高。

全相联映射 (Associative Mapping)

1. 全相联映射概念

无需映射函数： 主存的任何块 (Main Memory Block) 可以加载到缓存中的任意一行 (Cache Line)。
主存地址结构：
- 地址被分解为 Tag 字段 和 Word 字段。
- Tag 字段： 唯一标识主存中的块。
- Word 字段： 指定块中的具体字。
访问机制：
- 缓存中的每一行都会检查其 Tag 值是否与主存地址的 Tag 字段匹配。
- 如果找到匹配，则命中缓存 (Cache Hit)。
- 缺点： 检查所有行的 Tag，搜索开销较大。

2. 主存地址结构

字段	含义
Tag (s 位)	用于标识主存块
Word (w 位)	用于定位块中的字

地址格式：
$ Tag (s 位) $ $ Word (w 位) $

3. 缓存访问过程

主存地址解析：
- 从主存地址中提取 Tag 和 Word 字段。
- Tag 用于标识块，Word 用于选择块中的具体字。
缓存查找：
- 将主存地址的 Tag 字段与缓存中所有行的 Tag 逐一比较。
- 如果找到匹配，则读取对应行中的数据 (命中缓存)。
- 如果没有匹配，则发生未命中 (Cache Miss)，从主存加载数据到缓存。
缓存数据存储：
- 主存块可以存储到缓存中的任意行，位置无固定限制。

4. 例子分析

条件：
- 缓存行数：128
- 主存块数：4096
特点：
- 主存地址只需拆分为 Tag 和 Word 字段：
  - Tag 字段：用于标识 4096 个主存块。
  - Word 字段：用于定位块内的具体字。

5. 优缺点分析

优点：
- 灵活性高： 每个主存块可以加载到缓存的任意行，避免直接映射中的固定位置问题。
- 有效减少冲突问题，适合频繁访问不同主存块的场景。
缺点：
- 硬件复杂度高：
  - 查找缓存时，需要并行比较所有缓存行的 Tag 字段，电路设计复杂。
  - 查找开销较大，影响性能。

组相联映射 (Set Associative Mapping)

1. 组相联映射概念

结合了直接映射和全相联映射的技术。
缓存划分：
- 缓存被划分为若干个“组” (Set)，每组包含若干“行” (Line)。
- 一个主存块 (Block) 可以被映射到一个特定组中的任意行。
- 示例：
  - 如果缓存的每组有 2 行，则称为 2 路组相联映射。
  - 主存块 $ B_j $ 可以位于组 $ S_i $ 中的任意一行。

2. 组相联映射公式

假设缓存有 $ v = 2^d $ 组，每组有 $ k $ 行。
- 缓存总行数：$ m = v k $。
- 组号计算：$ i = j v $，其中：
  - $ i $ = 缓存组号
  - $ j $ = 主存块号
  - $ v $ = 缓存的组数
特殊情况：
- $ v = m, k = 1 $：直接映射
- $ v = 1, k = m $：全相联映射
- $ v = m/2, k = 2 $：2 路组相联映射
- $ v = m/4, k = 4 $：4 路组相联映射

3. 主存地址结构

字段	含义
Tag (s-d 位)	标识主存块
Set (d 位)	指定主存块映射到的缓存组
Word (w 位)	指定块内的具体字

地址分解格式：$ Tag (s-d 位) $ $ Set (d 位) $ $ Word (w 位) $

4. 缓存访问过程

主存地址解析：
- 提取 Tag 字段、Set 字段 和 Word 字段。
- Set 字段用于定位缓存组，Tag 字段用于验证块是否在缓存中。
查找缓存组：
- 根据 Set 字段确定具体组。
- 在该组中查找匹配的 Tag 值。
- 如果找到匹配，则发生命中 (Cache Hit)，读取数据。
- 如果未找到匹配，则发生未命中 (Cache Miss)，需要从主存加载数据到该组。
数据加载到缓存：
- 数据从主存加载到对应组中的某行。
- 如果组已满，则根据替换算法选择一行进行替换。

5. 示例

条件：
- 2 路组相联映射
- 缓存组数：64 ($ v = 64 $)
- 主存块号 $ j $ 的组号计算：$ i = j $
地址分解：
- 主存地址为 16 位：
  - Word 字段：4 位
  - Set 字段：6 位 ($ _2 64 $)
  - Tag 字段：$ 16 - 4 - 6 = 6 $ 位

6. 优缺点分析

优点：
- 减少冲突问题： 通过为主存块提供多个存储选择，缓解了直接映射中的冲突问题。
- 降低硬件复杂度： 与全相联映射相比，组相联映射的并行匹配硬件成本更低。
缺点：
- 标签比较复杂度：
  - 每次访问需要并行比较组中 $ k $ 行的 Tag 值，需要 $ k $ 个比较器。
  - 虽然比全相联映射 ($ n $ 个比较器，$ n $ 为缓存总行数) 成本低，但仍高于直接映射 (仅 1 个比较器)。
- 硬件设计比直接映射更复杂。

有效位 (Valid Bit)

1. 有效位的作用

在系统首次上电时，缓存中并没有有效数据。
每个缓存块需要一个控制位，通常称为有效位 (Valid Bit)，用于指示该块中的数据是否有效。

2. 有效位的定义

0：表示该缓存块中的数据无效。
1：表示该缓存块中的数据有效。

3. 有效位的初始化

当系统上电时：
- 所有缓存块的有效位均设置为 0。
- 表明缓存初始化后不包含任何有效数据。
当某块数据从主存加载到缓存中时：
- 该块的有效位被设置为 1，表示该块的数据现在是有效的。

4. 示例

假设缓存初始化时：
- 所有缓存块的有效位为 0。
某次缓存缺失后：
- 主存将对应块数据加载到缓存中。
- 该缓存块的有效位被设置为 1。

5. 总结

有效位的主要功能：
- 用于标记缓存块中数据的有效性。
- 避免处理无效数据，提高系统可靠性。
重要性：
- 在缓存的启动阶段和运行阶段，有效位是缓存控制的重要组成部分，保证了缓存数据的准确性和一致性。

替换算法 (Replacement Algorithms)

1. 直接映射缓存 (Direct Mapped Cache)

没有选择权：每个主存块只能映射到一个缓存行。
替换策略：直接替换该缓存行。

2. 关联映射和集合关联映射缓存 (Associative and Set Associative Mapped Cache)

硬件实现算法：由于硬件速度要求，这些替换算法通常由硬件实现。

3. 替换算法种类

LRU（最近最少使用，Least Recently Used）：
- 替换策略：替换最长时间没有被访问的块。
- 适用于当程序的访问模式表现出时间局部性时，优先保留最近访问的数据。
FIFO（先进先出，First In First Out）：
- 替换策略：每当块被访问时，将其推入队列。
- 替换时，选择队列中最早被访问的块（即队列最前面的块）进行替换。
随机 (Random)：
- 替换策略：随机选择一个块进行替换。
- 简单但可能不适用于所有情况，适用于硬件实现要求简单快速的场景。

4. 总结

直接映射缓存替换策略最简单，因为每个数据块只能映射到一个缓存行。
关联映射和集合关联映射缓存使用更复杂的替换算法如 LRU、FIFO 和随机，这些算法能够在缓存中更高效地选择被替换的数据块，从而优化缓存命中率和性能。

映射技术示例 (Mapping Techniques Example)

1. 假设条件

处理器具有分开的指令缓存和数据缓存。
数据缓存只能容纳8个数据块，每个块仅包含一个16位的数据字。
内存是按字地址化的，地址为16位。
使用 LRU (最近最少使用) 替换算法。

2. 问题描述

一个4×10的数组，元素占用一个字，存储在内存地址 7A00 到 7A27。
数组 A 的元素按列顺序存储。
应用程序将数组 A 第一行的元素根据该行元素的平均值进行归一化，即： $ A(0,i) $

注意地址一定要看这张图，不能惯性思维的思考存储关系。

3. 代码结构

SUM := 0
for j := 0 to 9 do
    SUM := SUM + A(0,j)
end

AVE := SUM / 10

for i := 9 down to 0 do
    A(0,i) := A(0,i) / AVE
end

4. 直接映射缓存 (Direct Mapped Cache)

内存地址的块映射到特定的缓存行。
缓存替换情况：在执行第二个循环时，8个元素被替换。
数据缓存内容变化：随着程序的执行，缓存中的元素依次替换。

5. 关联映射缓存 (Associative Mapped Cache)

在第二个循环执行过程中，仅替换了2个元素。
数据缓存内容变化：缓存内容通过对比标签和缓存中的内容来更新，减少了替换的次数。

6. 集合关联映射缓存 (Set Associative Mapped Cache)

在第二个循环执行过程中，6个元素被重新加载到缓存中。
数据缓存内容变化：相较于直接映射和关联映射，集合关联映射能够更灵活地选择替换的缓存行，减少了缓存失效率。

7. 映射技术对比

直接映射：每个块只能映射到特定的缓存行，容易导致缓存冲突，性能较低。
关联映射：允许任何块映射到缓存中的任意位置，灵活但增加了硬件开销。
集合关联映射：综合了两者的优点，允许每个块映射到多个缓存行中，减少了缓存冲突，性能较好，但硬件实现较复杂。

总结

在上述例子中，不同的映射技术对数据缓存的影响表现不同，选择合适的映射方式可以优化程序性能，特别是在处理大数据量时，集合关联映射能更好地减少缓存未命中的情况。

Quiz

问题 1：
通过 ____ 映射技术，可以将主存块放置到缓存的任何位置。

选项：
A. 直接映射 (Direct)
B. 全关联映射 (Associative)
C. 集合关联映射 (Set Associative)
D. 顺序映射 (Sequential)

答案：
B. 全关联映射 (Associative)

全关联映射是一种缓存映射技术，在这种方式下，主存的每一个块都可以被放置到缓存中的任何一个位置。它提供最大的灵活性，但也需要更多的硬件支持来查找缓存。

问题 2：
如果一个缓存的容量为 16KB，每个缓存行的长度为 128 字节，且该缓存是 2-way、4-way 或 8-way 集合关联映射，那么该缓存有多少个集合（sets）？

选项：
A. 64, 32, 16
B. 64, 16, 8
C. 32, 16, 8
D. 128, 64, 32

答案：
A. 64, 32, 16

计算过程：
- 缓存总容量 = 16KB = 16 * 1024B = 16384B
- 每个缓存行的大小 = 128B
- 缓存行总数 = 16384B / 128B = 128 个缓存行
- 在 2-way 集合关联映射下，每个集合包含 2 个缓存行，因此缓存有 128 / 2 = 64 个集合。
- 在 4-way 集合关联映射下，每个集合包含 4 个缓存行，因此缓存有 128 / 4 = 32 个集合。
- 在 8-way 集合关联映射下，每个集合包含 8 个缓存行，因此缓存有 128 / 8 = 16 个集合。

精华所在：

全关联映射：每个主存块可以映射到缓存的任意位置，提供最大的灵活性，但查找和管理更复杂。
集合关联映射：缓存被分成多个集合，每个集合包含多个缓存行，具体映射到哪个行取决于设置的方式，如 2-way、4-way 或 8-way 集合关联映射。

问题 3：
一个集合关联缓存总共有 64 个块，分为 4 个块集合。主存包含 4096 个块，每个块包含 128 个字。主存地址需要多少位？

选项：
A. 21
B. 24
C. 19
D. 32

答案：
C. 19

计算过程：
- 主存总共有 4096 个块，需要 12 位 来指定块地址（$ _2 4096 = 12 $）。
- 每个块包含 128 个字，需要 7 位 来指定字地址（$ _2 128 = 7 $）。
- 所以，主存地址总共有 12 + 7 = 19 位。

精华所在：

主存地址：由块地址和字地址组成。块地址指定主存中块的位置，字地址指定块内字的位置。
19 位地址：表示需要 12 位 来表示 4096 个块，和 7 位 来表示每个块内 128 个字的字地址。

问题 4：
一个集合关联缓存总共有 64 个块，分为 4 个块集合。主存包含 4096 个块，每个块包含 128 个字。每个地址中的 TAG、SET 和 WORD 字段各需要多少位？

选项：
A. 2, 5, 12
B. 12, 2, 5
C. 4, 8, 7
D. 8, 4, 7

答案：
D. 8, 4, 7

计算过程：
- 主存地址总共有 19 位（如问题 3 所计算）。
- WORD 字段：每个块包含 128 个字，因此需要 7 位 来表示字地址。
- SET 字段：缓存总共有 64 个块，分为 4 个块集合，即有 16 个集合（$ = 16 $）。所以需要 **4 位** 来表示集合地址（$ _2 16 = 4 $）。
- TAG 字段：剩余的位数就是 TAG 字段，即 19 - 7 - 4 = 8 位。

精华所在：

TAG 字段：用于标识缓存中的块。
SET 字段：用于标识缓存中具体的集合。
WORD 字段：表示块内字的偏移。

问题 5：
直接映射的优缺点是什么？

答案：

优点：
1. 简单，易于实现：直接映射是最简单的缓存映射方式，每个主存块映射到缓存中固定的一个位置，设计和实现都很直接。
2. 成本低：由于映射方式简单，硬件实现也较为便宜。
缺点：
1. 固定位置：每个主存块只能映射到缓存中的一个固定位置，这样可能会导致缓存冲突，如果多个块映射到相同的缓存位置，则会发生替换，导致缓存效率下降。

精华所在：

直接映射：每个主存块通过一个映射函数直接映射到缓存中某个固定位置，因此映射方式简单，硬件实现成本低。
优点：简单、易实现、成本低。
缺点：固定映射位置，可能导致缓存冲突和性能下降。

问题 6：
关联映射的优缺点是什么？

答案：

优点：
1. 完全自由的缓存位置选择：关联映射允许主存块映射到缓存中的任意位置，因此相比于直接映射，它能够提供更灵活的缓存管理，减少缓存冲突的概率。
缺点：
1. 复杂的电路：由于需要同时检查缓存中所有块的标签，因此关联映射需要更复杂的电路和更多的硬件资源来进行标签比较，这增加了硬件的复杂性和成本。

精华所在：

关联映射：缓存块的位置可以根据需要自由选择，不需要固定位置，能有效减少缓存冲突。
优点：灵活的缓存位置选择，减少冲突。
缺点：硬件实现复杂，增加电路和资源需求。

写入策略

(1)

写命中 (Write Hit)

写直达 (Write Through)
- 定义：缓存位置和主存位置同时更新。
- 优点：
  - 保证缓存和主存的数据一致性。
- 缺点：
  - 所有写操作都需要访问主存（总线事务），增加了系统开销。
  - 如果后续有读请求需要访问主存（因为缓存未命中），则必须等待之前的写操作完成，造成延迟。

(2)

写回 (Write Back)
- 定义：只更新缓存位置，并通过附加的标志位（脏位）标记缓存为已修改。当该缓存块被替换时，再将主存中的数据更新。
- 脏位：
  - 0：未修改
  - 1：已修改（脏）

(3)

写命中 (继续)

写回 (继续)
- 优点：
  - 比写直达更快，因为不需要每次访问主存。
  - 如果一个块内有多个字需要写入，只需要在主存中进行一次写操作。
- 缺点：
  - 主存中部分数据可能变得无效，因此通过 I/O 模块的访问只能通过缓存进行。
  - 需要在缓存中增加额外的位来标记哪些块已修改，这会增加缓存的大小。

(4)

写未命中 (Write Miss)

无写分配 (No Write Allocate)
- 定义：在写直达缓存中，信息直接写入主存，而不会加载到缓存中。
写分配 (Write Allocate)
- 定义：在写回缓存中，首先将包含目标字的块加载到缓存中，然后在缓存中的相应位置进行写入。

总结：

写直达：每次写操作都会同步更新缓存和主存，保证数据一致性，但会增加系统开销。
写回：仅更新缓存，减少主存访问，提高效率，但需要额外的脏位标记，且可能导致部分主存数据无效。
写未命中：直接写入主存，不加载到缓存中；写分配则将数据块加载到缓存后再写入。

缓存命中率 (Cache Hit Rate)

命中率 (Hit Rate)
- 定义：命中率是所有访问中命中的次数占总访问次数的比例。
- 公式： $ H = $
  - $H$：缓存命中率
  - $N_c$：访问缓存成功的次数
  - $N_m$：访问主存的次数
  - 总的访问次数为 $N_c + N_m$，因此缓存未命中率为 $1 - H$。
平均访问时间 (Average Access Time)
- 定义：平均访问时间是处理器访问数据时所经历的平均时间，考虑了命中和未命中的情况。
- 公式： $ t_{ave} = H t_c + (1 - H) t_m $
  - $t_{ave}$：平均访问时间
  - $H$：命中率
  - $t_c$：缓存访问时间
  - $t_m$：主存访问时间
- 例子：假设主存访问时间为70ns，缓存访问时间为10ns，命中率为90%。
  - 平均访问时间： $ 0.9 + (1 - 0.9) = 9 + 7 = 16ns $
  - 可以看到，缓存大大提高了访问速度。
例子：访问延迟计算
- 假设缓存和主存的访问时间分别为 $ $ 和 $ 10$，当缓存未命中时，将会加载一个包含8个字的数据块到缓存中。
- 访问延迟计算：
  - 初次访问延迟： $ $（缓存未命中时的延迟）
  - 数据块加载后，另一个延迟 $ $ 用于将数据传送给处理器
  - 总延迟：
    $ + 10+ 7+ = 19 $
命中率改进计算
- 假设程序中的30%指令涉及读写操作（即每100条指令有130次内存访问），且缓存中指令和数据的命中率分别为95%和90%。
- 改进计算： \[ \text{未使用缓存的时间} - \text{使用缓存的时间} = 130 \times 10\tau / 100 \times (0.95\tau + 0.05 \times 19\tau) + 30 \times (0.9\tau + 0.1 \times 19\tau) = 4.7\tau \]
- 结果表明，使用缓存能显著提高性能。

命中率是衡量缓存有效性的一个重要指标，决定了缓存的访问效率。
平均访问时间考虑了缓存命中与未命中的影响，缓存命中率越高，平均访问时间越短。
未命中延迟取决于加载数据块到缓存的过程，并且随着数据块大小增加，延迟也会增加。
通过提高缓存命中率，系统性能可以大幅提升，减少主存访问的次数。

多级缓存 (Multi-level Cache)

多级缓存层次结构
- 现代系统通常采用多级缓存体系结构。
- 各级缓存形成自己的小型内存层次。
- 指令缓存与数据缓存：
  - 统一缓存：指令和数据都缓存的缓存结构。
  - 数据和指令分开缓存：为了避免过多的缓存未命中，现代系统通常将数据和指令缓存分开。
  - 优点：分开缓存减少了访问的随机性和增加了访问的聚集性，通常比统一缓存的访问时间更短。
一级缓存（L1）与二级缓存（L2）
- 一级缓存 (L1)：
  - 通常位于CPU核心内。
  - 通常分为指令缓存和数据缓存。
  - 大小较小，通常为8KB到128KB。
  - 访问时间通常为4ns左右。
- 二级缓存 (L2)：
  - 位于CPU核心外。
  - 比一级缓存大，通常为256KB到几MB。
  - 通过高速总线与CPU连接，访问时间通常为15-20ns。
  - 通常是统一缓存。
平均访问时间 (Average Access Time)
- 假设：
  - $ h_1 $ 是一级缓存的命中率。
  - $ h_2 $ 是二级缓存的命中率。
  - $ C_1 $ 是访问一级缓存所需的时间。
  - $ C_2 $ 是将信息从二级缓存传输到一级缓存的延迟（未命中的惩罚）。
  - $ M $ 是将信息从主存传输到二级缓存的延迟。
- 平均访问时间公式为： $ t_{} = h_1 C_1 + (1 - h_1) (h_2 C_2 + (1 - h_2) M) $
商用处理器中的缓存示例
- Intel缓存发展史：
  - 80386：没有片上缓存，外部缓存。
  - 80486：片上L1缓存，大小为8KB，使用16字节行和4路组相联组织；外部有L2缓存。
  - Pentium（所有版本）：有两个片上L1缓存（分别用于数据和指令）。
  - Pentium II：片上有L2缓存。
  - Pentium III：添加了片外L3缓存。
Intel缓存演变过程：
- 问题与解决方案：
  - 问题：外部内存比系统总线慢。
    - 解决方案：增加外部缓存，使用更快的内存技术。
    - 首次出现于处理器：386。
  - 问题：处理器速度提高导致外部总线成为缓存访问瓶颈。
    - 解决方案：将外部缓存移至片上，与处理器同步运行。
    - 首次出现于处理器：486。
  - 问题：内部缓存较小，受芯片空间限制。
    - 解决方案：增加外部L2缓存，使用比主存更快的技术。
    - 首次出现于处理器：486。
  - 问题：指令预取器和执行单元同时访问缓存时发生竞争。
    - 解决方案：创建分离的数据和指令缓存。
    - 首次出现于处理器：Pentium。
  - 问题：处理器速度提高导致外部总线成为L2缓存访问瓶颈。
    - 解决方案：创建独立的背面总线（BSB），运行速度比前端总线更快，专门用于L2缓存。
    - 首次出现于处理器：Pentium Pro。
  - 问题：一些应用需要快速访问大量数据，片上缓存过小。
    - 解决方案：增加外部L3缓存。
    - 首次出现于处理器：Pentium III。
  - 问题：将L3缓存移至片上，进一步提高性能。
    - 首次出现于处理器：Pentium 4。

测验

缓存机制的有效性与计算机程序的属性

缓存机制的有效性基于计算机程序的哪个属性？

答案：B. locality of reference（局部性原理）
- 缓存机制的有效性主要依赖于程序的局部性原理，即程序通常会在时间上或空间上访问相近的内存位置，缓存可以利用这一点提高效率。

以下哪个管理缓存与主存之间数据的传输？

答案：D. hardware（硬件）
- 缓存和主存之间的数据传输完全由硬件管理，硬件负责将数据从主存加载到缓存以及缓存中的数据写回主存。

精华所在：

局部性原理：缓存有效性的一个关键因素是局部性原理。程序在运行时往往会多次访问相同的内存位置（时间局部性）或相邻的内存位置（空间局部性）。缓存利用这种访问模式，通过存储频繁访问的数据来减少访问主存的次数，从而提高系统性能。
硬件管理缓存与主存之间的数据传输：缓存和主存之间的数据传输通常由硬件自动管理，不需要操作系统或编译器干预。硬件负责判断是否发生缓存命中或未命中，并在未命中时自动将数据从主存加载到缓存，或将修改后的数据从缓存写回主存。

缓存系统问题解答：

如果缓存的缓存行大小为64字节，而主存对每个内存请求的响应时间为20个周期，每次返回2字节数据，那么从主存获取一个缓存行需要多少个周期？

答案：C. 640
解释：主存每次返回2字节数据，因此需要进行64字节的请求，计算过程如下： $ = 640 $ 即需要640个周期来从主存获取一个64字节的缓存行。

在缓存系统中，当一个块需要被覆盖时，最好覆盖那个最长时间没有被引用的块。这种技术称为____替换算法。

答案：D. LRU（最近最少使用）
解释：LRU（Least Recently Used）算法是一种替换策略，它会选择那个在缓存中最长时间没有被访问过的块进行替换，以优化缓存的命中率。该算法基于假设：如果一个块在最近没有被访问过，那么未来也不太可能被访问。

精华所在：

缓存行的获取时间：缓存行大小和主存的响应时间直接影响获取缓存行的总时间。在此题中，每次从主存读取2字节，64字节的缓存行需要32次读取，每次读取需要20个周期，因此总时间为640个周期。
LRU替换算法：LRU（最近最少使用）替换算法是缓存替换策略之一，它选择在缓存中最长时间未被访问的数据块进行替换。这种方法基于局部性原理，假设最近未被使用的数据未来也不太可能再被使用。

在直接映射缓存中，当需要从缓存中驱逐一条缓存行以腾出空间时，使用随机替换策略是合理的吗？

答案：False
解释：在直接映射缓存（Direct Mapped Cache）中，每个内存块只能映射到缓存中的唯一位置。因此，当需要替换数据时，并没有选择驱逐哪个缓存行的余地，必须替换掉映射到相同位置的缓存行。因此，不涉及随机替换策略。

在写操作中，缓存位置和主存位置同时更新。这种技术被称为写直通（Write Through）协议。

答案：True
解释：写直通（Write Through）是一种缓存写策略。在这种策略中，每当缓存被更新时，主存中的对应位置也会同步更新。这种方法的优点是缓存与主存始终保持一致，但缺点是每次写操作都会访问主存，可能导致较大的性能开销。

精华所在：

直接映射缓存中的替换策略：

直接映射特点：
- 每个内存块只能映射到缓存中的一个固定位置。
- 因此，当发生替换时，并不需要选择替换策略，因为被替换的块是唯一确定的。
无需随机替换：
- 直接映射缓存并不使用随机替换策略。
- 替换的块是新数据映射到的固定位置的旧数据。

写直通（Write Through）协议：

写直通操作机制：
- 写操作时，缓存和主存同步更新。
- 保证缓存和主存数据一致性。
优点：
- 简化了数据一致性问题。
- 特别适合频繁读取而不频繁写入的场景。
缺点：
- 写操作性能较低，因为每次写操作都会访问主存。
- 相比写回（Write Back）策略，开销更大。

写直通（Write Through）策略的优缺点

优点（Advantage）：

数据一致性（Consistency）：
- 写操作时，缓存和主存会同步更新，始终保持数据一致。
- 适合需要高数据可靠性的场景，减少数据一致性管理的复杂性。

缺点（Disadvantages）：

主存访问开销大（High Overhead of Main Memory Access）：
- 每次写操作都需要访问主存，增加了总的写延迟。
- 主存访问需要通过总线（Bus Transaction），进一步降低性能。
系统性能下降（Performance Impact）：
- 如果缓存未命中且主存正在处理写请求，其他读请求需要等待写操作完成，可能导致系统整体性能下降。
- 与写回策略相比，频繁写操作的性能会显著受限。

精华所在

写直通（Write Through）策略

特点：
- 写操作直接更新缓存和主存。
- 数据在缓存和主存中始终一致。
优点：
- 保证缓存和主存的数据一致性，无需额外机制管理一致性。
缺点：
- 高延迟：每次写入都需要同时更新主存，增加了写延迟。
- 性能降低：缓存未命中时，主存写入会阻塞后续内存访问操作。

写回（Write Back）策略的优缺点

优点（Advantages）：

速度更快（Faster Write Operations）：
- 数据只更新缓存，不立即写入主存，减少了主存的访问次数。
- 避免了每次写操作都占用总线带宽。
批量写入（Efficient for Multiple Writes）：
- 对缓存块中多个字的写操作可以合并为一次写回主存，减少了总的主存写入次数，提高效率。

缺点（Disadvantages）：

主存数据失效（Main Memory Inconsistency）：
- 缓存块未写回之前，主存中的数据是无效的。
- 这种情况下，I/O模块只能通过缓存访问数据，增加了数据访问的复杂性。
额外标记位（Additional Overhead）：
- 每个缓存块需要额外的标记位（脏位或修改位）来记录缓存块是否已被修改。
- 这增加了缓存的存储开销。

精华所在

写回（Write Back）策略

特点：
- 写操作仅更新缓存，只有当缓存块被替换时，才将数据写回主存。
- 使用脏位（Dirty Bit）标记缓存块是否已被修改。
优点：
- 性能高：减少了主存访问次数，写操作速度快。
- 支持批量写入：同一块的多次写操作只需一次主存更新。
缺点：
- 主存数据一致性问题：主存数据可能失效，I/O模块无法直接读取最新数据。
- 硬件复杂度增加：需要额外的脏位，增加了缓存设计和管理的复杂性。