第06章：存储器层次结构

万能的金字塔模型

导读

如果要用一句话概括计算机系统性能的核心矛盾，那就是：CPU 的处理速度与存储器的访问速度之间存在着巨大的、且在不断扩大的鸿沟。

现代处理器的时钟频率已经达到数 GHz，每个时钟周期可以执行多条指令，但主存（DRAM）的访问延迟却停留在数十到数百纳秒的水平。一次主存访问大约需要 200-300 个处理器时钟周期——这意味着如果 CPU 需要等待数据从主存到达，它将空闲相当于执行数百条指令的时间。这种速度差距在几十年间不仅没有缩小，反而在持续扩大。

为了弥合这道鸿沟，计算机体系结构的设计者们引入了一种优雅而高效的解决方案：存储器层次结构（Memory Hierarchy）。其核心思想是利用局部性原理（Principle of Locality），在 CPU 和主存之间插入一级或多级高速缓存（Cache），这些缓存使用速度更快但容量更小、成本更高的 SRAM 技术，将 CPU 最近可能用到的数据副本保存在距离处理器更近的位置。

存储器层次结构是计算机科学中最重要、最优雅的设计思想之一。它不仅体现在 CPU 缓存的设计中，还广泛存在于操作系统的虚拟内存管理、文件系统的页缓存、网络的内容分发网络（CDN）、数据库的缓冲池、甚至 Web 浏览器的缓存机制中。理解存储器层次结构的工作原理，对于编写高性能程序、理解系统软件的设计决策、以及进行系统级的性能调优都至关重要。

本章将从存储技术的基础知识开始，逐步深入到局部性原理、缓存的组织方式、缓存的读写策略，最终构建出完整的存储器层次结构图景。

核心概念详解

一、存储技术概览

计算机系统使用多种不同类型的存储设备，它们在速度、容量、成本、易失性等方面各有特点。理解这些存储技术的基本特性，是理解存储器层次结构设计的基础。

随机访问存储器（RAM）

RAM 是计算机的主存储器，CPU 可以直接通过地址总线和数据总线访问其中的任意位置。RAM 分为两大类：

SRAM（静态随机访问存储器）：每个存储位由 6 个晶体管组成的触发器电路保存。只要保持供电，SRAM 中的数据就会稳定保持，无需刷新。SRAM 的访问速度极快（1-10 纳秒），但每个存储位需要 6 个晶体管，导致其集成度低、成本高、功耗大。SRAM 主要用于制造 CPU 缓存（L1、L2、L3 Cache）。

DRAM（动态随机访问存储器）：每个存储位由一个晶体管和一个电容组成。电容会随时间漏电，因此需要定期刷新（通常每 64 毫秒一次）来保持数据。DRAM 的访问速度比 SRAM 慢（50-100 纳秒），但每个存储位只需要一个晶体管和一个电容，集成度远高于 SRAM，成本也更低。DRAM 用于制造计算机的主存（内存条）。

DRAM 的内部结构并非简单的二维数组，而是由多个bank（存储体）组成的三维结构。每个 bank 内部又由行（row）和列（column）组织。访问 DRAM 的过程包括：先发送行地址（激活一行到行缓冲区），再发送列地址（从行缓冲区中读取特定列的数据）。这种结构导致了 DRAM 的访问延迟由行选通延迟（tRCD）、列选通延迟（CL/tCAS）、行预充电时间（tRP）等多个参数组成。

DDR（Double Data Rate）SDRAM 是目前主流的 DRAM 技术。DDR 通过在时钟信号的上升沿和下降沿都传输数据，将数据传输率提高了一倍。从 DDR1 到 DDR5，每一代都在频率、带宽和能效方面有显著提升。DDR5 的数据速率已达到 4800-6400 MT/s 甚至更高。

磁盘存储

传统硬盘驱动器（HDD）使用旋转的磁性盘片来存储数据。数据以同心圆状的磁道（Track）组织，每个磁道又被分为多个扇区（Sector，通常 512 字节或 4KB）。磁盘的访问时间由三部分组成：

寻道时间（Seek Time）：磁头移动到目标磁道所需的时间，典型值 3-15 毫秒。

