局部性

具有良好局部性的程序倾向于一次又一次地访问相同的数据项集合，或是倾向于访问邻近的数据项集合。具有良好局部性的程序比局部性差的程序更多的倾向于从存储器层级结构的高层次处访问数据项，因此运行得更快

局部性有两种形式：

• 时间局部性：在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次引用
• 空间局部性：在一个具有良好空间局部性的程序中，如果一个内存的位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置

量化评价程序中局部性的一些原则：

• 重复引用相同变量的程序具有良好的时间局部性
• 对于具有步长k的引用模式程序，步长越小，空间局部性越好。在内存中以大步长跳来跳去的程序空间局部性很差
• 对于取指令来说，循环具有良好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好

存储器层级结构

存储器层级结构.png

从高层往底层走，存储设备变得更慢、更便宜和更大

存储器层级结构的核心思想是：对于每个k，位于k层的更快更小的存储设备作为位于k+1层的更大更慢的存储设备的缓存。换句话说，层级结构中的每一层都缓存来自较低一层的数据对象。

对于缓存而言，有几个重要的感念：

• 缓存命中：当程序需要第k+1层的某个数据对象d时，它首先会在第k层的一个块中查找d。如果d刚好缓存在第k层中，那么就是我们所说的缓存命中
• 缓存不命中：如果k层中没有缓存数据对象d，就表示缓存不命中

  发生缓存不命中之后，k层会从k+1层中读取出包含数据d的块。如果此时k层已经满了，就会根据替换策略来替换或是驱逐某个块。被替换或驱逐的块也被称为是牺牲块

高速缓存存储器

高速缓存的通用组织.png