关于内存 | diefish's blog

如何更好更快地访问内存是 HPC 中最大的瓶颈之一，仅仅了解 SIMD 或并行编程接口是不足够的，本文将梳理计算机的内存层次结构、缓存友好编程、内存墙现象、NUMA 架构以及预取技术。

Understanding Memory Hierarchy

为了充分利用现代 CPU 的性能，我们必须理解数据是如何在不同层级的内存组件之间流动的。

Registers, Caches, and Main Memory

寄存器 (Registers)： CPU 内置的、容量最小但速度最快的数据存储单元，用于存储正在被 CPU 活跃操作的数据。CPU 直接在寄存器上执行大部分计算。
缓存 (Cache)：位于 CPU 和主内存之间的小容量、高速存储区域。它们的目的是通过存储最可能被 CPU 再次访问的数据来减少对主内存的访问延迟。
- L1 缓存 (Level 1 Cache)：最小、最快，通常分为数据缓存 (L1d) 和指令缓存 (L1i)，每个 CPU 核心独有。其访问速度与 CPU 核心时钟周期相近。
- L2 缓存 (Level 2 Cache)：比 L1 大且慢，每个 CPU 核心独有或由几个核心共享。
- L3 缓存 (Level 3 Cache)：最大、最慢的缓存，通常由同一 CPU 插槽上的所有核心共享。
主内存 (Main Memory/RAM)：容量远大于缓存，但访问速度慢得多。当数据不在任何缓存中时，CPU 必须从主内存中获取。
TLB (Translation Lookaside Buffer)： TLB 是一个专用的高性能缓存，用于存储虚拟地址到物理地址的转换映射。当 CPU 访问一个虚拟地址时，它首先检查 TLB。如果找到对应的物理地址（TLB 命中），则可以快速进行内存访问；如果未找到（TLB 未命中），则需要查询页表，这将导致显著的延迟。理解 TLB 对于优化内存页访问模式，尤其是在处理大型数据集时至关重要。

通过这种多级内存层次结构访问内存，我们需要尽可能满足局部性原理来提高效率：

时间局部性 (Temporal Locality)：如果一个数据项最近被访问过，那么它很可能在不久的将来再次被访问。
空间局部性 (Spatial Locality)：如果一个数据项被访问了，那么它附近的内存地址中的数据项也很可能在不久的将来被访问。

Cache-Friendly Programming

编写“缓存友好”的代码意味着组织数据和访问模式，最大化缓存命中率。

Cache Line and Performance Impact

缓存行 (Cache Line)：缓存和主内存之间数据传输的最小单元，通常为 64 字节。当 CPU 从主内存中请求一个字节时，整个缓存行都会被加载到缓存中。
- 这强调了空间局部性：如果你的程序按顺序访问内存，那么一次缓存加载可以为未来的访问提供多个数据项，从而提高效率。
- 伪共享 (False Sharing)：如果两个或多个独立的变量不幸地位于同一个缓存行中，并且被不同的 CPU 核心修改，那么即使它们逻辑上不相关，也会因为缓存一致性协议导致大量的缓存行失效和重新加载，从而严重影响性能。

Cache Hit/Miss and Coherence

缓存命中 (Cache Hit)：当 CPU 需要的数据已经在某个缓存级别中时，访问速度非常快。
缓存未命中 (Cache Miss)：当 CPU 需要的数据不在任何缓存中时，必须从更慢的内存级别（最终是主内存）获取数据，这会引入延迟。未命中可分为：
- 强制性未命中 (Compulsory Miss/Cold Miss)：首次访问数据。
- 容量性未命中 (Capacity Miss)：缓存太小，无法容纳所有活跃数据。
- 冲突性未命中 (Conflict Miss)：多个数据项映射到缓存中的同一个位置。
缓存一致性 (Cache Coherence)：在多核处理器系统中，不同的核心可能有同一份数据在各自的缓存副本中。为了确保所有核心看到的数据是一致的最新版本，需要缓存一致性协议，如 MESI (Modified, Exclusive, Shared, Invalid) 协议。理解这些协议有助于避免伪共享等问题。

SoA vs. AoS

选择正确的数据布局对缓存性能至关重要。这部分在 HPC 中的 C 和 C++ 中也有提及。

结构体数组 (AoS: Array of Structs)： struct Point { float x, y, z; } points[N];
- 这种布局下，一个 Point 结构体的所有成员在内存中是连续的。如果你的代码经常需要访问一个点的所有坐标，这种布局是高效的。
数组结构体 (SoA: Struct of Arrays)： struct { float x[N], y[N], z[N]; } points_soa;
- 如果你需要对所有点的 $ x $ 坐标执行操作，那么可以高效地利用缓存行，因为内存访问是高度连续的。对于 SIMD 向量化操作来说，SoA 通常更优化。

