计组原理

Cache

连续性

  • 时间连续性：同一数据不久将被访问
  • 空间连续性：相邻数据不久将被访问
Cache Hit 与存取时间

记

  • Cache Hit Rate 为 $h$
  • Cache 存取时间为 $T_{\mathrm{cache}}$
  • 主存存取时间为 $T_{\mathrm{mem}}$

则存取时间

$$T=T_{\mathrm{cache}}\cdot h + (T_{\mathrm{cache}}+T_{\mathrm{mem}})\cdot(1-h)$$

因为 Cache Miss 要先访问 Cache 再访问主存

主存映射

映射方式 直接映射 全相联映射 组相联映射
映射关系 Cache 行号 =
主存块号 % Cache 行数		 Cache 分为若干槽，
主存块按策略存入槽		 先取模直接映射到组，
再组内采用相联映射
tag 算法 地址 / 块长 % 组数(行数) 地址 / 块长 地址 / 块长 % 组数
优点 易实现，命中快，易淘汰 Miss Rate 低
缺点 命中率低 tag compare 慢
地址结构 [标记:行号:块内地址] [标记:块内地址] [标记:组号:块内地址]
寻址方式 1. 查询行号
2. 对比标记，一致 hit 否则 miss		 1. 查找标记是否 cached
2. 存在 hit 否则 miss		 1. 先查询组号 (直接映射)
2. 组内再相联映射
关联度

关联度 := 可用槽数 per Cache 组

一般关联度越高 $\Rightarrow$

  • Miss Rate 越低
  • 比较时间越长，Hit Time 越长
直接与相联

可以把组相联看成对 Cache 的 $m\times n$ 划分

  • $n=1$ 即 $m\times 1$ 时退化到直接映射
  • $m=1$ 即 $1 \times n$ 时退化到全相联映射

每组 $n$ 行，也叫 n-路组相联映射

地址位数

  1. len(标记) = $\log |主存地址空间|-\log 行数 - \log 行长$
  2. len(行号/组号) = $\log 组数$
  3. len(valid) = 1
  4. len(脏位) = 1

替换策略

常见替换策略

  • 随机 RAND
  • 先进先出 FIFO
  • 近期最不常用 LRU ⭐
    • 组内每行持有"常用值"，值越小越常用
    • 命中 $\Rightarrow$ 命中行值置 0，其余行 +1
    • 未命中
      • 组未满 $\Rightarrow$ 新行置 0，其余行 +1
      • 组满 $\Rightarrow$ 值最大的被替换，新行置 0，其余行 +1
  • 最不常用 LFU

主存一致性

写命中

一致性方式 全写法 Write Through 回写法 Write Back
写命中时 同时写 Cache 和主存 只写 Cache
Cache 替换时 将 Cache 写回主存
优点 一致性 减少访存次数
缺点 增加访存次数 一致性风险
实现部件 写缓存 修改位 (脏位)
写缓存

减少全写法直接写回主存的时间损耗 设计为 FIFO 队列

写不命中

  • 写分配法
    1. 先把下一层内存块写到 Cache
    2. 再对 Cache 进行写操作
  • 非写分配法 避开 Cache 直接对主存写

多级 Cache

  • 单级/多级
    • on-chip cache：Cache 和 CPU 在同一芯片上
    • off-chip cache：独立设置 Cache
  • 联合/分立
联合/分立 联合 分立
组织形式 数据+指令存在相同 Cache 分离单独的 数据Cache & 指令Cache
命中擅长 命中率 命中时间
应用采用 L2 Cache L1 Cache
应用采用原因 减少主存访存 减少时钟周期，防止结构冒险
(就算 Miss，L2 Cache 访存代价也不大)

坑点总结

  1. 从高级编程语言(C, C++, …) 看 cache hit，先转成指令 e.g. a[k] = a[k] + 32 其实访问了 a + k 处两次 (lw + addi)
  2. Cache 比较器用于并行比较组内 tag，个数 = 组内行数，位数 = $\log_{2}|\mathrm{tag}|$