旋转延迟（Rotational Latency）：等待目标扇区旋转到磁头下方的时间，平均为旋转周期的一半。对于 7200 RPM 的硬盘，平均旋转延迟约为 4.17 毫秒。

传输时间（Transfer Time）：数据从磁盘表面读取并传输到控制器的时间。

磁盘的访问时间（毫秒级）与 DRAM 的访问时间（纳秒级）之间相差约 100 万倍。这个巨大的速度差距是引入缓存和 SSD 的重要原因。

固态硬盘（SSD）

固态硬盘使用 NAND Flash 闪存技术来存储数据，没有机械运动部件。闪存是一种特殊的 EEPROM（电可擦可编程只读存储器），以块（Block）为单位进行擦除，以页（Page）为单位进行读写。

SSD 的主要优势：

访问速度极快：随机读取延迟通常在 50-200 微秒，比 HDD 快 100-1000 倍。
无噪音、低功耗：没有旋转盘片和移动磁头。
抗震性好：没有机械部件，适合移动设备。

但 SSD 也有一些独特的限制：

写入放大（Write Amplification）：由于闪存必须以块为单位擦除，即使只修改一个字节，也需要将整个块读出、修改、写入新位置，导致实际写入量大于逻辑写入量。
有限的擦写寿命：每个闪存块的擦写次数有限（SLC 约 10 万次，MLC 约 1 万次，TLC 约 1000 次，QLC 约 100 次）。SSD 控制器使用磨损均衡（Wear Leveling）算法来均匀分配擦写操作，延长整体寿命。
垃圾回收（Garbage Collection）：随着使用时间的增长，SSD 需要定期整理无效数据块，可能影响性能。TRIM 命令可以帮助 SSD 更高效地进行垃圾回收。

闪存技术正从 2D 平面结构向 3D NAND（多层垂直堆叠）发展，通过增加层数来提高存储密度和降低成本。目前主流的 3D NAND 已经达到 200 层以上。

二、局部性原理

局部性原理（Principle of Locality）是存储器层次结构得以有效工作的理论基础。它指出：程序在执行过程中，倾向于在较短的时间段内重复访问相同或相近的内存区域。局部性分为两种类型：

时间局部性（Temporal Locality）

时间局部性是指：如果一个存储位置当前正在被访问，那么在不久的将来它很可能再次被访问。

时间局部性的典型来源包括：

循环结构：循环体内的指令在每次迭代中都会被执行，具有极好的时间局部性。
局部变量：函数中的局部变量在函数执行期间会被反复使用。
热点数据：某些数据结构（如计数器、标志位、常用配置）会被频繁访问。

时间局部性是缓存能够工作的最基本原因——如果最近被访问的数据很快又会被访问，那么将它保存在快速的缓存中就能避免重复访问慢速的主存。

空间局部性（Spatial Locality）

空间局部性是指：如果一个存储位置当前正在被访问，那么在不久的将来它附近的存储位置也很可能被访问。

空间局部性的典型来源包括：

顺序执行的指令：程序计数器（PC）通常顺序递增，指令的访问具有极好的空间局部性（遇到跳转指令时除外）。
数组遍历：数组在内存中连续存储，顺序遍历数组时，相邻元素会被依次访问。
结构体访问：访问结构体的某个字段后，很可能紧接着访问同一结构体的其他字段。

空间局部性是缓存行（Cache Line）设计的理论基础。缓存不是以单个字节为单位进行传输的，而是以缓存行（通常为 64 字节）为单位。当一个字节被访问时，它所在的整个缓存行都会被从主存加载到缓存中，这样后续对同一缓存行内其他字节的访问就可以直接在缓存中完成。

局部性的量化分析

可以通过分析代码来评估其局部性：

// 良好的空间局部性：顺序遍历数组
int sum_array(int *arr, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}

// 较差的空间局部性：跳跃式遍历数组
int sum_array_stride(int *arr, int n, int stride) {
    int sum = 0;
    for (int i = 0; i < n; i += stride) {
        sum += arr[i];
    }
    return sum;
}

// 良好的时间局部性：循环中反复使用同一变量
int dot_product(int *a, int *b, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i] * b[i];
    }
    return sum;
}

