存储层次

不同存储介质在速度、容量、成本上差异巨大,现代计算机采用金字塔式的多级存储层次,以小容量高速层弥补下层速度不足。

金字塔结构

            寄存器     1 ns,    ~ KB
              |
             L1 Cache  1-2 ns,  32-64 KB
              |
             L2 Cache  3-10 ns, 256 KB-1 MB
              |
             L3 Cache  10-30 ns, 数 MB-几十 MB
              |
              主存     50-100 ns, 8-64 GB
              |
              SSD     10-100 µs, 数百 GB-几 TB
              |
              HDD     5-15 ms,   TB 级

上小下大,越靠近 CPU 越快越贵;每级作为下级的高速缓存,平均访存时间(AMAT)由命中率和各级延迟决定。

时间与空间局部性

• 时间局部性:刚被访问的数据短时间内可能再被使用,典型如循环变量、计数器。
• 空间局部性:被访问数据的相邻地址在短时间内也可能被访问,典型如数组顺序遍历。

利用这两条原则,Cache 块(行)通常为 32/64 字节,预取与预读也是典型优化手段。

Cache 三种映射

设主存共 M 块,Cache 共 C 块,块大小 B 字节。

• 直接映射:主存块 i 映射到 Cache 槽 i mod C。硬件简单,但抖动严重(两个活跃块映射同槽)。
• 组相联:Cache 分 S 组,每组 K 路,主存块 i 映射到 i mod S 组内的任意一路。K=1 即直接映射,K=C 即全相联。
• 全相联:主存块可放任意 Cache 槽,命中率高但比较器开销大,常用于 TLB、小容量 Cache。

替换算法

组相联/全相联发生冲突时需淘汰一路:

• LRU (最近最少使用):命中率最优,实现需记录访问顺序,4 路以上代价高。
• FIFO (先进先出):实现简单,命中率不如 LRU。
• 随机:硬件代价最低,性能接近 LRU。

写策略

• 写直达 (Write-Through):命中时同时写 Cache 与主存,数据一致性好,但写带宽压力大。
• 写回 (Write-Back):仅写 Cache,对应行置 脏位,淘汰时才写回主存,带宽省,需要一致性协议(MESI)保障多核一致。
• 写分配 (Write-Allocate):写不命中时,先把块加载到 Cache 再写;搭配写回策略使用。
• 非写分配 (No-Write-Allocate):写不命中时直接写主存,搭配写直达使用。