计算机系统基础-03：存储器层次结构

存储器层次结构

存储系统由多种设备组成。越靠近 CPU 的层次速度越快、容量越小、单位成本越高；越远离 CPU 的层次速度越慢、容量越大、单位成本越低。

典型层次：

1	寄存器 -> L1 Cache -> L2 Cache -> L3 Cache -> DRAM 主存 -> SSD/HDD 外存

不同存储技术的访问时间差异较大。
更快的技术通常单位成本更高、容量更小。
CPU 与主存之间的速度差距持续扩大。
程序通常具有局部性。

存储器层次结构的目标：用靠底层的大容量低成本存储提供容量，用靠顶层的小容量高速存储提供常见访问速度。

随机访问存储器

RAM 通常封装为芯片，基本存储单位是 cell，每个 cell 存储 1 bit。多个 RAM 芯片组成主存。

SRAM 与 DRAM

类型	存储方式	特点	典型用途
SRAM	每个 bit 用六晶体管电路保存	只要供电即可保持数据，对电噪声较稳定，速度快，成本高	Cache
DRAM	每个 bit 用电容和晶体管保存	需要每 10 ~ 100 ms 刷新一次，对干扰更敏感，密度高，成本低	主存

SRAM 和 DRAM 都是易失性存储器，断电后信息会丢失。

DRAM 组织

DRAM 常表示为 $d \times w$ 结构：共有 $d \cdot w$ bit，被组织成 $d$ 个 supercell，每个 supercell 有 $w$ bit。

读取某个 supercell 的过程：

RAS Row Access Strobe 选择目标行。
目标行被复制到 row buffer。
CAS Column Access Strobe 选择目标列。
目标 supercell 从 row buffer 复制到数据线，再传回 CPU。

非易失性存储器

非易失性存储器断电后仍保留数据，通用名称是 ROM（Read-Only Memory）。该名称并不完全准确，因为部分 ROM 可以被修改。

固件（Firmware）是存储在 ROM 中的程序。典型例子包括：

BIOS：启动时执行的基本输入输出系统。
显卡、磁盘控制器中的控制程序。
将 CPU 的 I/O 请求转换为设备操作的程序。

数据传输

CPU 和内存之间存在频繁的数据传输。总线（bus）是一组并行导线，用于传递地址、数据和控制信号。总线通常由多个设备共享。

读事务步骤：

CPU 将地址 A 放到内存总线上。
主存从总线读取地址 A，取出地址对应的字 x，并把 x 放到总线上。
CPU 从总线读取 x，并复制到寄存器，例如 %rax。

写事务步骤：

CPU 将地址 A 放到总线上，主存读取地址并等待数据。
CPU 将数据字 Y 放到总线上。
主存读取 Y，并写入地址 A。

磁盘

磁盘结构

磁盘驱动器通常包含：

arm/head：磁头臂和读写磁头。
actuator：驱动磁头移动的执行机构。
controller/electronics：磁盘内部控制逻辑。
spindle：主轴。
platters：盘片。
surfaces：每个盘片有两个表面。
tracks：每个表面由同心磁道组成。
sectors：每个磁道由扇区和间隙组成。
多个盘面中半径相同的磁道组成一个 cylinder。

磁盘容量

磁盘容量指最多能存储的 bit 数。厂商通常用十进制 GB 表示容量，其中 $1\text{ GB}=10^9$ byte。

容量由以下因素决定：

recording density：每英寸磁道可存储的 bit 数。
track density：每英寸半径方向可放置的磁道数。
areal density：recording density 与 track density 的乘积。

传统磁盘中每个磁道有相同数量的扇区。现代磁盘将磁道划分为多个 recording zone，同一区域内每个磁道扇区数相同，不同区域扇区数不同。

磁盘容量计算公式：

$\text{Capacity}=(\text{bytes/sector})\times(\text{avg sectors/track})\times(\text{tracks/surface})\times(\text{surfaces/platter})\times(\text{platters/disk})$

若给定磁盘参数：

$512 bytes/sector \quad 300 sectors/track (on average) \quad 20,000 tracks/surface \quad 2 surfaces/platter \quad 5 platters/disk$