sum_array 具有极好的空间局部性——每次迭代访问的数组元素与前一次相邻。sum_array_stride 的空间局部性随着 stride 的增大而恶化——当 stride 大于缓存行大小（64 字节 / 4 字节 = 16 个 int）时，每次访问都会导致缓存未命中。dot_product 同时具有良好的空间局部性（顺序遍历两个数组）和时间局部性（sum 变量在每次迭代中都被使用）。

局部性与矩阵遍历顺序

局部性原理在多维数组遍历中的影响尤为显著：

#define N 1024
int matrix[N][N];

// 行优先遍历：良好的空间局部性
int sum_rows() {
    int sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            sum += matrix[i][j];
        }
    }
    return sum;
}

// 列优先遍历：较差的空间局部性
int sum_cols() {
    int sum = 0;
    for (int j = 0; j < N; j++) {
        for (int i = 0; i < N; i++) {
            sum += matrix[i][j];
        }
    }
    return sum;
}

在 C 语言中，二维数组按行优先（Row-Major）顺序存储——matrix[0][0]、matrix[0][1]、...、matrix[0][N-1]、matrix[1][0]、... 在内存中是连续的。sum_rows 按行遍历，每次访问的元素与前一次相邻，具有极好的空间局部性。而 sum_cols 按列遍历，每次访问的元素间隔 N 个 int（4096 字节），远远超过缓存行大小，导致几乎每次访问都是缓存未命中。

在 N = 1024 的情况下，matrix 的大小为 4MB，远大于典型的 L1 缓存（32KB）但小于 L3 缓存。sum_rows 的 L1 缓存命中率接近 100%（每次缓存行加载后，连续 16 次访问都命中），而 sum_cols 的 L1 缓存命中率接近 0%。实际测试中，sum_rows 的执行速度可能是 sum_cols 的 10-50 倍。

三、缓存的组织方式

缓存（Cache）是存储器层次结构的核心组件。理解缓存的组织方式对于编写缓存友好的程序至关重要。

缓存的基本结构

一个通用的缓存由一组缓存行（Cache Line，也称为 Cache Block）组成。每个缓存行包含以下字段：

有效位（Valid Bit）：标识该缓存行是否包含有效数据。缓存初始化时所有有效位都为 0。
标记（Tag）：用于标识该缓存行对应主存中的哪个地址块。
数据块（Data Block）：实际存储的数据，大小通常为 64 字节（一个缓存行）。
其他状态位：如脏位（Dirty Bit，用于写回策略）、LRU 状态位等。

当 CPU 需要读取某个内存地址的数据时，缓存控制器会执行以下步骤：

从地址中提取索引（Index）部分，定位到缓存中的特定组（Set）。

在该组的所有缓存行中，比较标记（Tag）部分是否匹配。

如果标记匹配且有效位为 1，则缓存命中，从缓存行中取出数据。

如果不匹配或有效位为 0，则缓存未命中，需要从下一级存储器加载数据。

缓存地址的划分

一个内存地址被划分为三个字段：

| Tag (标记) | Index (索引) | Block Offset (块偏移) |

块偏移（Block Offset）：用于在缓存行内定位具体的字节。如果缓存行大小为 64 字节，则需要 6 位块偏移（2^6 = 64）。
索引（Index）：用于在缓存中定位特定的组。如果缓存有 S 个组，则需要 log₂(S) 位索引。
标记（Tag）：剩余的高位部分，用于区分映射到同一组的不同主存块。

三种缓存映射方式

根据每个内存块可以放置在缓存中的位置，缓存分为三种组织方式：

直接映射缓存（Direct-Mapped Cache）

在直接映射缓存中，每个内存块只能映射到缓存中的唯一一个位置（组）。映射规则为：组索引 = (内存地址 / 缓存行大小) % 组数。

直接映射缓存的优点是硬件实现简单——只需要一个比较器来判断命中与否，查找速度快。缺点是冲突不命中率高——如果程序频繁访问两个映射到同一组的内存块，它们会不断互相驱逐，导致每次访问都是未命中。

直接映射示例（4 组，每行 16 字节）：
地址 0x00 → 组 0
地址 0x10 → 组 1
地址 0x20 → 组 2
地址 0x30 → 组 3
地址 0x40 → 组 0  (与 0x00 冲突！)

