局部性原理

局部性原理是存储器层次结构的理论基础。程序对存储器的访问不是随机的，而是呈现聚集性。

时间局部性（Temporal Locality）

• 刚被访问的数据很可能在近期再次被访问
• 原因：循环、重复调用的函数 / 变量

空间局部性（Spatial Locality）

• 刚被访问的数据附近的数据很可能在近期被访问
• 原因：顺序执行的指令、数组遍历

数组求和（空间局部性强）

for (i = 0; i < N; i++) sum += A[i];  // 顺序访问，空间局部性好
+ sum 体现时间局部性（每轮都访问）

矩阵乘法（两种局部性）

C[i][j] += A[i][k] * B[k][j];
A 按行访问 → 空间局部性好
B 按列访问 → 空间局部性差（跳跃）

链表遍历（局部性差）

while (p) { process(p->data); p = p->next; }
// 节点在内存中不连续 → 空间局部性差

层次结构：寄存器 → L1 → L2 → L3 → 主存 → 磁盘。局部性如何支撑它：

• 时间局部性 → Cache 保留最近使用的数据
• 空间局部性 → Cache 按块（Cache Line）加载数据

循环交换（按行而非按列访问）

// 好：按行访问（空间局部性好）
for (i) for (j) A[i][j] = 0;
// 差：按列访问（空间局部性差）
for (j) for (i) A[i][j] = 0;

分块（Tiling）

for (ii = 0; ii < N; ii += B)
  for (jj = 0; jj < N; jj += B)
    for (i = ii; ...) for (j = jj; ...) 处理 A[i][j];