计算出磁盘容量：

$512\times300\times20000\times2\times5=30{,}720{,}000{,}000\text{ bytes}=30.72\text{ GB}$

磁盘访问时间

访问目标扇区的平均时间可近似为：

$T_{access}=T_{avg\ seek}+T_{avg\ rotation}+T_{avg\ transfer}$

其中：

seek time：磁头移动到目标 cylinder 的时间，典型平均值约 9 ms。
rotational latency：等待目标扇区旋转到磁头下方的时间。
transfer time：读取目标扇区 bit 的时间。

平均旋转延迟（转一圈时间的一半，即平均等待时间）：

$T_{avg\ rotation}=\frac{1}{2}\times\frac{1}{RPM}\times60\ \text{sec}$

传输时间（扫一圈是一 Track，该项为扫完一个 Sector 的时间）：

$T_{avg\ transfer}=\frac{1}{\text{avg sectors/track}}\times\frac{1}{RPM}\times60\ \text{sec}$

示例：7200 RPM，平均 seek time 为 9 ms，平均每磁道 400 个扇区：

$T_{avg\ rotation}=\frac{1}{2}\times\frac{60}{7200}\times1000\approx4\text{ ms}$

$T_{avg\ transfer}=\frac{1}{400}\times\frac{60}{7200}\times1000\approx0.02\text{ ms}$

$T_{access}=9+4+0.02=13.02\text{ ms}$

磁盘访问时间主要由 seek time 和 rotational latency 决定。

读取扇区的第一个 bit 成本最高，后续 bit 的边际成本较低。

SRAM 访问约为 4 ns / 64-bit word。

DRAM 访问约为 60 ns / 64-bit word。

磁盘比 SRAM 慢约 40,000 倍，比 DRAM 慢约 2,500 倍。

现代磁盘向系统提供更简单的抽象：将可用扇区表示为连续逻辑块序列 $0,1,\dots,B-1$ 。

逻辑块到物理位置 (surface, track, sector) 的映射由磁盘控制器维护。格式化容量通常小于最大容量，因为控制器会为每个 zone 预留备用 cylinder 等空间。

I/O 与 DMA

Memory-mapped I/O：控制器和适配器内部也有处理器和寄存器。I/O port 是地址空间中的保留地址，设备寄存器可映射到这些地址。设备连接到总线后，会关联一个或多个 I/O port。CPU 通过这些 port 与设备通信。
DMA Direct Memory Access：指设备在没有 CPU 直接参与的情况下，自行执行读或写总线事务。该数据传输称为 DMA transfer。整个过程如下：
1. CPU 向磁盘控制器发出读请求。
2. 磁盘控制器读取目标扇区。
3. 控制器通过 DMA 将数据写入主存。
4. 传输完成后，设备触发中断通知 CPU。
中断：I/O 设备通过向处理器芯片上的引脚发送信号触发中断。触发中断的设备包括网络适配器、磁盘控制器、计时器等。
- 设备在系统总线上放置一个编号，用于标识中断来源。
- CPU 暂停当前执行内容。
- CPU 跳转到操作系统中对应的中断处理例程。

固态硬盘

SSD（Solid State Disk）基于 flash memory，可通过 USB、SATA 或 PCIe 等接口连接。SSD 中的 flash translation layer 扮演类似磁盘控制器的角色。

Flash memory 通常按 page 和 block 组织：

page 大小约 512 B 到 4 KB。
一个 block 包含 32 到 128 个 page。
数据以 page 为单位读写。
page 只能在所在 block 被擦除后写入。
block 经过约 100,000 次重复写入后可能磨损。

修改某个 page 时，常需要将同一 block 中其他 page 复制到新 block，再擦除旧 block。擦除 block 需要较长时间，约 1 ms。特点：

顺序访问快于随机访问。
随机写通常较慢。
Flash translation layer 可积累小写入，再进行 block 写入。

SSD 优点：无机械运动部件；访问更快；功耗更低；更抗震。
SSD 缺点：存在写入磨损；需要 wear leveling 逻辑分散写入；单位容量价格通常高于机械硬盘，但差距持续缩小。