全相联缓存（Fully Associative Cache）

在全相联缓存中，任何内存块可以放置在缓存中的任何位置。查找时需要同时比较所有缓存行的标记，因此需要与缓存行数相同的比较器。

全相联缓存的优点是冲突不命中率为零——只要缓存中有空闲位置，任何块都可以放入。缺点是硬件成本高（比较器数量与缓存行数成正比），查找速度慢，因此只适用于非常小的缓存（如 TLB）。

组相联缓存（Set-Associative Cache）

组相联缓存是直接映射和全相联的折中方案。缓存被分为 S 个组，每个组包含 E 个缓存行（称为 E 路组相联）。一个内存块首先通过索引映射到特定的组，然后可以在该组内的任意一行中放置。查找时需要在该组的所有 E 行中并行比较标记。

2路组相联示例（4 组，每组 2 行）：
地址 0x00 → 组 0 → 可放入第 0 行或第 1 行
地址 0x40 → 组 0 → 可放入第 0 行或第 1 行（不与 0x00 冲突！）

现代处理器的缓存几乎都是组相联的：

L1 数据缓存：通常 8 路组相联，大小 32-64KB。
L2 缓存：通常 4-16 路组相联，大小 256KB-1MB。
L3 缓存：通常 8-20 路组相联，大小 4-32MB。

缓存替换策略

当缓存未命中且目标组已满时，需要选择一个现有的缓存行进行替换（驱逐）。常见的替换策略包括：

随机替换（Random）：随机选择一个缓存行替换。实现简单，但性能不稳定。

先进先出（FIFO）：替换最早进入缓存的行。实现简单（使用队列），但不考虑访问频率。

最近最少使用（LRU, Least Recently Used）：替换最长时间未被访问的行。LRU 能较好地反映程序的局部性特征，但真正的 LRU 实现成本较高——需要维护一个访问顺序的链表或栈，对于 E 路组相联缓存，每次访问需要更新 E 个条目的状态。

近似 LRU：实际硬件中常用的折中方案。例如，为每个缓存行添加一个"年龄位"（Age Bit），每次访问时将年龄位设为"年轻"，替换时选择"最老"的行。这种方式比真正的 LRU 简单得多，但性能接近。

伪 LRU（Pseudo-LRU）：使用树形结构近似 LRU 行为，硬件开销远小于真正的 LRU，但性能差距很小。

缓存不命中的三种类型

缓存不命中可以分为三种类型：

强制性不命中（Compulsory Miss / Cold Miss）：数据首次被访问时必然发生的不命中，因为缓存中还没有该数据的副本。这种不命中无法通过增大缓存或改变替换策略来避免，只能通过预取（Prefetching）来减少其影响。

容量不命中（Capacity Miss）：缓存的总容量不足以容纳程序工作集（Working Set）导致的不命中。即使缓存可以是全相联的，只要工作集大于缓存容量，就会发生容量不命中。这种不命中只能通过增大缓存容量来解决。

冲突不命中（Conflict Miss）：由于缓存的组相联结构，多个活跃的内存块映射到同一组，导致它们不断互相驱逐。即使缓存的总容量足够，也会发生冲突不命中。这种不命中可以通过增加路数（如从 4 路改为 8 路）来减少。

四、缓存写入策略

缓存的读取过程相对简单——查找标记，命中则返回数据，未命中则从下一级加载。但缓存的写入要复杂得多，因为必须保证缓存和主存之间的一致性。

缓存命中时的写策略

写穿透（Write-Through）：数据同时写入缓存和下一级存储器（主存或下级缓存）。优点是主存始终保持最新数据，一致性简单。缺点是每次写操作都需要访问慢速的下一级存储器，写延迟高。通常会使用一个写缓冲区（Write Buffer）来暂存待写入主存的数据，避免 CPU 等待。

写回（Write-Back）：数据只写入缓存，不立即写入主存。被修改过的缓存行的脏位（Dirty Bit）被置为 1。只有当脏行被替换出去时，才会将数据写回主存。优点是写操作只需访问快速的缓存，写延迟低；多次写入同一位置时只需最终写回一次。缺点是主存中的数据可能不是最新的，一致性管理复杂；替换时需要额外的一次写操作。