选择 SoA 还是 AoS 取决于数据访问模式：如果经常需要访问一个对象的所有属性，AoS 可能更好（但要注意缓存行对齐和填充）。如果经常需要对多个对象的某个特定属性进行批处理操作，SoA 通常是更好的选择。

The Memory Wall

内存墙是指 CPU 的计算速度与主内存的访问速度之间日益扩大的差距。CPU 处理能力的增长远远快于内存延迟的改进速度，这意味着即使 CPU 理论上可以执行大量的指令，但如果它必须经常等待数据从主内存中加载，那么大部分时间都会处于空闲状态，从而限制了实际的应用程序性能。

解决方案：

优化算法，减少对内存的访问次数。
最大化缓存命中率，利用数据局部性。
采用预取技术来隐藏内存访问延迟。

NUMA Architectures

Non-Uniform Memory Access Challenges

NUMA (Non-Uniform Memory Access) ，即非一致性内存访问架构，在多处理器系统中变得越来越普遍。在 NUMA 系统中，每个 CPU (或 CPU 插槽) 都有一组直接连接的本地内存，访问本地内存比访问连接到另一个 CPU 的远端内存要快得多。不同的内存器件和 CPU 核心从属不同的 Node，每个 Node 都有自己的集成内存控制器（IMC，Integrated Memory Controller）。

如果一个线程在 CPU0 上运行，却频繁访问挂载在 CPU1 上的内存，性能会显著下降，因为数据必须通过处理器间互连（如 Intel 的 UPI 或 AMD 的 Infinity Fabric）传输，这会引入额外的延迟。

不当的内存放置策略可能导致严重的性能瓶颈，甚至超过内存墙的限制。

NUMA Optimization with `numactl`

为了在 NUMA 架构下获得最佳性能，我们必须确保计算尽可能地在靠近其所访问数据的 CPU 核心上进行。numactl 是一个强大的 Linux 命令行工具，它允许我们精确控制进程的 CPU 亲和性和内存分配策略。

查看 NUMA 节点布局：numactl --hardware 命令可以显示系统中所有的 NUMA 节点、每个节点的 CPU 核心及其本地内存大小。

1
numactl --hardware

输出示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
available: 2 nodes (0-1)
node 0 cpus: 0 1 2 3
node 0 size: 16000 MB
node 0 free: 15000 MB
node 1 cpus: 4 5 6 7
node 1 size: 16000 MB
node 1 free: 15000 MB
node distances:
node   0   1
  0:  10  21
  1:  21  10

这表示系统有 2 个 NUMA 节点（0 和 1）。节点 0 拥有 CPU 核心 0-3，节点 1 拥有 CPU 核心 4-7。node distances 表示访问本地内存的成本为 10，访问远端内存的成本为 21，远端访问的开销约为本地的两倍。

重要 numactl 选项：
- --cpunodebind <nodes>：将进程或线程绑定到指定 NUMA 节点上的 CPU 核心。例如，--cpunodebind=0 将进程限制在节点 0 上的 CPU。
- --membind <nodes>：强制所有内存分配都来自指定 NUMA 节点。例如，--membind=1 将所有内存都从节点 1 分配。
- --localalloc：在当前线程运行的 NUMA 节点上分配内存。这是最佳实践，因为它确保了数据存储在距离计算最近的位置。
- --physcpubind <cpus>：将进程或线程绑定到特定的物理 CPU 核心。

NUMA Memory Access Test

可以通过一个简单的多线程数组求和程序来演示 numactl 对 NUMA 性能的影响。程序会分配一个非常大（足够超出 cache）的数组，然后使用 OpenMP 让多个线程并行计算数组元素的总和。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <numeric>
#include <chrono>
#include <omp.h>
#include <algorithm>

// 确保足够大以超出缓存并触及 NUMA 效应
const size_t ARRAY_SIZE = 1000000000ULL;