局部性

局部性原则：程序倾向于访问最近访问过的地址，或最近访问地址附近的地址。其分为两类：

时间局部性：最近访问的对象在不久后可能再次访问。
空间局部性：地址相近的对象倾向于在相近时间被访问。

现代系统各层都利用局部性：

硬件用 cache 加速主存访问。
操作系统用主存缓存虚拟地址空间和磁盘文件。
应用程序可缓存最近访问的数据，例如浏览器缓存页面。

以向量求和为例：

int sumvec(int v[N])
{
    int i, sum = 0;
    for (i = 0; i < N; i++)
        /* v[i] 顺序访问，数组访问具有 stride-1 空间局部性。 */
        sum += v[i];
    /* sum 和 i 每轮都会访问，通常可保存在寄存器中。 */
    return sum;
}

局部性分析：

sum 和 i 每轮循环访问，具有时间局部性。
v[0], v[1], ..., v[N-1] 顺序访问，具有空间局部性。
该访问模式称为 stride-1 reference pattern。

stride-k reference pattern 指每隔 $k$ 个元素访问一次连续向量。 $k$ 越大，空间局部性越差。

推广到二维数组。二维数组按行优先存储，按行遍历具有 stride-1 访问模式：

int sumarrayrows(int a[M][N])
{
    int i, j, sum = 0;
    for (i = 0; i < M; i++)
        /* C 数组按行优先存储，内层 j 递增时访问连续地址。 */
        for (j = 0; j < N; j++)
            sum += a[i][j];
    return sum;
}

按列遍历在内层循环中跨行访问，stride 为 $N$ ：

int sumarraycols(int a[M][N])
{
    int i, j, sum = 0;
    for (j = 0; j < N; j++)
        /* 内层 i 递增时跨行访问，地址步长为一整行 N 个 int。 */
        for (i = 0; i < M; i++)
            sum += a[i][j];
    return sum;
}

当数组按行连续存储时，sumarrayrows 的空间局部性通常优于 sumarraycols。

Cache

在存储器层次结构中，对每一层 $k$ ，更快、更小的第 $k$ 层可作为更慢、更大的第 $k+1$ 层的 cache。其中：

较慢层被划分为固定大小的 block。
数据以 block 为单位在相邻层次之间复制。
较快层只缓存较慢层的一部分 block。

Hit 与 Miss

当程序需要 block b：

若 b 已在 cache 中，称为 hit。
若 b 不在 cache 中，称为 miss，需要从下一层取回。

miss 处理时需要决定：

placement policy：新 block 放到 cache 的哪个位置。
replacement policy：如果目标位置已满，替换哪个 block。

Cache Miss 类型：

类型	原因
Cold / compulsory miss	cache 初始为空，第一次访问某个 block 必然 miss
Capacity miss	活跃 block 集合大于 cache 容量
Conflict miss	cache 容量足够，但多个 block 映射到同一 cache 位置。比如若 cache 规定 block `i` 只能放到位置 `i mod 4`，连续访问 block `9, 13, 9, 13, ...` 会反复冲突，因为二者映射到同一位置。

Cache Memory

Cache memory 是小容量、高速、基于 SRAM 的存储器，由硬件自动管理。历史上存储层次从早期的寄存器、主存、磁盘三层，逐步扩展为现代处理器中的寄存器、L1、L2、L3、DRAM、外存多层结构。

CPU 访问内存时，通常先查 L1，再查 L2、L3，最后访问主存。

执行 movq 时：

1	movq A, %rax # 用地址 A 访问内存；硬件会先查询 cache，再决定是否访问下一层存储

执行时会用地址 A 查询 cache：

若命中，直接从 cache 取值。
若不命中，触发 miss handling，从下一层取回数据。

Cache 组织

基本参数与组成

参数	含义
$S=2^s$	set 数量
$E$	每个 set 中的 line 数
$B=2^b$	block 大小，单位 byte
$m=\log_2(M)$	物理地址位数

