1
内存地址空间：
2
┌──────────┬──────────┬──────────┬──────────┐
3
│ 行 0     │ 行 1     │ 行 2     │ 行 3     │
4
│ 0-63     │ 64-127   │ 128-191  │ 192-255  │
5
│ 字节     │ 字节     │ 字节     │ 字节     │
6
└──────────┴──────────┴──────────┴──────────┘
7
每次加载/传输一整行（64 字节）

1
struct Data {
2
    int a;    // 偏移 0
3
    int b;    // 偏移 4
4
    int c;    // 偏移 8
5
    int d;    // 偏移 12
6
    // ... 共 16 字节
7
};
8

9
struct Data arr[4];
10
// arr[0]: 地址 0-15    → 缓存行 0 (0-63)
11
// arr[1]: 地址 16-31   → 缓存行 0 (0-63)
12
// arr[2]: 地址 32-47   → 缓存行 0 (0-63)
13
// arr[3]: 地址 48-63   → 缓存行 0 (0-63)
14
// 4 个结构体共享 1 个缓存行！访问任意字段都会加载整行

1
地址分解：[Tag][Index][Offset]
2
                    ↓
3
映射到缓存中的第 Index 行
4

5
示例：缓存 64 行，缓存行 64 字节
6
地址 0x0000 → Index 0
7
地址 0x1000 → Index 0  ← 冲突！
8
地址 0x0040 → Index 1

1
4 路组相联缓存：
2
┌─────────────────────────────────────┐
3
│ 组 0: │ Way 0 │ Way 1 │ Way 2 │ Way 3 │
4
│ 组 1: │ Way 0 │ Way 1 │ Way 2 │ Way 3 │
5
│ 组 2: │ Way 0 │ Way 1 │ Way 2 │ Way 3 │
6
│ ...   │       │       │       │       │
7
└─────────────────────────────────────┘
8
地址映射到固定组，组内 4 路任选

1
// 缓存抖动示例
2
#define STRIDE 4096  // = 64 行 × 64 字节/行
3
int *arr = malloc(STRIDE * 8 * sizeof(int));  // 8 个元素间隔 4096 字节
4

5
// 如果 L1 是 8-way 组相联，这 8 个元素映射到同一组
6
// 交替访问会不断驱逐
7
for (int i = 0; i < 8; i++) {
8
    arr[i * STRIDE / 4]++;  // 每次访问驱逐前一个
9
}

1
8 路 PLRU 树（3 bit 即可管理 8 路）：
2

3
          bit0
4
         /    \
5
      bit1    bit2
6
     /  \     /  \
7
    W0  W1   W2  W3    ← 4 个 Way
8
   /\  /\   /\  /\
9
  W4 W5 W6 W7          ← 另外 4 个 Way（简化展示）
10

11
bit0=0 → 左半边优先驱逐
12
bit0=1 → 右半边优先驱逐
13
每次访问某一路时，沿途 bit 指向另一侧

1
// 普通拷贝：污染 L1/L2 缓存
2
void copy_normal(float *dst, float *src, int n) {
3
    for (int i = 0; i < n; i++) {
4
        dst[i] = src[i];  // 数据进入 L1/L2，驱逐热点
5
    }
6
}
7

8
// 非临时存储：绕过缓存
9
void copy_nontemporal(float *dst, float *src, int n) {
10
    int i = 0;
11
    for (; i + 16 <= n; i += 16) {
12
        __m512 data = _mm512_load_ps(src + i);      // 加载（不可避免）
13
        _mm512_stream_ps(dst + i, data);             // 非临时存储！绕过缓存
14
    }
15
    for (; i < n; i++) dst[i] = src[i];
16
    _mm_sfence();  // 确保所有流式存储完成
17
}
18
// 非临时存储直接写内存，不加载到缓存
19
// 热点数据留在缓存中，不受拷贝影响

