考研笔记

程序访问的局部性原理

局部性是整个存储层次结构赖以成立的唯一前提（见 3.1.3）。它不是一条硬件设计原则，而是一条对程序行为的经验观察：程序在一小段时间里访问的地址，总是集中在一小片区域内。

正因为它是关于程序的，所以它可以被程序员改变。 这是本节最有价值的一点——同一台机器、同一个 Cache，改一下循环的嵌套顺序，命中率能差一个数量级，2014 年的统考真题考的就是这件事。

机制

两种局部性

时间局部性：刚被访问过的地址，很可能马上又被访问。

  • 来源：循环（循环体的指令、循环变量、累加器变量）
  • 硬件对策：把访问过的内容留在 Cache 里

空间局部性：刚被访问过的地址，它附近的地址很可能马上被访问。

  • 来源：指令的顺序存放与顺序执行、数组元素的连续存放
  • 硬件对策：一次装入一整块（Cache 行），而不是一个字

两种局部性各自对应 Cache 的一个设计决策：时间局部性决定”要不要留”，空间局部性决定”一次装多大”。块大小的选择就是在空间局部性上下注，见 3.5.2。

指令与数据分别看

指令流的局部性几乎总是很好：顺序执行给出空间局部性，循环给出时间局部性。

数据流的局部性差别巨大，取决于访问模式：

访问模式空间局部性例子
顺序遍历数组好for(i) a[i]
跨步长遍历随步长增大而变差for(i) a[i*N]
随机访问差哈希表、链表追指针

疑问点：循环体的时间局部性好，是因为"没有跳转"

这个判断把两种局部性的来源接反了。

空间局部性来自”没有跳转”——指令在主存中顺序存放，顺序执行时下一条指令就在旁边，所以取一个块能覆盖后面好几条指令。 时间局部性恰恰来自”有跳转”——循环末尾那条回边把 PC 拉回循环开头，同一段指令被重复执行了 次。若真的没有跳转、程序一路直线执行下去，每条指令只执行一次，时间局部性反而为零。

一句话概括：顺序执行给空间局部性，循环回跳给时间局部性。 循环体两者兼得，正是因为它既是顺序的、又是重复的。

这道 2014 年真题的设问方式值得单独记住。 题目给的两个程序只在循环嵌套顺序上不同（一个按行遍历二维数组、一个按列遍历），因此： 指令部分完全相同——都是同样的二重循环、同样的指令条数，指令 Cache 的命中率一样； 数据部分差别极大——按行遍历顺着数组在内存中的存放顺序走，空间局部性好；按列遍历每次跨过一整行，每访问一个元素就换一个 Cache 块，空间局部性极差。 所以这道题的正确回答是”指令局部性相同、数据局部性不同”，而不是笼统地说”两个程序局部性一样”或”不一样”。

局部性可以被写出来

二维数组在 C 语言中按行优先存放，因此：

for (i = 0; i < N; i++)          for (j = 0; j < N; j++)
  for (j = 0; j < N; j++)          for (i = 0; i < N; i++)
    sum += a[i][j];                  sum += a[i][j];
        ↑ 按行，空间局部性好              ↑ 按列，每次跨一整行

设 Cache 块能装 个数组元素：按行遍历时每 次访问只缺失 1 次，缺失率 ；按列遍历时若一行的长度超过 Cache 容量，则每次访问都缺失，缺失率接近 100%。

这就是”局部性是程序的属性”的全部含义：硬件只能被动地利用它，创造它的是代码。

边界

局部性是统计规律，不是保证。 它对绝大多数程序成立，但对精心构造的反例可以完全失效——例如步长恰好等于 Cache 容量除以相联度的遍历，会让每次访问都冲突缺失（见 3.5.3）。“Cache 一定能提高速度”是错的。

“局部性好”必须说清是哪一种、哪一部分。 一道题问”两个程序的局部性是否相同”，必须分指令与数据、分时间与空间四格来答，笼统地说”一样”或”不一样”都不得分。

空间局部性的度量是”步长”，不是”访问了多少数据”。 遍历一个 1 GB 的数组，只要是顺序的，空间局部性就好。

局部性同时是 Cache 和虚拟存储器的前提。 页式虚拟存储器的工作集概念、缺页率随驻留集大小的变化，全部建立在同一条规律上，见 OS 3.2.5 抖动与工作集。

对照速查

时间局部性空间局部性
内容刚访问的还会再访问刚访问的附近会被访问
指令的来源循环回跳顺序存放与执行
数据的来源反复使用的变量数组连续存放
硬件对策保留在 Cache 中按块装入
相关设计替换算法块大小、预取

考点

  • 层次存储器成立的唯一前提是局部性
  • 顺序执行 → 空间局部性；循环回跳 → 时间局部性（两者不能接反）
  • 指令局部性通常好，数据局部性取决于访问模式
  • 按行/按列遍历二维数组，指令局部性相同、数据局部性差别极大
  • 空间局部性决定块大小，时间局部性决定要不要保留
  • 局部性是程序的属性，硬件只能利用不能创造
  • 答”局部性是否相同”要分指令/数据、时间/空间四格

链接

反向链接