存储层次设计

1. 局部性原理

存储层次设计的理论基石是局部性原理（Principle of Locality）：

类型	含义	利用方式
时间局部性	最近访问的数据很可能再次被访问	将最近数据保留在快速存储中（缓存）
空间局部性	与当前数据相邻的数据很可能被访问	以块（cache line）为单位传输数据

2. 存储层次全景

graph TB
    A["寄存器<br/>~1 ns | ~1 KB | SRAM"] --> B["L1 Cache<br/>~1-2 ns | 32-128 KB | SRAM"]
    B --> C["L2 Cache<br/>~3-10 ns | 256 KB-1 MB | SRAM"]
    C --> D["L3 Cache<br/>~10-30 ns | 4-64 MB | SRAM"]
    D --> E["主存 DRAM<br/>~50-100 ns | 8-128 GB | DRAM"]
    E --> F["SSD<br/>~10-100 μs | 256 GB-8 TB | Flash"]
    F --> G["HDD<br/>~5-10 ms | 1-20 TB | 磁盘"]

    style A fill:#e8f5e9
    style B fill:#c8e6c9
    style C fill:#a5d6a7
    style D fill:#81c784
    style E fill:#fff9c4
    style F fill:#ffe0b2
    style G fill:#ffccbc

核心设计目标：以接近最快存储的速度、接近最慢存储的容量和成本来运行程序。

3. 平均存储访问时间（AMAT）

\[ \text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty} \]

对于多级缓存：

\[ \text{AMAT} = t_{L1} + r_{L1} \times (t_{L2} + r_{L2} \times (t_{L3} + r_{L3} \times t_{\text{mem}})) \]

数值示例

设 L1 命中时间 = 1 ns，L1 miss rate = 5%，miss penalty（访问主存）= 100 ns：

\[\text{AMAT} = 1 + 0.05 \times 100 = 1 + 5 = 6 \text{ ns}\]

如果 L1 miss rate 从 5% 降到 2%：

\[\text{AMAT} = 1 + 0.02 \times 100 = 3 \text{ ns}\]

AMAT 减半——说明降低 miss rate 的巨大价值。

4. Cache 基本原理

4.1 Cache 行结构

每个 cache line 包含：

[Valid Bit(1)] [Dirty Bit(1)] [Tag(t bits)] [Data Block(B bytes)]

地址分解（\(m\) 位地址，\(2^s\) 组，每组 \(E\) 路，块大小 \(B = 2^b\) 字节）：

\[ \underbrace{\text{Tag}}_{t = m - s - b} \quad \underbrace{\text{Set Index}}_{s} \quad \underbrace{\text{Block Offset}}_{b} \]

4.2 映射方式

graph LR
    subgraph "直接映射 Direct-Mapped"
        A1[地址] -->|唯一映射| B1[1 个位置]
    end
    subgraph "组相联 Set-Associative"
        A2[地址] -->|映射到组| B2[N 个位置中选1]
    end
    subgraph "全相联 Fully-Associative"
        A3[地址] -->|任意位置| B3[所有位置]
    end

映射方式	组数	每组路数	命中延迟	冲突 miss	硬件复杂度
直接映射	\(C/B\)	1	最低	最高	最低
\(N\) 路组相联	\(C/(N \cdot B)\)	\(N\)	中等	中等	中等
全相联	1	\(C/B\)	最高	最低	最高

典型配置：

L1 Cache：4-8 路组相联（平衡延迟和 miss rate）
L2 Cache：8-16 路组相联
TLB：全相联（条目少，需最低 miss rate）

4.3 替换策略

当 cache 组满时需要选择驱逐哪一行：

策略	原理	优劣
LRU	替换最久未使用的行	最优但高路数下硬件成本高
Pseudo-LRU	树形近似 LRU	低成本近似
Random	随机选择	简单；高路数下接近 LRU
FIFO	先进先出	简单但可能替换热数据

5. Cache Miss 分类——3C 模型

类型	英文	原因	优化方式
强制 miss	Compulsory	首次访问，数据从未在 cache 中	预取（Prefetching）
容量 miss	Capacity	cache 总容量不足以容纳工作集	增大 cache 容量
冲突 miss	Conflict	多个地址映射到同一组	增大相联度；Victim cache

第四种——一致性 miss（Coherence miss）：多核环境下其他核心的写操作使本地 cache 行失效。

6. 写策略

写命中

策略	行为	优劣
Write-Through	同时写 cache 和下级存储	一致性简单，带宽消耗大
Write-Back	仅写 cache，dirty 行被替换时才写回	减少写流量，需 dirty bit

写未命中

策略	行为
Write-Allocate	先将块取入 cache，再写入（配合 write-back）
No-Write-Allocate	直接写入下级存储（配合 write-through）

现代处理器几乎都采用 Write-Back + Write-Allocate 组合。

7. Cache 优化技术

7.1 降低 Miss Rate

增大块大小：利用空间局部性（但过大导致容量和冲突 miss 增加）
增大 Cache 容量：减少容量 miss（但增大面积和延迟）
增大相联度：减少冲突 miss（经验规则：2:1 规则——\(N\) 路的 miss rate ≈ \(N/2\) 路直接映射的 miss rate）
Victim Cache：小型全相联 cache 保存被驱逐的行

7.2 降低 Miss Penalty

多级 Cache：L1（小快）→ L2 → L3（大慢）
Critical Word First：请求的字先返回，CPU 立即使用
Early Restart：所需字到达后立即重启 CPU

7.3 降低 Hit Time

小而简单的 L1 Cache：直接映射或低相联度
Way Prediction：预测命中哪一路，先比较该路
虚拟索引物理标签（VIPT）：用虚拟地址索引+物理地址比较tag，并行化

7.4 预取（Prefetching）

硬件预取：检测访问模式（stride、stream），自动预取后续块
软件预取：编译器/程序员插入预取指令（__builtin_prefetch）

8. 虚拟内存

8.1 基本概念

虚拟内存为每个进程提供独立、连续的地址空间，由操作系统和硬件协同管理。

核心功能：

地址隔离：进程间相互独立
内存保护：权限控制（读/写/执行）
需求分页：仅将活跃页面加载到物理内存
共享：多个进程可共享物理页面（如共享库）

8.2 页表（Page Table）

虚拟地址 → 物理地址的映射：

\[ \text{VA} = \underbrace{\text{VPN}}_{\text{虚拟页号}} + \underbrace{\text{Offset}}_{\text{页内偏移}} \]

\[ \text{PA} = \underbrace{\text{PPN}}_{\text{物理页号}} + \underbrace{\text{Offset}}_{\text{页内偏移}} \]

页表项（PTE） 包含：

字段	功能
PPN	物理页号
Valid	是否在物理内存中
Dirty	是否被修改
Reference	是否被访问（用于替换算法）
Protection	读/写/执行权限

8.3 多级页表

单级页表占用连续内存太大（64-bit 地址 + 4KB 页 → \(2^{52}\) 个 PTE）。

多级页表按需分配：

x86-64：4 级页表（PML4 → PDPT → PD → PT），每级 9 位索引
RISC-V Sv48：4 级页表
实际只为已使用的虚拟地址范围分配页表页

8.4 TLB（Translation Lookaside Buffer）

页表查找需要多次内存访问（4 级 = 4 次），TLB 是页表的硬件缓存：

\[ \text{Effective Access Time} = t_{\text{TLB}} \times h + (t_{\text{TLB}} + t_{\text{page walk}}) \times (1 - h) \]

其中 \(h\) 为 TLB 命中率。