1
// locality=3: 预取到 L1（高局部性）
2
__builtin_prefetch(&arr[i + 8], 0, 3);
3

4
// locality=1: 预取到 L2（中局部性）
5
__builtin_prefetch(&arr[i + 16], 0, 1);
6

7
// locality=0: 预取到 L2/L3（低局部性，可被快速驱逐）
8
__builtin_prefetch(&arr[i + 32], 0, 0);

1
// 不好：跳跃访问
2
for (int i = 0; i < N; i += 16) {
3
    sum += arr[i];  // 每次跳 64 字节，缓存行利用率 1/16
4
}
5

6
// 好：顺序访问
7
for (int i = 0; i < N; i++) {
8
    sum += arr[i];  // 连续访问，缓存行利用率 100%
9
}

1
// 不好：大结构体数组
2
struct BigStruct {
3
    int key;           // 4 字节
4
    char data[1020];   // 1020 字节
5
};  // 总大小 1024 字节
6

7
// 遍历 key 时，每个缓存行只有 1 个 key
8
// 缓存行利用率 = 4/64 = 6.25%
9

10
// 好：分离热/冷数据
11
struct HotData {
12
    int key;  // 4 字节
13
};  // 16 个 key/缓存行
14

15
struct ColdData {
16
    char data[1020];
17
};
18

19
// 先遍历 HotData 数组（缓存行利用率 100%）
20
// 只对需要的 key 访问 ColdData

1
// 不好：2 的幂步长
2
#define SIZE 1024  // 2 的幂
3
int matrix[SIZE][SIZE];
4
for (int i = 0; i < SIZE; i++) {
5
    for (int j = 0; j < SIZE; j++) {
6
        sum += matrix[j][i];  // 列优先访问
7
    }
8
}
9
// 列优先访问 + 2 的幂行宽 = 同一组反复驱逐
10

11
// 好：填充避免 2 的幂
12
#define SIZE 1024
13
#define PADDED_SIZE 1025  // 不是 2 的幂
14
int matrix[PADDED_SIZE][SIZE];
15
// 或者改为行优先访问
16
for (int i = 0; i < SIZE; i++) {
17
    for (int j = 0; j < SIZE; j++) {
18
        sum += matrix[i][j];  // 行优先访问
19
    }
20
}

1
// 朴素版本：O(N³) 访问，缓存未命中率高
2
void matmul_naive(double *C, double *A, double *B, int N) {
3
    for (int i = 0; i < N; i++)
4
        for (int j = 0; j < N; j++)
5
            for (int k = 0; k < N; k++)
6
                C[i*N+j] += A[i*N+k] * B[k*N+j];
7
    // B 的访问模式是列优先 → 缓存不友好
8
}
9

10
// 分块版本：利用缓存局部性
11
#define BLOCK 64  // 适配 L1 缓存大小
12
void matmul_blocked(double *C, double *A, double *B, int N) {
13
    for (int ii = 0; ii < N; ii += BLOCK)
14
        for (int jj = 0; jj < N; jj += BLOCK)
15
            for (int kk = 0; kk < N; kk += BLOCK)
16
                for (int i = ii; i < ii + BLOCK && i < N; i++)
17
                    for (int j = jj; j < jj + BLOCK && j < N; j++)
18
                        for (int k = kk; k < kk + BLOCK && k < N; k++)
19
                            C[i*N+j] += A[i*N+k] * B[k*N+j];
20
    // 每个工作块适配 L1 缓存，命中率大幅提升
21
}

1
# L1 数据缓存
2
perf stat -e L1-dcache-loads,L1-dcache-load-misses ./your_program
3

4
# L3 缓存（最后一级缓存）
5
perf stat -e LLC-loads,LLC-load-misses ./your_program
6

7
# 典型输出：
8
#   1,234,567,890  L1-dcache-loads
9
#      12,345,678  L1-dcache-load-misses  # 1.00% 未命中率
10
#       1,234,567  LLC-loads
11
#         123,456  LLC-load-misses         # 10.0% 未命中率