现代处理器的 L2 及以上缓存通常使用写回策略。L1 缓存有些使用写穿透（简化与 L2 的一致性），有些使用写回（降低写延迟）。

缓存未命中时的写策略

写分配（Write-Allocate）：写未命中时，先将数据所在的块从主存加载到缓存中，然后再执行写操作。这样后续的写操作就可以命中缓存。写分配通常与写回策略配合使用。

非写分配（No-Write-Allocate / Write-Around）：写未命中时，直接将数据写入主存，不加载到缓存中。非写分配通常与写穿透策略配合使用。

典型组合

实际中最常见的两种组合是：

写穿透 + 非写分配：实现简单，适合 L1 数据缓存（与 L2 缓存之间的一致性容易管理）。

写回 + 写分配：性能更优，适合 L2 及以上缓存（减少了对主存的写操作次数）。

多处理器缓存一致性

在多核处理器中，每个核心都有自己的 L1 和 L2 缓存，多个核心可能同时缓存了同一内存地址的数据副本。当某个核心修改了其缓存中的数据时，其他核心缓存中的副本就变为无效。维护缓存一致性的协议（如 MESI 协议）是多处理器系统设计中的关键挑战。

MESI 协议为每个缓存行定义了四种状态：

Modified（已修改）：数据已被本核心修改，与主存不一致，且是唯一副本。
Exclusive（独占）：数据与主存一致，且是唯一副本。可以直接写入而无需通知其他核心。
Shared（共享）：数据与主存一致，可能存在其他核心的副本。写入前必须先使其他副本无效。
Invalid（无效）：缓存行无效，不能使用。

五、存储器山模型详解

存储器山（Memory Mountain）是由 CSAPP 教材作者 Bryant 和 O'Hallaron 教授提出的一个性能可视化模型，它通过系统地测量不同工作集大小和不同访问步长下的内存读取吞吐量，构建出一个三维曲面图，直观地展示了存储器层次结构的性能特征。

测试方法

存储器山的测试程序使用一个二维参数空间：

数组大小（Size）：从 1KB 到几百 MB，跨越各级缓存和主存的容量范围。
步长（Stride）：从 1 到几十个元素，测试不同空间局部性下的性能。

测试程序的核心是一个读取函数，它以指定的步长遍历指定大小的数组，并测量遍历的吞吐量（MB/s）：

void *test_data;
long test_size;

void test(int size, int stride) {
    test_data = malloc(size);
    test_size = size / sizeof(long);
    long sum = 0;
    for (int pass = 0; pass < NUM_PASSES; pass++) {
        for (long i = 0; i < test_size; i += stride) {
            sum += *((long *)(test_data + i * sizeof(long)));
        }
    }
    // 计算吞吐量 = (test_size / stride * NUM_PASSES * sizeof(long)) / elapsed_time
    free(test_data);
}

存储器山的解读

存储器山的三维图以工作集大小为 X 轴，步长为 Y 轴，读取吞吐量为 Z 轴。典型的存储器山呈现以下特征：

山顶（高吞吐量区域）：位于步长为 1、工作集较小的区域。此时数据完全在 L1 缓存中，且连续访问具有最好的空间局部性，吞吐量达到峰值（通常等于 L1 缓存的带宽，约 50-100 GB/s）。

山坡（吞吐量递减区域）：随着工作集增大，数据逐渐超出 L1、L2、L3 缓存的容量，每次超出都会导致吞吐量出现阶梯式下降。在 L1→L2、L2→L3、L3→主存的边界处，吞吐量下降最为显著。

山谷（低吞吐量区域）：位于步长大、工作集大的区域。大步长导致空间局部性极差，每次访问几乎都缓存未命中；大工作集导致数据在主存中，访问延迟高。两者叠加，吞吐量降至最低。

山脊线：在步长为 1 的方向上，随着工作集的增大，吞吐量沿着缓存边界形成明显的"悬崖"。这些悬崖的位置对应着各级缓存的容量。通过分析这些悬崖的位置，可以精确地测量出各级缓存的大小。

存储器山的实践意义

