前言本节围绕 Cache 三大核心问题展开学习主存块与 Cache 块如何建立映射关系三种映射方式Cache 空间存满后淘汰哪一块数据四种置换算法CPU 修改 Cache 数据后如何保证 Cache 与主存数据一致写策略基础概念铺垫Cache 存放主存数据块的副本CPU 优先访问高速 Cache缺失才访问低速主存数据传输单位为块Cache 块大小 主存块大小Cache 行组成数据区 标记 Tag 有效位 Valid置换算法额外加计数器写回法加脏位有效位0 该行数据无效标记无意义1 标记有效当前存储有效主存块副本一、Cache 与主存的三种映射方式统一例题条件全程举例主存总空间 256MB按字节编址地址 28 位Cache 共 8 行块块大小 64B2⁶B块内地址 6 位。主存总块数2²⁸ / 2⁶ 2²² 块主存块号占 22 位。1.全相联映射规则任意主存块可以存入 Cache任意一行无位置限制。地址拆分整个 22 位主存块号全部作为标记 Tag地址结构【22 位 Tag 标记 | 6 位块内地址】CPU 访存流程取出地址高 22 位 Tag遍历 Cache所有行逐行对比标记找到标记匹配 有效位 1 → Cache 命中用低 6 位块内地址取数据全部标记不匹配 / 有效位为 0 → 不命中从主存调入目标块随机选空闲 Cache 行存放。优缺点•优点空间利用率高只要 Cache 有空位就能存入命中率最高•缺点查找时需要对比全部 Cache 行硬件并行比较电路复杂访问速度最慢。2.直接映射规则主存块只能固定存入 Cache 唯一一行计算公式Cache 行号 主存块号 % Cache 总行数例Cache 共 8 行 (2³)主存块 1、91%819%81只能放入 Cache 第 1 行。二进制简化原理Cache 行数为 2ⁿ取主存块号末尾 n 位直接作为 Cache 行号无需除法电路。例题 82³取主存块号低 3 位为行号标记只需剩余 19 位。地址结构【19 位 Tag 标记 | 3 位 Cache 行号 | 6 位块内地址】CPU 访存流程取主存块号低 3 位直接锁定唯一 Cache 行仅对比这一行的 Tag 标记 判断有效位匹配且有效位 1 → 命中否则不命中直接覆盖当前行原有数据。优缺点•优点仅对比一行标记查找速度最快硬件最简单•缺点空间利用率极低不同主存块会争抢同一 Cache 行频繁覆盖命中率最低。3. 组相联映射折中方案工程最常用规则将 Cache 所有行均等分组每组包含 N 行称为N 路组相联主存块只能存入指定组内任意一行计算公式组号 主存块号 % 总组数例题8 行 Cache 分为 4 组每组 2 行二路组相联主存块 1、9 对 4 取余 1只能放入第 1 组。二进制简化原理总组数 2ⁿ主存块号低 n 位为组号例题 42²低 2 位是组号标记剩余 20 位。地址结构【20 位 Tag 标记 | 2 位组号 | 6 位块内地址】CPU 访存流程1.取主存块号低 2 位锁定唯一分组2.仅遍历当前组内所有行对比 Tag 有效位3.组内匹配成功则命中组内无空闲行时执行置换算法淘汰本组某一块。优缺点综合全相联、直接映射的优势平衡硬件成本与命中率实际 CPU 普遍使用。三种映射对比总结二、Cache 四种置换算法使用前提•直接映射固定位置覆盖不需要置换算法•全相联整个 Cache 满才置换•组相联对应分组全部占满才置换。统一测试场景Cache 共 4 行访问序列1,2,3,4,1,2,5,1,2,3,4,51.随机置换算法RAND规则Cache 空间不足时随机任选一块淘汰无任何逻辑判断。优缺点实现最简单完全不考虑程序局部性命中率不稳定实际极少使用。2.先进先出算法FIFO规则优先淘汰最早调入 Cache的块按调入时间排序。硬件实现用队列记录调入顺序循环 0、1、2、3 行依次轮换淘汰。缺陷不考虑块是否频繁访问早期调入但高频使用的块会被强制淘汰抖动现象刚被淘汰的块立刻又被访问重复频繁换入换出大幅降低效率。3. 近期最少使用算法LRU考试 / 工程重点核心思想遵循时间局部性近期很少访问的块未来大概率不用淘汰最久未访问块。1手动做题快速方法从当前访问位置向前遍历访问序列淘汰最晚出现的 Cache 内块。2硬件实现计数器方案每行配置独立计数器Cache 总行数为 2ᵏ仅需 k 位计数器计数器规则新块调入空闲行该行计数器置 0其余非空行计数器 1命中某行该行计数器清零所有更小计数器的值 1大计数器保持不变需要置换选择计数器数值最大最久未访问的行淘汰。优缺点命中率四种算法中最高硬件实现复杂度中等是现代 Cache 标准置换算法。局限若活跃主存块数量 Cache 总行数依然会产生抖动。4. 最不经常使用算法LFU规则每行计数器记录总访问次数淘汰访问次数最少的块若多块次数相同默认淘汰行号更小 / 调入更早的块。计数器规则块每命中一次计数器 1。缺陷只统计全局总访问次数忽略时间局部性曾经高频访问、现在长期不用的块计数器数值很大长期无法被淘汰浪费 Cache 空间实际效果差。四种置换算法对比三、Cache 写策略解决 Cache 与主存数据一致性基础说明读操作不会修改数据不存在一致性问题仅写操作需要策略区分分两类场景写命中、写不命中。场景 1写命中要写入的块已在 Cache 中1写回法回写法操作仅修改 Cache 副本不立刻同步主存新增硬件标记脏位Dirty脏位 0该行数据和主存一致淘汰时无需写回脏位 1该行被修改过淘汰时必须整块写回主存搭配方案通常和写分配法配合使用优缺点减少访存次数写速度快存在数据不一致风险。2全写法写直通法 Write-through操作写 Cache 的同时同步写入主存二者数据时刻一致优化增设写缓冲FIFO 队列SRAM 高速CPU 把写入数据丢进写缓冲即可继续执行后台硬件异步同步主存弊端大量连续写操作会填满写缓冲CPU 阻塞等待搭配方案通常和非写分配法配合使用优缺点数据永远一致无需脏位每次写都访问主存速度慢。场景 2写不命中要写入的块不在 Cache 中1写分配法先把目标主存块调入 Cache再修改 Cache 副本适配写回法。2非写分配法不加载主存块到 Cache直接修改主存适配全写法。标准搭配组合高性能 CPU Cache ↔ 写回法 写分配法简单设备 / 多级 Cache 高层 ↔ 全写法 非写分配法。拓展多级 CacheL1/L2/L3 Cache层级规则越靠近 CPU速度越快、容量越小、成本越高L1 L2 L3层级副本关系L1 存放 L2 的部分副本L2 存放主存部分副本各级之间同样存在一致性同步规则各级 Cache 内部采用全写法 非写分配Cache 与主存采用写回 写分配。四、整体知识框架复盘1.三大模块映射方式全相联、直接、组相联 → 解决 “块放哪”配套硬件标记 Tag 有效位 Valid置换算法RAND、FIFO、LRU、LFU → 解决 “满了删谁”仅全相联、组相联需要LRU 最优写策略写命中写回 / 全写、写不命中写分配 / 非写分配→ 解决 “数据同步”配套硬件脏位、写缓冲2. 核心做题结论地址拆分关键2ⁿ块 / 组对应 n 位行号 / 组号剩余高位为标记性能优先级命中率 LRUFIFORAND查找速度直接 组相联 全相联工程标配二路 / 四路组相联映射 LRU 置换 写回法 写分配法。