1
假设：
2
- L1 命中：3 周期
3
- L2 命中：12 周期
4
- L3 命中：36 周期
5
- DRAM：200 周期
6
- L1 未命中率：5%
7
- L2 未命中率（在 L1 未命中中）：20%
8
- L3 未命中率（在 L2 未命中中）：30%
9

10
平均访问时间（AMAT）= 3 + 0.05 × (12 + 0.20 × (36 + 0.30 × 200))
11
= 3 + 0.05 × (12 + 0.20 × 96)
12
= 3 + 0.05 × 31.2
13
= 3 + 1.56
14
= 4.56 周期

1
// GCC 内建预取指令
2
for (int i = 0; i < N; i++) {
3
    __builtin_prefetch(&arr[i + 16], 0, 1);  // 预取 16 个元素后的数据
4
    sum += arr[i];
5
}

1
#include <stdio.h>
2
#include <time.h>
3

4
#define SIZE (64 * 1024 * 1024)
5

6
int main() {
7
    int *arr = calloc(SIZE, sizeof(int));
8

9
    printf("步长  每元素延迟(ns)\n");
10
    for (int stride = 1; stride <= 128; stride *= 2) {
11
        clock_t start = clock();
12
        long long sum = 0;
13
        for (int i = 0; i < SIZE; i += stride) {
14
            sum += arr[i];
15
        }
16
        clock_t end = clock();
17
        double ns = (double)(end - start) / CLOCKS_PER_SEC * 1e9 / (SIZE / stride);
18
        printf("%4d   %.1f\n", stride, ns);
19
    }
20
    free(arr);
21
    return 0;
22
}
23
// 当步长从 1→16 时延迟急剧增加（16 个 int = 64 字节 = 1 个缓存行）
24
// 步长 > 16 后延迟趋于平稳

1
#include <stdio.h>
2
#include <time.h>
3
#include <stdlib.h>
4

5
int main() {
6
    printf("工作集(KB)  每次访问延迟(ns)\n");
7
    for (int size_kb = 4; size_kb <= 16384; size_kb *= 2) {
8
        int size = size_kb * 1024 / sizeof(int);
9
        int *arr = malloc(size * sizeof(int));
10
        for (int i = 0; i < size; i++) arr[i] = (i + 16) % size;
11

12
        clock_t start = clock();
13
        int idx = 0;
14
        for (int i = 0; i < 10000000; i++) idx = arr[idx];
15
        clock_t end = clock();
16

17
        double ns = (double)(end - start) / CLOCKS_PER_SEC * 1e9 / 10000000;
18
        printf("%8d     %.1f\n", size_kb, ns);
19
        free(arr);
20
    }
21
    return 0;
22
}
23
// 延迟在 32KB(L1)、256KB(L2)、几MB(L3) 处阶梯式增加

1
#include <stdio.h>
2
#include <time.h>
3
#include <stdlib.h>
4

5
#define N 2048
6

7
int main() {
8
    int (*matrix)[N] = malloc(N * N * sizeof(int));
9
    for (int i = 0; i < N; i++)
10
        for (int j = 0; j < N; j++)
11
            matrix[i][j] = i + j;
12

13
    // 行优先遍历
14
    clock_t start = clock();
15
    long long sum = 0;
16
    for (int i = 0; i < N; i++)
17
        for (int j = 0; j < N; j++)
18
            sum += matrix[i][j];
19
    clock_t end = clock();
20
    printf("行优先: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
21

22
    // 列优先遍历
23
    start = clock();
24
    sum = 0;
25
    for (int j = 0; j < N; j++)
26
        for (int i = 0; i < N; i++)
27
            sum += matrix[i][j];
28
    end = clock();
29
    printf("列优先: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
30

31
    free(matrix);
32
    return 0;
33
}
34
// 行优先通常快 3-10 倍（利用了缓存行预取）