存储器山模型为程序员提供了以下实践指导：

缓存大小是性能的关键分界线：工作集能否放入缓存，对性能的影响可能是 10 倍甚至 100 倍。算法设计应尽量减小工作集，或将大数据分块处理（如分块矩阵乘法）。

空间局部性至关重要：即使工作集在缓存中，大步长的跳跃访问也会导致低吞吐量。顺序访问（步长为 1）的性能远优于随机访问。

多级缓存的影响：现代处理器通常有 3-4 级缓存，每一级都会在存储器山上形成一个"台阶"。程序的性能取决于其内存访问模式落在存储器山的哪个位置。

硬件预取的作用：现代处理器配备了硬件预取器，能够检测顺序访问模式并提前加载数据。这使得步长为 1 或较小步长的实际吞吐量可能接近理论峰值。但预取器对大步长或随机访问模式通常无效。

六、存储器层次结构的完整图景

一个完整的现代计算机系统的存储器层次结构从最快到最慢依次包括：

层级	存储设备	典型延迟	典型容量	管理方式
L0	寄存器	0 周期	~1KB	编译器
L1	L1 缓存（SRAM）	~4 周期	32-64 KB	硬件
L2	L2 缓存（SRAM）	~12 周期	256 KB-1 MB	硬件
L3	L3 缓存（SRAM）	~30-40 周期	4-32 MB	硬件
L4	主存（DRAM）	~200-300 周期	8-256 GB	硬件 + OS
L5	本地磁盘/SSD	~10-200 μs	256 GB-4 TB	OS
L6	远程存储/NFS	~1-100 ms	无限	OS + 网络

这个层次结构的核心设计原则是：越靠近 CPU 的存储层级，速度越快、容量越小、成本越高。每一级缓存都是对下一级存储器的"加速"——利用局部性原理，将频繁访问的数据副本保存在更快的存储器中。

层次结构的有效性依赖于一个关键假设：上层缓存的命中率必须足够高。如果 L1 缓存的命中率为 99%，那么只有 1% 的内存访问需要访问 L2；如果 L2 的命中率也为 99%，那么只有 0.01% 的访问需要访问 L3；以此类推。这种"乘法效应"使得即使各级存储器之间的速度差异巨大，整个系统的平均访问时间也可以接近最快存储器的水平。

反之，如果命中率不够高，性能会急剧恶化。例如，如果 L1 缓存的命中率只有 95%，那么 5% 的访问需要访问 L2（假设 L2 延迟是 L1 的 3 倍），平均访问时间将增加到 L1 的 1.15 倍。如果 L2 的命中率也只有 90%，那么平均访问时间将进一步增加。多级缓存的命中率必须逐级提高，才能保证整体性能。

七、编写缓存友好的代码

理解存储器层次结构的最终目的是编写出对缓存友好的代码。以下是几条重要的实践原则：

原则一：最大化空间局部性

使用连续存储的数据结构（数组优于链表）。
循环嵌套的顺序应与数据的存储顺序一致（C 语言中行优先）。
避免大步长的跳跃式访问。
将相关的数据组织在相邻的内存位置（如使用结构体而非多个平行数组）。

原则二：最小化工作集

使用合适的数据类型（如 int 而非 long long，如果值域允许）。
分块处理大数据集（如分块矩阵乘法，每次处理一个能放入缓存的子块）。
避免在循环中引用不必要的数据。

原则三：利用时间局部性

将频繁使用的变量放在寄存器或缓存中。
在代码中重用最近访问过的数据。
合理组织函数调用，避免频繁的上下文切换导致缓存污染。

原则四：理解缓存的容量和行为

了解目标机器的缓存参数（行大小、关联度、容量）。
注意缓存的"别名"问题——不同虚拟地址可能映射到同一物理地址，导致缓存效率降低。
注意缓存的"污染"问题——某些操作（如大数组的顺序扫描）可能将有用数据从缓存中驱逐。

