Chapter 5. Memory Hierarchy¶

Memory Hierarchy Overview¶

存储容量和读写速度不可兼得。

Cache的出现解决了主存速度不够快的问题，也是这门课程讨论的重点。

• Hit The CPU accesses the upper level and succeeds
• Miss The CPU accesses the upper level and fails
• Hit time 访问上层存储的时间，包括决定该次访问是否命中所需的时间
• Miss penalty 将上层存储的 Block 替换为下层 Block 所需的时间，包括将这个 Block 传递给处理器所需的时间

Cache¶

• Block 块：cache 和主存(下层)之间信息交互的单元
• Word 字：cache 和 CPU(上层)之间信息交互的单元
• hit 命中：处理器所需数据在本层存储中找到
• miss 失效：处理器所需数据未能在本层存储中找到
• 命中率 ：在访问本层存储时命中的次数占总次数的比例，通常作为层次结构的性能衡量指标之一
• 失效率 ：在访问本层存储时失效的次数占总次数的比例。命中率与失效率相加为1

Directed Mapping¶

常见有三种映射方式：

• 直接映射 Direct Mapping
• 组相联 Set associated
• 全相联 Fully associated

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Cache 地址映射：
+-------+--------+-------+
|标签TAG|索引INDEX|块偏移量|
+-------+--------+-------+

Cache 结构：
+----------------+----------+-------+-------+
|    标签TAG      | 数据DATA | Valid | Dirty |
+----------------+----------+-------+-------+
 64-(n+m+2) bit   2^m*32 bit   1bit   (1bit)

- Valid(1 bit) 表示 Cache 中数据是否有效
- Dirty(1 bit) 表示 Cache 中数据是否是最新且还没写回主存

例如，主存为 64-bit 地址，Cache 含有 \(2^n\) 个 Block，每个 Block 含有 \(2^m\) 个 word：

• Byte Offset m+2 bit
  • 以 byte 为单位的偏移量，即 \(\log _2 (2^m\cdot 4)\) (1 word = 4 byte = 32 bit)
• Cache index n bit
• Tag field 64-(n+m+2) bit

那么该 Cache 的大小为：

Cache Hit & Miss¶

显然，读和写的时候发生 cache miss 的处理方式是不一样的；另外读也有读数据和读指令之分（指令 cache 和数据 cache 通常是分离的）。我们分别对其进行讨论：

Other Mapping¶

• 组相联 Set associated
• 全相联 Fully associated

n-way 组相联将每 n 个 Block 分为一组，找对应 Block 时先确定组号，再搜寻一遍该组 Block 找是否命中。direct mapping 其实就是 1-way set associative，而 fully associative 就是 n-way set associative，其中 n 是 cache block 的个数；我们称一组的大小为 associativity，那么这两种方法的 associativity 就分别是 1 和 n。

替换算法：

• <1> 先入后出算法 FILO
• <2> 随机替换算法 RAND
  • 方法简单，易于实现；命中率较低
• <3> 先入先出算法 FIFO
  • 最先调入并被多次调用的Block可能会被优先替换，不符合局部性规律，所以命中率不满足要求
• <4> 近期最少使用算法 LRU
  • 较好反映了程序局部性规律，命中率较高

考试常考三种 Miss (3C)：

• 冷启动 Miss (Compulsory Miss)
  • 缓存刚上电为空，此时访问什么都是 Miss
• 容量 Miss (Capacity Miss)
  • 指全相联缓存中，内存中的块由于容量不够而被替换，再次访问该块时发生 Miss
• 冲突 Miss (Conflict Miss)
  • 指组相联缓存中，某个组内的块被替换，然后再次访问该块时发生 Miss
  • 如果是全相联则不会发生 Conflict Miss，因为还有别的空位（如果没有空位的话就该计入 Capacity Miss 了）

Performance¶

因此，提高 Cache 性能的关键在于增加命中率和减少 Miss Penalty 时间。

Example 假设：

• instruction cache miss rate: 2%
• data cache miss rate: 4%
• CPI without any memory stall: 2
• miss penalty: 100 cycles
• The frequency of all load and store in gcc: 36%

Solution

• <1> 通过更灵活的Block替换规则来减少 Miss Rate
  • 组相连、LRU...
  • 随着 Assoiciativity 提高，Miss Rate 越来越低（Direct > Set > Full）
• <2> Least Recent Used
  • 随着 Assoiciativity 提高，实现 LRU 算法越来越困难
• <3> 选择合适 Block Size
  • 一般来讲，选择更大的Block可以降低 Miss Rate，但也会带来更大的 Miss Penalty
  • 并且对于一个大小有限的 Cache，更大的Block也意味着更少的Block数量，可能反而增加了 Miss Rate
  • 对于 256KB 往下的Cache，Block Size选 64 bytes 的效果最好
• <4> 设计一个存储系统来减少 Miss Penalty
  • 交叉地址访问...
• <5> 通过多级 Cache 减少 Miss Penalty
  • L1 Cache、L2 Cache...
• <6> Software Optimization Blocking

Virtual Memory¶

Mapping¶

虚拟内存技术可以让多个程序之间高效、安全地共享内存，同时允许单个程序使用超过内存容量的内存。

操作系统会为每一个进程分配一个 Page Table，进程通过虚拟内存这一中介来跟内存和磁盘读写信息。

虚拟地址转换到物理地址分为两步：

• <1> 根据 Virtual page number 读取 Page Table 上对应数据，记作 Physical page number
  • 如果 Valid 位为0，说明不在 DRAM 中，要去 Disk 中找
• <2> 将 Physical page number 与 Page Offset 合并，得到物理地址

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Virtual Address:
+---------------------+-------------+
| Virtual page number | Page Offset |
+---------------------+-------------+
      || Translation
      \/
Physical Address:
+----------------------+-------------+
| Physical page number | Page Offset |
+----------------------+-------------+

由于 Virtual Memory 处于较下层的位置，如果出现 Page Fault 的情况，造成的性能损失会相当大，因此优化的主要目标在于减少 Page Fault 的发生。

所以，Virtual Memory 采用 LRU、全相联映射的方式来处理 Page，从而减小失效率；同样，Write Through 写 Disk 的代价也是非常昂贵的，所以使用Write Back（这也需要为 Page Table 增加 Dirty 位）。

Translation-lookaside Buffer¶

每个进程的 Page Table 都存放在内存中；而 Page Table Register 则存放着该 Page Table 的物理地址，因此进行 Translation 时将 Virtual Page Number 对应的偏移量和 Page Table 的物理地址相加即可得到该 Entry 的地址。

但是上述方法存在效率问题，当进程希望访问内存中的数据时，都需要先访问内存中的 Page Table 以获取数据的物理地址，这意味着对内存访问时间会加倍。

一种解决方法是使用 TLB，其作用相当于 Page Table 的高速缓存，位于进程和内存中间。其基本的 Entry 结构为：

1
2
3
4
5
6
7

+-----+-----+---+---------------+-------------------------+
|Valid|Dirty|Ref|      Tag      |  Physical Page Address  |
+-----+-----+---+---------------+-------------------------+

- Reference 位: 最近是否被访问过，操作系统会定期清零该位
- TLB: 16-512 Entries
- Miss Rate: 0.01% - 1%

当 TLB Miss 时，处理器才会去内存中的 Page Table 找对应项；如果 Page Table 对应项是 Valid 的，则将其拿到 TLB 中；如果 Page Table 对应项不是 Valid 的，则触发 Page Fault，要继续向下层读取；若被替换的 Entry 的 Dirty 位为 1，则要将其写回 Page Table。