参数	含义
$M=2^m$	可寻址内存大小
$s=\log_2(S)$	set index bit 数
$b=\log_2(B)$	block offset bit 数
$t=m-(s+b)$	tag bit 数
$C=B\times E\times S$	cache 数据容量，不含 valid bit 和 tag bit 等额外开销

物理地址划分为三个部分：

1	\| tag: t bits \| set index: s bits \| block offset: b bits \|

名称	含义
Block	在 cache 与下一级存储之间传输的固定大小数据包
Line	cache 中保存 block 的容器，包含 block、valid bit、tag bit 等信息
Set	一个或多个 line 的集合

直接映射 Cache

直接映射 cache 是最简单的 cache，每个 set 只有一个 line，即 $E=1$ 。

访问直接映射 cache 有三步：

Set selection：用 set index bit 选择 set。
Line matching：检查 valid bit 是否为 1，并比较 line 中 tag 与地址 tag 是否相同。
Word extraction：用 block offset 选择目标 byte 或 word。

命中条件：

1	valid bit = 1 且 cache line tag = address tag

示例：16 lines、4-byte line size、直接映射 cache。地址 0x354 的分解为：
1
2
3
offset = 0x0
index  = 0x05
tag    = 0x0D
若 index 5 对应 line 的 valid bit 为 1 且 tag 为 0x0D，则命中，并由 offset 取出目标 byte。

直接映射 cache miss 后：

根据 set index 找到唯一 cache line。
若该 line 有效，则驱逐旧 line。
将地址的低 $b$ 位清零，得到目标 block 的起始地址。
从下一层存储读取整个 block。
将 block 写入 cache line，并更新 valid bit 和 tag。
从新 line 中取出目标数据。

多次访问 miss/hit 示例：

$M=16$ byte addresses。

$B=2$ bytes/block。

$S=4$ sets。

$E=1$ line/set。

地址序列：0 [0000], 1 [0001], 13 [1101], 8 [1000], 0 [0000]。

访问结果：
1
2
3
4
5
0   -> miss
1   -> hit
13  -> miss
8   -> miss
0   -> miss
最后一次访问 0 miss 是因为 8 和 0 映射到同一 set，前者替换了后者。这种反复替换称为 thrashing。

冲突 miss 示例：
1
2
3
4
5
6
7
8
9
float dotprod(float x[8], float y[8])
{
    float sum = 0.0;
    int i;
    for (i = 0; i < 8; i++)
        /* 若 x 与 y 在直接映射 cache 中冲突，每轮可能反复替换 cache line。 */
        sum += x[i] * y[i];
    return sum;
}
假设：

x 从地址 0 开始，占 32 bytes。

y 紧接在 x 后，从地址 32 开始。

block 大小为 16 bytes，可容纳 4 个 float。

cache 有 2 个 set，总容量 32 bytes。

读取 x[0] 会加载 x[0]~x[3]。随后读取 y[0] 会把同一 set 中的 line 替换为 y[0]~y[3]。继续访问会造成反复冲突。

解决方法之一是 padding，例如将 x[8] 声明为 x[12]，改变 y 的起始位置，避免二者持续映射到同一 set。

为什么使用中间位作为 index：
若使用高位作为 index，由于地址高位一般几乎是保持不变的，连续内存 line 可能一直映射到同一个 cache entry 或 cache set，访问时会持续发生 conflict miss，空间局部性利用较差。
使用中间位作为 index 时，连续内存 line 会映射到不同 cache line，有利于同时缓存连续地址区域。

组相联与全相联 Cache

组相联 Cache

组相联 cache 中每个 set 有多个 line，即 $E>1$ 。

访问流程：

set selection 与直接映射相同。
在选中 set 中比较每个有效 line 的 tag。
若任一 line tag 匹配，则命中。
用 block offset 取出目标数据。

组相联可降低冲突 miss，但需要在同一 set 中并行或顺序比较多个 tag。

示例：16 lines、4-byte line size、2-way set associative cache。地址 0x354 可被分解为：
1
2
3
offset = 0x0
index  = 0x05
>tag    = 0x1A
若 set 5 中所有有效 line 的 tag 都不是 0x1A，则 miss。