// 缓存友好的分块矩阵乘法
void matmul_blocked(double *A, double *B, double *C, int n) {
    int BLOCK = 64;
    for (int ii = 0; ii < n; ii += BLOCK) {
        for (int jj = 0; jj < n; jj += BLOCK) {
            for (int kk = 0; kk < n; kk += BLOCK) {
                for (int i = ii; i < min(ii + BLOCK, n); i++) {
                    for (int j = jj; j < min(jj + BLOCK, n); j++) {
                        for (int k = kk; k < min(kk + BLOCK, n); k++) {
                            C[i * n + j] += A[i * n + k] * B[k * n + j];
                        }
                    }
                }
            }
        }
    }
}

分块矩阵乘法将大矩阵分成能放入缓存的小块，在每个块内完成所有计算后再处理下一个块。这样每个数据块在被加载到缓存后会被反复使用（时间局部性），同时块内的数据是连续存储的（空间局部性），显著提高了缓存命中率。

代码示例

示例一：验证缓存行大小对性能的影响

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARRAY_SIZE (1 << 20)

double benchmark(int stride) {
    int *arr = malloc(ARRAY_SIZE * sizeof(int));
    for (int i = 0; i < ARRAY_SIZE; i++) arr[i] = i;

    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);

    long sum = 0;
    int iterations = 100;
    for (int iter = 0; iter < iterations; iter++) {
        for (int i = 0; i < ARRAY_SIZE; i += stride) {
            sum += arr[i];
        }
    }

    clock_gettime(CLOCK_MONOTONIC, &end);
    double elapsed = (end.tv_sec - start.tv_sec) +
                     (end.tv_nsec - start.tv_nsec) / 1e9;

    free(arr);
    return elapsed;
}

int main() {
    printf("Stride\tTime(s)\n");
    for (int stride = 1; stride <= 64; stride *= 2) {
        double time = benchmark(stride);
        printf("%d\t%.4f\n", stride, time);
    }
    return 0;
}

当步长从 1 增加到 16（超过 64 字节缓存行 / 4 字节 int = 16）时，执行时间会显著增加，因为每次访问都需要加载新的缓存行。

示例二：行序 vs 列序遍历矩阵

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 2048
int matrix[N][N];

void init_matrix() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            matrix[i][j] = rand();
}

long sum_rows() {
    long sum = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            sum += matrix[i][j];
    return sum;
}

long sum_cols() {
    long sum = 0;
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++)
            sum += matrix[i][j];
    return sum;
}

int main() {
    init_matrix();
    struct timespec start, end;

    clock_gettime(CLOCK_MONOTONIC, &start);
    sum_rows();
    clock_gettime(CLOCK_MONOTONIC, &end);
    printf("Row-major: %.4f s\n",
           (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9);

    clock_gettime(CLOCK_MONOTONIC, &start);
    sum_cols();
    clock_gettime(CLOCK_MONOTONIC, &end);
    printf("Col-major: %.4f s\n",
           (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9);

    return 0;
}

在大多数系统上，sum_cols 的执行时间是 sum_rows 的 5-20 倍，原因就在于列序遍历破坏了空间局部性，导致大量的缓存未命中。

实验解读

实验：使用 cachegrind 分析缓存行为

实验目的：使用 Valgrind 的 cachegrind 工具观察不同代码模式的缓存命中/未命中情况。

实验步骤：

编写包含行序和列序遍历矩阵的程序。

使用 gcc -g -O0 编译（关闭优化以便更清晰地观察缓存行为）。

运行 valgrind --tool=cachegrind ./program。

使用 cg_annotate cachegrind.out.<pid> 查看详细报告。

预期结果：

对于行序遍历，cachegrind 会报告极高的 L1 数据缓存命中率（通常 > 99%），因为每次缓存行加载后的 16 次连续访问都命中 L1。

对于列序遍历，cachegrind 会报告极低的 L1 数据缓存命中率（通常 < 10%），因为每次访问都跳转到新的缓存行。

关键观察：

行序遍历的 L1 miss 数量约为 N * N / 16（每 16 个 int 一个缓存行），而列序遍历的 L1 miss 数量接近 N * N（几乎每次访问都是 miss）。
两者的 L1 命中数差异约为 16 倍，但实际执行时间差异往往更大（因为 L1 miss 后的 L2/L3 访问延迟远大于 L1）。

实验：绘制存储器山

实验目的：通过实际测量绘制存储器山，直观理解缓存层次的性能特征。