int main() {
    std::cout << "Allocating array of " << ARRAY_SIZE * sizeof(long long) / (1024 * 1024 * 1024.0) << " GB..." << std::endl;

    std::vector<long long> data(ARRAY_SIZE);
    #pragma omp parallel for
    for (size_t i = 0; i < ARRAY_SIZE; ++i) {
        data[i] = i % 100;
    }
    std::cout << "Array initialized." << std::endl;

    int num_threads = 2;
    omp_set_num_threads(num_threads);
    std::cout << "Using " << num_threads << " OpenMP threads." << std::endl;

    long long total_sum = 0;
	
    auto start = std::chrono::high_resolution_clock::now();
	
    #pragma omp parallel reduction(+:total_sum)
    {
        int thread_id = omp_get_thread_num();
        size_t chunk_size = ARRAY_SIZE / num_threads;
        size_t start_idx = thread_id * chunk_size;
        size_t end_idx = std::min(start_idx + chunk_size, ARRAY_SIZE);

        std::cout << "Thread " << thread_id << " processing from " << start_idx << " to " << end_idx << std::endl;

        for (size_t i = start_idx; i < end_idx; ++i) {
            total_sum += data[i];
        }
    }
	
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> diff = end - start;
	
    std::cout << "Calculated total sum: " << total_sum << std::endl;
    std::cout << "Time taken: " << diff.count() << " seconds" << std::endl;
	
    return 0;
}

可以使用 GCC 编译这个程序：

1
g++ -std=c++11 -O3 -fopenmp numa_test.cpp -o numa_test

（由于我的电脑只有一个 NUMA 核心，所以下面测试无法进行。。。）

Baseline：

1
./numa_test

远端内存访问：CPU 在节点 1，内存绑定到节点 0。这时所有数据都是远端访问，理论上性能应该最差。

1
numactl --cpunodebind=1 --membind=0 ./numa_test

本地内存访问：CPU 在节点 0，内存绑定到节点 0。这是理性的 NUMA 配置，所有数据访问都是本地的。

1
numactl --cpunodebind=0 --membind=0 ./numa_test

真实多线程场景：CPU 绑定到节点 0 和 1，但内存仅分配到节点 0。跑在节点 1 上的线程将进行远端内存访问。

1
2
export OMP_NUM_THREADS=2
numactl --cpunodebind=0,1 --membind=0 ./numa_test

Prefetching

预取 (Prefetching) 是一种技术，它尝试在 CPU 实际需要数据之前，就将其从较慢的内存层级加载到较快的缓存中。这有助于隐藏内存访问延迟，使 CPU 能够专注于计算。

硬件预取器 (Hardware Prefetcher)：现代 CPU 内置的智能逻辑单元，它们会监控内存访问模式，并根据检测到的模式（如顺序访问）自动预测接下来可能需要哪些数据，将其提前加载到缓存中。
- 优点：全自动，无需程序员干预。
- 缺点：有时预测不准确，可能将无用数据加载到缓存中，挤出有用数据，甚至增加内存总线流量。
编译器预取 (Compiler Prefetching)：一些编译器能够根据代码中的循环和访问模式，在编译时插入预取指令。通过 -O3 等优化选项或特定的编译器提示，可以启用此功能。
软件预取 (Software Prefetching)：程序员可以通过使用特殊的 CPU 指令（通常通过内联函数 Intrinsics 暴露）显式地告诉 CPU 预取哪些数据。例如，在 x86 架构上：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <xmmintrin.h> // For _mm_prefetch

void process_data(int* arr, int n) {
    for (int i = 0; i < n; ++i) {
        // 在实际访问 arr[i + PREFETCH_DISTANCE] 之前提前预取
        if (i + PREFETCH_DISTANCE < n) {
            _mm_prefetch((char*)&arr[i + PREFETCH_DISTANCE], _MM_HINT_T0);
        }
        // 处理 arr[i]
        // ...
    }
}

当硬件预取器无法有效应对复杂的访问模式时，软件预取可以提供更精确的控制。
需要程序员手动插入，可能会增加代码复杂性，不当使用可能导致性能下降。

Summary

在 HPC 领域，仅依靠 CPU 的原始计算能力和并行编程模型是不够的。深入理解计算机内存，是编写高性能代码的基础。通过采用缓存友好的编程，如优化数据布局和分块算法，我们可以显著提高应用程序的性能，真正发挥现代 CPU 的潜力。

Reference

每个程序员都应该知道的 CPU 知识：NUMA（知乎）
浅解 NUMA 机制（知乎）

Understanding Memory Hierarchy#

Registers, Caches, and Main Memory#

Cache-Friendly Programming#

Cache Line and Performance Impact#

Cache Hit/Miss and Coherence#

SoA vs. AoS#

The Memory Wall#

NUMA Architectures#

Non-Uniform Memory Access Challenges#

NUMA Optimization with numactl#

NUMA Memory Access Test#

Prefetching#

Summary#

Reference#