当目标 set 中所有 line 都有效，miss 时需要选择 victim line。

常见替换策略：

策略	含义	代价
LFU	替换过去一段时间内访问次数最少的 line	需要计数和额外硬件
LRU	替换最久未被访问的 line	需要维护最近使用信息

这些策略可减少 miss，但会增加硬件复杂度和访问时间。

全相联 Cache

全相联 cache 只有一个 set，所有 line 都属于该 set。地址中没有 set index bit。

访问时必须比较所有有效 line 的 tag。全相联可以减少冲突 miss，但 tag 比较成本较高，因此通常用于较小结构，例如 TLB。

写操作策略

Write Hit

写命中时有两种策略：

策略	行为	特点
Write-through	更新 cache 后立即写回下一层存储	实现简单，但写流量较高
Write-back	只更新 cache，等 line 被驱逐时再写回下一层	写流量较低，但需要 dirty bit

Write-back 需要为每个 line 维护 dirty bit，表示该 line 是否被修改过。

Write Miss

写不命中时有两种策略：

策略	行为
Write-allocate	先把对应 block 加载到 cache，再更新 cache
No-write-allocate	不加载到 cache，直接写下一层存储

常见组合：

Write-through + no-write-allocate。
Write-back + write-allocate，现代实现常采用该组合。

Cache 性能指标

Miss Rate 与 Hit Rate

miss rate 是未在 cache 中找到的访问比例：

$\text{miss rate}=\frac{\text{misses}}{\text{references}}$

hit rate 是命中比例：

$\text{hit rate}=1-\text{miss rate}$

典型值：

L1 miss rate 常见约 3% ~ 10%。
L2 miss rate 可低于 1%，取决于容量和程序行为。

Hit Time 与 Miss Penalty

指标	含义	典型值
Hit time	判断是否命中并把 cache line 交给处理器的时间	Core i7 中 L1 约 4 cycles，L2 约 11 cycles
Miss penalty	miss 后从下一层取回数据的额外时间	主存访问常见 50 ~ 200 cycles

平均访问时间可表示为：

$T_{avg}=T_{hit}+\text{miss rate}\times T_{miss\ penalty}$

若 hit time 为 2 cycles，miss penalty 为 200 cycles：

1 2	hit rate = 99%: 20.99 + 2000.01 = 4 cycles hit rate = 97%: 20.97 + 2000.03 = 8 cycles

hit rate 只下降 2%，平均访问时间可翻倍。因此分析 cache 性能时通常更关注 miss rate。

Cache 参数

参数	影响
Cache size	容量越大，miss rate 通常越低，但 hit time 可能增加
Block size	较大 block 利用空间局部性，但可能降低时间局部性并增加 miss penalty
Associativity	较高相联度减少冲突 miss，但增加 tag 比较成本和访问时间
Write strategy	影响写流量、实现复杂度和 read miss 行为

多级 cache 通常使用相同或相近的 block size，例如 64 bytes。

编写 Cache 友好代码

基本原则：

局部性越好，miss rate 越低。
miss rate 越低，程序通常越快。
优先优化热点函数和内层循环。
尽量减少内层循环中的 cache miss。

局部变量的重复引用通常具有良好时间局部性。编译器可将局部变量保存在寄存器中，减少内存访问。
stride-1 访问通常具有良好空间局部性，因为 cache 以连续 block 为单位加载数据。空间局部性在多维数组程序中尤其重要。

矩阵遍历

int sumarrayrows(int a[M][N])
{
    int i, j, sum = 0;
    for (i = 0; i < M; i++)
        /* 每行连续扫描，cache block 中后续元素可被重复利用。 */
        for (j = 0; j < N; j++)
            sum += a[i][j];
    return sum;
}

若 M=4, N=8 且 cache block 可容纳 4 个 int，则每行大致每 4 个元素产生一次 miss，其余为 hit。

按列遍历示例：

int sumarraycols(int a[M][N])
{
    int i, j, sum = 0;
    for (j = 0; j < N; j++)
        /* C 的二维数组按行存储，内层 i 递增会跨行访问。 */
        for (i = 0; i < M; i++)
            sum += a[i][j];
    return sum;
}

