组成（1）：CPU Cache 与局部性

6 分钟阅读

发布于： January 01, 2019

前言

CPU Cache 是现代计算机系统性能的关键，它通过利用程序的局部性原理，大幅提升了内存访问速度。理解 Cache 的工作原理和局部性的影响，不仅是掌握计算机组成原理的关键，更是进行性能优化的基础。本文将从原理、实现、性能等多个维度深入解析 CPU Cache 和局部性，帮助读者全面理解这一重要机制。

1. 为什么需要 Cache

CPU 计算越来越快，但内存访问相对更慢。 Cache 的目标是：把“可能马上要用的数据”放在更快的层级里（L1/L2/L3）。

2. 两种局部性

时间局部性：刚用过的数据，短时间内还会再用
空间局部性：访问某个地址后，附近地址很可能也会被访问

这也是为什么顺序扫描通常比随机访问更快。

3. CPU Cache 的层次结构

3.1 多级 Cache 架构

现代 CPU 通常采用多级 Cache 架构：

graph TD
    A[CPU核心] --> B[L1 Cache]
    B --> C[L2 Cache]
    C --> D[L3 Cache]
    D --> E[主内存]
    
    B --> F[L1指令Cache]
    B --> G[L1数据Cache]
    
    style A fill:#e3f2fd
    style B fill:#fff3e0
    style C fill:#f3e5f5
    style D fill:#e8f5e9
    style E fill:#ffebee

Cache 层次特征：

层级	容量	延迟	位置
L1	32-64KB	1-3 周期	CPU 核心内
L2	256KB-1MB	10-20 周期	CPU 核心内
L3	8-32MB	40-75 周期	共享
主内存	GB 级	100-300 周期	片外

3.2 Cache 的组织方式

Cache 通常采用组相联（Set-Associative）组织方式：

graph LR
    A[内存地址] --> B[Tag]
    A --> C[Set Index]
    A --> D[Offset]
    
    C --> E[Cache Set]
    E --> F[Way 0]
    E --> G[Way 1]
    E --> H[Way N]
    
    F --> I[Tag比较]
    G --> I
    H --> I
    
    I -->|匹配| J[Cache Hit]
    I -->|不匹配| K[Cache Miss]
    
    style A fill:#e3f2fd
    style E fill:#fff3e0
    style J fill:#e8f5e9
    style K fill:#ffebee

4. 局部性原理的深入分析

4.1 时间局部性（Temporal Locality）

时间局部性是指：刚访问过的数据，短时间内很可能再次被访问。

// 时间局部性的例子
int sum = 0;
for (int i = 0; i < 1000; ++i) {
    sum += array[i];  // array[i] 在循环中多次访问，时间局部性好
}

4.2 空间局部性（Spatial Locality）

空间局部性是指：访问某个地址后，附近地址很可能也会被访问。

// 空间局部性的例子
for (int i = 0; i < 1000; ++i) {
    process(array[i]);  // 顺序访问，空间局部性好
}

// 随机访问，空间局部性差
for (int i = 0; i < 1000; ++i) {
    int index = random() % 1000;
    process(array[index]);  // 随机访问，空间局部性差
}

4.3 局部性对性能的影响

graph TD
    A[程序访问模式] --> B{局部性好?}
    B -->|是| C[Cache命中率高]
    B -->|否| D[Cache命中率低]
    
    C --> E[性能好]
    D --> F[性能差]
    
    G[顺序访问] --> C
    H[随机访问] --> D
    I[重复访问] --> C
    J[一次性访问] --> D
    
    style C fill:#e8f5e9
    style D fill:#ffebee
    style E fill:#e3f2fd
    style F fill:#fff3e0

5. Cache 替换策略

5.1 常见的替换策略

LRU（Least Recently Used）：淘汰最近最少使用的 Cache line
FIFO（First In First Out）：淘汰最早进入的 Cache line
Random：随机淘汰

5.2 LRU 的实现

graph LR
    A[Cache访问] --> B{Cache Hit?}
    B -->|是| C[更新LRU顺序]
    B -->|否| D[Cache Miss]
    D --> E[选择Victim]
    E --> F[LRU策略]
    F --> G[淘汰最久未使用]
    G --> H[加载新数据]
    
    style B fill:#e3f2fd
    style D fill:#ffebee
    style F fill:#fff3e0

6. 实际工程案例

6.1 数据结构对 Cache 性能的影响

// 数组：顺序访问，Cache 友好
int sum_array(int* arr, int n) {
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += arr[i];  // 顺序访问，空间局部性好
    }
    return sum;
}

// 链表：随机访问，Cache 不友好
int sum_list(Node* head) {
    int sum = 0;
    while (head) {
        sum += head->value;  // 随机访问，空间局部性差
        head = head->next;
    }
    return sum;
}

// False Sharing：多个变量在同一 Cache line，导致性能下降
struct BadAlignment {
    int counter1;  // 与 counter2 在同一 Cache line
    int counter2;  // 不同线程写这两个变量会导致 Cache line 失效
};

// 解决：使用 padding 或 alignas 分离
struct GoodAlignment {
    alignas(64) int counter1;  // 64 字节对齐，确保不在同一 Cache line
    alignas(64) int counter2;
};

7. 性能分析与优化

7.1 Cache 性能指标

Cache Hit Rate：Cache 命中率，越高越好
Cache Miss Penalty：Cache miss 的代价，取决于内存延迟
AMAT（Average Memory Access Time）：平均内存访问时间

7.2 性能优化策略

提升局部性：
- 顺序访问而非随机访问
- 重用数据而非一次性访问
- 紧凑的数据结构
减少 False Sharing：
- 使用 padding 分离热点变量
- 使用 alignas 确保对齐
预取优化：
- 使用 __builtin_prefetch 预取数据
- 编译器自动预取

