6.2 局部性

• 局部性 locality
  • 倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项的本身
  • 这种倾向称为局部性原理
• 时间局部性 temporal locality
  • 良好的时间局部性
    • 被引用过一次的内存位置很可能在不远的将来再被多次引用
• 空间局部性 spatial locality
  • 良好的空间局部性
    • 如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置
• 有良好的局部性的程序运行得快
• 局部性原理使：
  • 硬件层：引入“高速缓存存储器”的小而快速的存储器来保存最近被引用的指令和数据项
  • 操作系统级：系统使用主存作为虚拟地址空间最近被引用块的高速缓存

6.2.1 对程序数据引用的局部性

6.2.2 取指令的局部性

6.2.3 局部性小结

• 重复引用相同变量的程序有良好的时间局部性
• 对于步长为k的引用模式的程序，步长k越小，空间局部性越好
• 对于取指令，循环有好的时间和空间局部性
  • 循环体越小
    • 时间局部性越好
  • 循环迭代次数越多
    • 空间局部性越好

• 缓存命中 cache hit
  • 需要第k+1层的数据对象d，d刚好缓存在第k层中
  • 比读取第k+1层要快
    • 良好时间局部性
• 缓存不命中 cache miss
  • 第k层没有缓存数据对象d
  • 覆盖现存的块称为替换replacing或驱逐evicting
  • 被驱逐的块称为牺牲块 victim block
  • 决定替换哪个块是有缓存的替换策略replacement policy来控制的
    • 随机替换策略
    • 严格的放置策略
      • 将第k+1层的某个块限制放置再第k层的一小个子集中
  • 种类
    • 冷缓存：第k层缓存为空
      • 强制性不命中/冷不命中
        • 很重要
        • 短暂
        • 不会再反复访问存储器
          • 使得缓存暖身warmed up之后的稳定状态出现
    • 冲突不命中：限制性放置策略引起
      • 例如.第k+1层的块i必须放置在第k层的块（i mod 4）中.
    • 容量不命中：发生在当活跃块集合（工作集working set)）的大小比缓存大.

6.4.2 直接映射高速缓存

6.4.3 组相连高速缓存

1 <  E  < C/B

组相联高速缓存中的不命中的行替换

• 若组里有空行，则是个好候选
• 若无，必须选择一个非空的行
  • 最不常使用（LFU）策略：替换过去某个时间窗口内引用次数最少的一行
  • 最近最少使用（LRU）策略：替换最后一次访问时间最久远的一行

6.4.4 全相联高速缓存

E=C/B

• 组中没有索引位
• 地址被划分位标记和块偏移

• 高速缓存电路必须并行地搜索许多相匹配的标记
• 构造一个又大又快的相连高速缓存很困难，而且很昂贵
• 因此，全相联高速缓存只适合做小的高速缓存
  • 例如：虚拟内存系统中的翻译备用缓冲器（TLB）

6.4.5 有关写的问题

• 存在多个数据副本:
  • L1, L2, L3,主存, 磁盘
• 在写命中时要做什么?
  • 直写 (立即写入存储器)，将V=0
  • 写回 (推迟写入内存直到行要替换)
    • 需要一个修改位 (和内存相同或不同的行)
    • 局部性，减少总线流量
• 写不命中时要做什么?
  • 写分配 (加载到缓存,更新这个缓存行)
    • 好处是更多的写遵循局部性
  • 非写分配 (直接写到主存中,不加载到缓存中)
• 典型的
  • 直写 + 非写分配                         --高层-成本低
  • 写回 + 写分配-----建议       ---低层如虚拟内存  ---高层也用（集成度提高）

6.4.6 一个真实的高速缓存层次结构的解剖

• 只保存指令 i-cache
• 只保存程序数据 d-cache
• 都保存 unified cache

6.4.7 高速缓存参数的性能影响

• 命中时间
  • 从高速缓存向处理器发送一行的时间
    • 时间包括行是否在缓存中
  • 典型的数:
    • L1  4个时钟周期
    • L2  10个时钟周期
• 不命中处罚
  • 由于不命中需要额外的时间
    • 通常主存为50-200周期(趋势: 增加！)
• 不命中率
  • 一部分内存引用在缓存中没有找到 (不命中 / 访问)
  • = 1 – 命中率
    • 典型的数 (百分比):
  • §  3-10%  L1
    • 可以相当小(e.g., < 1%)  根据大小, 等等.

• 这就是为什么用“不命中率”而不是“命中率”
• 在命中和不命中之间差距巨大
  • 如果只有L1 和 主存，那么可以差100倍
• 99%命中率要比97%好两倍
  • 思考:
    • 缓存命中时间为1个周期
    • 不命中处罚要100个周期
  • 平均访问时间:
  • 97% 命中率:  1 周期 + 0.03 x 100 周期 = 4 周期
  • 99% 命中率:  1 周期 + 0.01 x 100 周期 = 2 周期

6.6 综合：高速缓存对程序性能的影响

6.6.1 存储器山

• 读吞吐量 (读带宽)
  • 每秒从存储系统中读取的字节数(MB/s)
• 存储器山：测量读取吞吐量作为空间和时间局部性的函数
  • 紧凑方式去描述存储系统性能

6.6.2 重新排列循环以提高空间局部性

假设：

• 按行扫描：不命中率 = sizeof(aij) / B
• 按列扫描：不命中率 = 1
• double类型
  • sizeof（double）=8
• 高速缓存，块大小位32字节
  • B=32
• n很大
  • 一行不能装进L1高速缓存

当行查找时，最快