按列遍历在 C 的行优先存储中步长较大，可能导致每次访问都 miss。

矩阵乘法

矩阵乘法有 $O(n^3)$ 次加法和乘法。每个矩阵元素可能被重复读取多次，循环顺序会影响局部性。

假设：

每个矩阵是 $n\times n$ 的 double 数组。
double 大小为 8 bytes。
cache block 大小 $B=32$ bytes，可容纳 4 个 double。
$n$ 足够大，使单行矩阵不能全部放入 cache。
编译器将局部变量保存在寄存器中。
iter 指最内层的一次迭代。

`ijk` 顺序

/* ijk */
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        /* sum 只对应 c[i][j]，通常保存在寄存器中。 */
        double sum = 0.0;
        for (k = 0; k < n; k++)
            /* a[i][k] 顺序访问；b[k][j] 按列访问，空间局部性差。 */
            sum += a[i][k] * b[k][j];
        c[i][j] = sum;
    }
}

内层循环：

a[i][k] 按行访问，stride-1，约 0.25 misses/iter。
b[k][j] 按列访问，stride-n，约 1.0 misses/iter。
c[i][j] 固定，sum 在寄存器中，约 0.0 misses/iter。

总计约 1.25 misses/iter。

`jik` 顺序

/* jik */
for (j = 0; j < n; j++) {
    for (i = 0; i < n; i++) {
        double sum = 0.0;
        for (k = 0; k < n; k++)
            /* 与 ijk 一样，内层 k 使 a 按行访问、b 按列访问。 */
            sum += a[i][k] * b[k][j];
        c[i][j] = sum;
    }
}

内层访问模式与 ijk 相同，总计约 1.25 misses/iter。

`kij` 顺序

/* kij */
for (k = 0; k < n; k++) {
    for (i = 0; i < n; i++) {
        /* a[i][k] 在内层 j 循环中不变，先放入局部变量。 */
        double r = a[i][k];
        for (j = 0; j < n; j++)
            /* b[k][j] 与 c[i][j] 都按行连续访问。 */
            c[i][j] += r * b[k][j];
    }
}

内层循环：

a[i][k] 固定在局部变量 r 中，约 0.0 misses/iter。
b[k][j] 按行访问，约 0.25 misses/iter。
c[i][j] 按行访问，读写同一行，约 0.25 misses/iter。

总计约 0.5 misses/iter。

`ikj` 顺序

/* ikj */
for (i = 0; i < n; i++) {
    for (k = 0; k < n; k++) {
        /* 固定 a[i][k]，让内层循环集中顺序访问 b 的一行和 c 的一行。 */
        double r = a[i][k];
        for (j = 0; j < n; j++)
            c[i][j] += r * b[k][j];
    }
}

访问模式与 kij 类似，总计约 0.5 misses/iter。

`jki` 与 `kji` 顺序

/* jki */
for (j = 0; j < n; j++) {
    for (k = 0; k < n; k++) {
        /* b[k][j] 在内层 i 循环中不变，但 a 和 c 都会按列访问。 */
        double r = b[k][j];
        for (i = 0; i < n; i++)
            c[i][j] += a[i][k] * r;
    }
}

/* kji */
for (k = 0; k < n; k++) {
    for (j = 0; j < n; j++) {
        /* 固定 b[k][j]，但内层 i 仍导致 a[i][k] 和 c[i][j] 跨行访问。 */
        double r = b[k][j];
        for (i = 0; i < n; i++)
            c[i][j] += a[i][k] * r;
    }
}

内层循环中 a[i][k] 和 c[i][j] 都按列访问，miss/iter 较高：

a：约 1.0 misses/iter。
b：固定在局部变量中，约 0.0 misses/iter。
c：约 1.0 misses/iter。

总计约 2.0 misses/iter。

miss rate 比较

顺序	A misses/iter	B misses/iter	C misses/iter	总 misses/iter
`ijk`	0.25	1.00	0.00	1.25
`jik`	0.25	1.00	0.00	1.25
`kij`	0.00	0.25	0.25	0.50
`ikj`	0.00	0.25	0.25	0.50
`jki`	1.00	0.00	1.00	2.00
`kji`	1.00	0.00	1.00	2.00

