Cache映射方式与替换策略
Cache映射方式与替换策略
复习定位
Cache的容量很小——主存内容需要映射到Cache中。映射方式决定了一个主存块可以放在Cache中的哪些行——同时也决定了Cache未命中时的替换策略。组相联是折中——让每个主存块只有少量选择(几路)——冲突低且硬件可实现。替换策略决定组满了后——哪个Cache行被踢出去——LRU效果最好但实现最复杂。
三种映射方式
直接映射(Direct Mapping)——将主存地址分为三段：标记位(Tag)|块号(Line)|块内偏移(Offset)。主存块固定映射到Cache中的一行——通过块号运算直接确定位置。CPU访问内存时——用块号找到对应的唯一Cache行——比较该行存储的Tag是否与地址中的Tag匹配——相同则命中。优点——查找简单速度快。缺点——冲突率高——两个经常访问的块如果映射到同一行即使其他Cache行空闲也会互相挤掉。
全相联映射(Full Associative)——主存块可进入任意Cache行。地址结构：Tag|Offset——不需要Line位。访问时——需要将地址的Tag与Cache所有行的Tag同时比较。优点是利用率高——没有冲突未命中。但需要昂贵的全相联比较器——每个时钟周期要同时比较几百个Tag——功耗和面积巨大。只适用于小容量Cache。
组相联映射(Set Associative)——折中——Cache被分为多个组——每组包含几行(几路)。地址结构：Tag|Set|Offset。主存块先映射到固定的组(通过Set位确定)——在该组内可以占据任一行。查找时——根据Set位确定组——然后组内的几路Tag与地址中的Tag同时比较。典型L1Cache为8路组相联。组相联在命中率和硬件成本之间取得了较好的平衡。
替换策略(当组已满)
LRU(Least Recently Used)——替换组中最近最少使用的行。完全精确的LRU需要用额外计数器跟踪每组每行的访问顺序——n路组相联每组需要log₂(n!)种状态来记录完整的最近使用顺序——4路需log₂(4!)=5位——8路需log₂(40320)=16位——随路数增长而快速膨胀。
伪LRU(Pseudo-LRU或Tree-PLRU)——近似LRU——使用二叉树跟踪路的使用历史——每次访问一路时——设置树路径上每个结点指向该路的方向——替换时沿未被访问的方向走到叶子——选一个路替换。4路需3位二叉树——8路需7位——远少于完全LRU——且命中率接近完整LRU。现代CPU的L2/L3 Cache通常使用Pseudo-LRU。
随机替换(Random)——在组内随机选择一行替换。实现极简——在不少大型L3 Cache(如Intel的某些芯片)中使用——因为路数较多时LRU提升的命中率不足以抵消其硬件复杂性——而随机策略表现稳定。
写策略对性能的影响
写直达——每次写Cache时都要写下一级(如L2/主存)。每次写都需等待下一级接受数据——写性能差。但实现简单——一致性容易维护(因为下一级始终持有最新数据)。大多数CPU的L1Cache使用写直达(保证L1和L2一致——L2使用写回以减少对主存的写)。
写回——写Cache时不立即写下一级——只在Cache行被替换时才把数据回写到下一级。需要脏位(dirty bit)记录该行是否被修改过。写回减少了慢速的下一级写操作——极大幅度提高写的性能。现代CPU的大多数Cache(L1/L2/L3)基本使用写回。
复习检查
直接映射Cache——地址格式中哪部分决定Cache行号——Tag和Offset分别是做什么的？为什么高地址位用来做Tag而不用来做行号——例如Tag所占位数较多使得标记(Tag)占主导——如果行号位数占的过少可能使很多块映射到同一行——频繁冲突。
n路组相联Cache如果从2路变为4路——命中率能否得到具有商业价值的提升——对硬件复杂度的影响是什么(需要更多的比较器——寄存器组的数量迅速扩大)？
LRU替换策略在8路组相联中的硬件成本——完全LRU需要16位记录状态(2^16种可能)但实现真实LRU不仅仅需要位宽——还要额外的比较逻辑——所以Pseudo-LRU(3位二叉树)在相近的命中率下更受看好。
写回策略的脏位——当替换Cache行时——如果脏位=1——必须将此行的数据写回下一级——如果脏位=0——可以直接丢弃——因为下一级的数据与此行一致。为什么脏位能避免不必要的对主存的写操作？
为什么L1指令Cache从不写数据——所以它的写策略永远是"写直达"还是不需要写策略——指令Cache只读——它的Cache块被踢出时只需丢弃(因为没有改变它)不需要写回——所以指令Cache可以简单得多。
三种映射方式的地址结构对比
直接映射、全相联和组相联的地址结构差异体现在地址的划分方式上：
| 映射方式 | Tag(标记) | Index(索引) | Offset(偏移) | 适用容量 |
|---|---|---|---|---|
| 直接映射 | 高位数位 | Cache行号位数 | 块内偏移位数 | 小容量L1 |
| 全相联 | 全部地址高位 | 无 | 块内偏移位数 | 极小(TLB) |
| 组相联 | 高位Tag | 组号位数 | 块内偏移位数 | L1/L2/L3 |
假设64位地址、64字节Cache行、32KB L1 Cache、8路组相联：每组包含8行(8路)、组数=32KB/(64B×8)=64组——因此Index占6位——Offset占6位(64字节对齐)——Tag占52位(64-6-6)。地址确定为Tag+Index+Offset三部分的组合——CPU访问时先通过Index定位到组——然后8路Tag并行比较——匹配成功则命中并从该行的缓存框中读取数据。
写策略对性能影响的定量分析
写直达每次写Cache都要写下一级——对内存带宽的消耗显著——因为写操作带宽是读的两倍(读一次命中——写一次同时写Cache和下一级)。假设CPU运行频率3GHz——L1数据Cache写命中率95%——L2命中延迟10周期——每次写直达都要经过L2的写(即使L2也命中)——则频繁写操作会对L2造成大量访问压力。
写回策略仅在替换时才写下一级——当CPI被Cache miss支配时(特别是大量写操作的应用如数据库事务日志)——写回可以明显减少对下级存储的写次数——因为在替换之前该行中的数据可能被多次修改——但只在最后写回一次。写回需要脏位(dirty bit)记录该行是否被修改——替换时查询脏位：脏位=1写回——脏位=0直接丢弃不做额外写入。
Cache性能评价指标
命中率(Hit Rate)——CPU访问命中Cache的比例——通常L1命中率95%以上、L2约80-90%、L3约60-70%(多核共享后的大容量命中率更高)。
缺失损失(Miss Penalty)——一次Cache miss导致CPU等待的额外周期数——L1 miss去L2约10-20周期——L2 miss去L3约30-50周期——L3 miss去主存约200-300周期。可以看到L3 miss的代价极大——所以计算机系统的主要设计目标就是尽量减少L3 miss。
平均存储访问时间(Average Memory Access Time) = Hit Time + Miss Rate × Miss Penalty。Hit Time是命中时的访问延迟。对于L1 Cache——Hit Time约1-2周期；Miss Rate约2-8%；Miss Penalty约10-20周期(到L2的延迟)——因此L1贡献的AMAT约为1 + 0.05×15 ≈ 1.75周期——如果L1 miss率从5%降到2%——AMAT=1+0.02×15=1.3周期——性能提升约25%。
Cache一致性与写策略
在多核系统中——不同核的Cache可能同时持有同一主存行的副本——其中一个核修改了数据——其他核的副本变成过时——这就是Cache一致性问题。核心通过一致性协议(如MESI协议)确保所有核看到的同一数据是一致的。写直达简化了cache一致性——因为每次写都更新下一级——其他核通过"监听"下一级的更新来发现数据变化——但写回策略需要在替换和一致性协议中通过"无效"消息让其他核的副本失效——实现更复杂但性能更好。
复习检查（续）
64位地址、64B行、8路组相联、32KB L1 Cache——问Tag/Index/Offset各占多少位——Index = log₂(组数) = log₂(32KB/(64B×8)) = log₂64 = 6位。
全相联映射为什么不适合大容量Cache——Tag比较需要同时访问所有行——n行需要n路比较器——n越大硬件成本线性上升——功耗和面积在数百行的大容量下不可接受。
伪LRU(二叉树法)在8路组相联下需要多少位——7位(二叉树有7个结点)——远少于完全LRU(16位)——且命中率接近完全LRU。
写直达策略下——一次写L1 miss会发生什么——写直达+写不分配时直接写下一级(L2)而不分配L1——写直达+写分配时先从L2把行读入L1再写L1再写L2——大多数写直达采用写不分配以减少L1的写入流量。
平均存储访问时间的计算——L1命中率95%——命中时间1周期——L1 miss罚时10周期(L2命中)——AMAT=1+0.05×10=1.5周期。
Cache的行程局部性与预取
硬件预取器通过检测连续访问的模式——在程序实际请求之前预加载Cache行——降低Cache miss。当代英特尔处理器拥有多个预取器(IP-based预取器根据指令PC记录访问地址的步幅——下一条指令的访存计数由当前指令动态推进——L2预取器根据L2的缺失模式提前发起对L3或主存的预取)。预取的粒度通常是连续的几行——对线性遍历数组等具有规律访存模式的代码极其有效。
程序优化的Cache友好策略
顺序访问——对于需要频繁遍历的数据结构——尽量使用数组(连续内存布局)而不是链表(随机散布)串联访问。链表的p=p->next指针跳跃导致无法进行连续内存空间的空间局部性预取——引发大量Cache miss——性能降幅可达数组的10倍以上。
数据对齐——将经常一起访问的数据放在同一个Cache行中(如结构体字段重排使热点字段在同一个行内)——降低Cache行需求的同时提升一次访存就拿到所有需要数据的概率。
分块遍历——对于大矩阵的转置或归约运算——在循环中按Cache行大小分割——确保内部多次循环的数据在Cache换出之前集中在小组块中被反复重用——经典的分块循环的访问方式可以大幅降低大矩阵遍历的Cache miss。
实际性能分析中的Cache行为考量
程序员不需要时刻关注Cache——但在性能敏感的场景下——Cache局部性是可以用perf等工具观测到的：
perf stat -e cache-references,cache-misses,cycles,instructions ./program输出的cache-misses/cache-references比例就是Cache miss率——如果程序的Cache miss率超过10%——说明数据结构或访问模式可能是性能瓶颈——可以通过将链式数据结构改为数组、合并多次遍历、按照Cache行大小对齐数据等方法优化。
多核环境下的Cache伪共享问题
当两个核频繁读写不同的变量——但这两个变量恰好在同一个Cache行中——Cache一致性协议迫使该行在核间来回传递(即使两个核操作的是不同的变量)——这种现象称为"伪共享(False Sharing)"——性能损耗可能高达数倍。解决方案：在结构体字段之间加入填充字节——将热点变量分离到不同的Cache行——使不同核操作的变量处于不同的Cache行中——避免不必要的Cache一致性通信。
Cache与虚拟内存的交互
TLB(Translation Lookaside Buffer,转译后备缓冲区)是CPU内部用于缓存最近使用的虚拟地址到物理地址映射的Cache——本质上也是一个Cache——但TLB的miss需要CPU内存页表遍历(多级页表查表)——代价远高于普通Cache miss(可上百周期)。TLB未命中率较高时——可以通过使用大页面(huge page, 2MB/1GB页)减少页表项数量——从而降低TLB miss。在数据库和大数据应用中——操作系统配置透明大页面(THP)通常可以提升性能。
复习检查（续三）
一个数组大小为8MB——L1 32KB——L2 1MB——L3 8MB——遍历一次需要多少次L1 miss——多少需要从L3读——多少需要从主存读？
伪共享的成因——两个变量位于同一Cache行——两个核各自频繁写不同变量——一致性协议使行在核间传递——每次写都使对方的副本失效——性能急剧下降。
TLB的作用是什么——Cache虚拟地址到物理地址的映射——避免每次访存都遍历多级页表。
大页面(huge page)如何降低TLB miss——2MB页面比4KB页面所需页表项少512倍——TLB的相同条目数可以覆盖更大的地址空间。
写回策略为什么比写直达更适合现代CPU的多级Cache层次——写回L1再写回L2再写回主存——每次写操作只修改L1——替换时才写下一级——减少了总线写流量。
Cache替换策略的工程选择分析
在实际CPU微架构设计中——替换策略的选择是在访存模式的预期命中率和实现成本之间的权衡：
L1 Cache——容量小(32-64KB)——路数少(8路)——使用完全LRU或近似LRU——因为L1的访问频率最高——LRU对命中率的微小提升在总性能上有显著影响且硬件成本有限。
L2 Cache——容量中等(256KB-2MB)——4-16路——使用伪LRU或随机——因为L2的load/store频率较L1低——且优先使用更适合处理L2大容量的Tree-PLRU(二叉树伪LRU)——它的命中率与完全LRU相比几乎无损失但硬件开销少了近一半以上。
L3 Cache——容量大(8MB-64MB)——路数多(12-24路)——常使用随机替换策略——因为L3的访问频次已经很低——路数多使得随机策略替换到热行的概率已经足够低——而LRU的硬件复杂度(16路以上完全LRU约需几百位状态位)在经济性上不具备优势。
复习检查（续四）
L1 Cache为什么通常使用LRU或近似LRU——L1路数少、访问频率最高、LRU的命中率增益明显且硬件成本可接受。
L3 Cache为什么常使用随机替换策略——L3路数多在12-24路——随机替换命中率接近LRU——LRU的硬件成本在路数多时增长到不可接受。
伪共享问题的诊断方法——在perf中观察到
cache-misses比例异常高但程序的访存量不大——可能原因是多个线程写同一Cache行中的不同变量——典型场景是结构体数组中的多个字段被不同线程分别修改。分块遍历如何降低Cache miss——将大数组的遍历切分为Cache容量级别的小块——使小块内的数据在被冲洗之前得到充分重用——减少对外存带宽的占用。
平均存储访问时间公式的直接含义——减少miss rate和减少miss penalty同样有效——但减少miss penalty通常需要更大的Cache(增加Hit Time)——需要权衡。
Cache映射方式地址计算示例
条件：64位地址系统、64字节Cache行(Offset 6位)、256KB L2 Cache、8路组相联
组数 = 256KB / (64B × 8路) = 512组 → Index 9位(2^9=512)
Offset = log₂(64) = 6位
Tag = 64 - 9 - 6 = 49位
CPU访问地址 0x7FFF12345678：
二进制: 0111 1111 1111 1111 0001 0010 0011 0100 0101 0110 0111 1000
Tag(49位): 按上述计算截取
Index(9位): 取中间9位确定Cache组
Offset(6位): 取最低6位确定字节在行内的位置
物理硬件中Index被送入组译码器选中具体的Cache组——该组内8行的Tag全部与地址的Tag用比较器并行比对——匹配则命中——8选1的数据多路器将对应行的数据返回。写分配与写不分配策略
写分配(Write-Allocate)——写miss时先将数据从下一级读入Cache行中——然后在该行上执行写操作。配合写回策略时最常用——因为写操作后不久通常在同一Cache行上还有后续读或写(时间局部性)——预先分配行可以避免接下来再次产生Cache miss。
写不分配(Write-No-Allocate or Write-Around)——写miss时直接写下一级而不将行读入Cache。配合写直达策略——因为写直达直接写下一级——不需要在Cache中留下副本。写不分配可以有效避免"一次性写"(如memcpy写大块数据)将Cache中已有的热数据冲走——当仅在大块写入操作后并不需要从该地址读取时适用写不分配。
大多数现代CPU对L1数据Cache使用写回+写分配的混合策略——根据写miss的地址模式判断是一次性流式写入还是分散的随机写入——动态调整写分配策略以获得更好的综合性能。