7.3 Cache 访问流程

sequenceDiagram
  participant CPU as CPU
  participant L1 as L1 Cache
  participant L2 as L2 Cache
  participant L3 as L3 Cache
  participant Mem as Memory

  CPU->>L1: 访问地址
  L1->>L1: 查找 Cache
  
  alt L1 Hit
    L1-->>CPU: 返回数据 (1-3周期)
  else L1 Miss
    L1->>L2: 查找 Cache
    alt L2 Hit
      L2-->>L1: 返回数据
      L1-->>CPU: 返回数据 (10-20周期)
    else L2 Miss
      L2->>L3: 查找 Cache
      alt L3 Hit
        L3-->>L2: 返回数据
        L2-->>L1: 返回数据
        L1-->>CPU: 返回数据 (40-75周期)
      else L3 Miss
        L3->>Mem: 访问内存
        Mem-->>L3: 返回数据
        L3-->>L2: 更新 Cache
        L2-->>L1: 更新 Cache
        L1-->>CPU: 返回数据 (100-300周期)
      end
    end
  end

7.4 AMAT 计算

平均内存访问时间（AMAT）的计算公式：

AMAT = Hit Time + Miss Rate × Miss Penalty

对于多级 Cache：

AMAT = L1 Hit Time + L1 Miss Rate × (L2 Hit Time + L2 Miss Rate × (L3 Hit Time + L3 Miss Rate × Memory Access Time))

flowchart TD
  A[AMAT 计算] --> B[L1 Hit Time]
  A --> C[L1 Miss Rate]
  A --> D[Miss Penalty]
  
  C --> E[L2 Hit Time]
  C --> F[L2 Miss Rate]
  F --> G[L3 Hit Time]
  F --> H[L3 Miss Rate]
  H --> I[Memory Access Time]
  
  B --> J[总延迟]
  E --> J
  G --> J
  I --> J

7.5 性能优化示例

// 优化前：随机访问，Cache 不友好
void process_random(int* data, int* indices, int n) {
    for (int i = 0; i < n; ++i) {
        process(data[indices[i]]);  // 随机访问，Cache miss 率高
    }
}

// 优化后：排序索引，提高局部性
void process_optimized(int* data, int* indices, int n) {
    // 按索引排序，提高空间局部性
    std::sort(indices, indices + n);
    for (int i = 0; i < n; ++i) {
        process(data[indices[i]]);  // 顺序访问，Cache 友好
    }
}

8. 实际性能测试案例

8.1 顺序访问 vs 随机访问

测试不同访问模式对性能的影响：

// 顺序访问测试
void test_sequential_access(int* arr, int n) {
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += arr[i];
    }
}

// 随机访问测试
void test_random_access(int* arr, int* indices, int n) {
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += arr[indices[i]];
    }
}

性能对比（n=1M，数组大小 4MB）：

顺序访问：~10ms
随机访问：~50ms

差异主要来自 Cache miss 率：

顺序访问：Cache miss 率 < 1%
随机访问：Cache miss 率 > 50%

8.2 数据结构选择的影响

flowchart TD
  A[数据结构选择] --> B[数组]
  A --> C[链表]
  A --> D[树]
  
  B --> E[顺序访问]
  E --> F[Cache 友好]
  F --> G[性能好]
  
  C --> H[随机访问]
  H --> I[Cache 不友好]
  I --> J[性能差]
  
  D --> K[部分顺序]
  K --> L[中等性能]

// 测试 False Sharing 的影响
struct Counter {
    alignas(64) int count1;  // 分离到不同 Cache line
    alignas(64) int count2;
};

void test_false_sharing() {
    Counter c;
    // 两个线程分别写 count1 和 count2
    // 如果不在同一 Cache line，性能好
    // 如果在同一 Cache line，性能差（Cache line 乒乓）
}

性能影响：

无 False Sharing：吞吐 ~100M ops/s
有 False Sharing：吞吐 ~10M ops/s

9. 设计模式与架构原则

8.1 设计模式视角

CPU Cache 体现了多个设计模式：

缓存模式：通过缓存提高访问速度
分层模式：多级 Cache 形成层次结构
替换策略模式：不同的替换策略适用于不同场景

8.2 架构原则

局部性原理：利用程序的局部性提高 Cache 命中率
层次化设计：多级 Cache 平衡容量和速度
性能优化：通过多种机制优化 Cache 性能

9. 小结

CPU Cache 是现代计算机系统性能的关键，它通过利用程序的局部性原理，大幅提升了内存访问速度。

核心概念总结：

Cache 原理：通过多级 Cache 层次结构提高内存访问速度
局部性原理：时间局部性和空间局部性是 Cache 性能的基础
替换策略：LRU 等策略决定哪些数据保留在 Cache 中
性能优化：通过提升局部性、减少 False Sharing 等优化性能

设计亮点：

多级层次：L1/L2/L3 Cache 形成层次结构，平衡容量和速度
局部性利用：通过时间局部性和空间局部性提高命中率
智能替换：通过 LRU 等策略保留最可能使用的数据
预取机制：通过硬件和软件预取提前加载数据
性能优化：通过多种机制优化 Cache 性能

关键要点：

局部性几乎决定了性能上限，顺序访问比随机访问快得多
数据结构设计会影响 cache miss，数组通常比链表更 Cache 友好
访问模式会影响预取效果，顺序访问可以充分利用预取
False sharing 会让多线程性能崩掉，需要合理对齐和分离
理解 Cache 和局部性是进行性能优化的基础

掌握 CPU Cache 和局部性的原理，可以更好地进行性能优化和系统设计。

前言