同一矩阵乘法应用，不同循环顺序可产生接近 40 倍性能差异。

具有相同内存引用数和 miss/iter 的版本性能接近。

在该例中，miss rate 比总内存访问次数更能预测性能。

kij 和 ikj 访问模式较好，性能较稳定。

预取硬件可识别 stride-1 访问，并在紧密内层循环中跟上访问速度。

存储器山

Memory mountain 用于测量内存系统在不同工作集大小和访问步长下的读吞吐。

读吞吐（read bandwidth）指程序从内存系统读取数据的速率。

Memory mountain 是一个二维函数：

1	read throughput = f(working set size, stride)

它用于刻画一台机器内存系统在不同时间局部性和空间局部性条件下的能力。

山顶：工作集小、stride 小，数据容易命中 cache，读得快；
山坡：stride 变大，空间局部性变差，吞吐下降；
山脚：工作集很大，数据放不进 cache，只能频繁访问主存，读得慢。

主程序结构

#define MINBYTES (1 << 14)   /* 16 KB */
#define MAXBYTES (1 << 27)   /* 128 MB */
#define MAXSTRIDE 12         /* 测试的最大访问步长 */
#define MAXELEMS (MAXBYTES / sizeof(long))  /* 最大工作集对应的 long 元素个数 */

/* 全局数组作为被测工作集，避免栈空间限制。 */
long data[MAXELEMS];

主程序遍历不同工作集大小和 stride：

for (size = MAXBYTES; size >= MINBYTES; size >>= 1) {
    /* 固定工作集大小，依次测试不同 stride。 */
    for (stride = 1; stride <= MAXSTRIDE; stride++)
        printf("%.1f\t", run(size, stride, Mhz));
    printf("\n");
}

测试函数

double run(int size, int stride, double Mhz)
{
    double cycles;
    /* 将字节数转换为 long 元素个数。 */
    int elems = size / sizeof(long);

    test(elems, stride);                    /* warm up cache */
    /* fcyc2 测量 test(elems, stride) 消耗的 CPU 周期数。 */
    cycles = fcyc2(test, elems, stride, 0);
    /* 每次只访问 size/stride 个元素，除以时间得到读吞吐。 */
    return (size / stride) / (cycles / Mhz);
}

test 函数按指定 stride 访问数组，并使用多个累积变量减少循环相关开销：

int test(int elems, int stride)
{
    long i;
    /* 预先计算 2、3、4 倍 stride，减少循环内乘法。 */
    long sx2 = stride * 2;
    long sx3 = stride * 3;
    long sx4 = stride * 4;
    /* 多累积变量减少加法依赖链对循环吞吐的影响。 */
    long acc0 = 0, acc1 = 0, acc2 = 0, acc3 = 0;
    long length = elems;
    /* 主循环每轮按 stride 访问 4 个元素，limit 防止越界。 */
    long limit = length - sx4;

    for (i = 0; i < limit; i += sx4) {
        /* 访问间隔由 stride 决定，用于观察空间局部性对吞吐的影响。 */
        acc0 += data[i];
        acc1 += data[i + stride];
        acc2 += data[i + sx2];
        acc3 += data[i + sx3];
    }
    for (; i < length; i += stride)
        /* 处理主循环之后的剩余元素。 */
        acc0 += data[i];

    return ((acc0 + acc1) + (acc2 + acc3));
}

实验变量：

working set：从 16 KB 到 128 MB。
stride：从 1 到 16 左右。

主要观察：

时间局部性 ridge：固定 stride（如 stride=8）观察不同工作集大小的吞吐，可反映 L1/L2/L3/主存层次。
空间局部性 slope：固定 working set（如 4 MB）观察不同 stride 的吞吐，可显示 cache block size 对访问效率的影响。
stride 为 1 时可能出现较平坦的高吞吐 ridge，即使工作集超过 L1/L2 容量，硬件预取仍能保持较高读吞吐。