为什么你的CPU那么快？Cache如何填平与内存的“速度鸿沟”？

目录一、CacheCPU与主存之间的“高速驿站”1为什么要有Cache2现代3级Cache3Cache与内存的数据交互二、内存条及其编址方法1内存条多DRAM的集合2多DRAM芯片的地址编码方式3内存条预MDR寄存器的数据交互三、局部性原理、主存块突发传输1局部性原理2主存块的概念四、Cache映射数据如何在Cache中存放的1Cache的不同结构与映射方法1. 直接映射2. 全相联映射3. 组相联映射2Cache与内存的完整交互过程五、Cache替换算法高效利用缓存空间的核心策略1. 随机算法Random2. 先进先出算法FIFO3. 最近最少使用算法LRU在计算机系统中“速度匹配”是永恒的命题——早期CPU与主存的直接交互因两者速度鸿沟成为性能瓶颈。而Cache与内存编址技术的演进正是为了填补这一鸿沟让数据流动既快又准。一、CacheCPU与主存之间的“高速驿站”1为什么要有Cache早期的CPU内部是没有Cache的而CPU的运算速度远超主存的访问速度两者存在数量级的速度鸿沟——普通CPU的运算周期仅为纳秒级1~10ns而主存DRAM的访问延迟通常在几十到上百纳秒直接交互会让CPU频繁进入“等待访存”状态严重拖累系统性能。于是由SRAM静态随机存取存储器构成的Cache应运而生它是CPU寄存器与主存之间的中间层访问速度接近CPU运算速度L1 Cache延迟仅1~3ns容量虽远小于主存但能将高频访问的数据“就近缓存”让大部分访存操作在Cache内完成大幅减少CPU等待时间。2现代3级Cache随着计算机的发展一级Cache已经不够用了于是为了进一步平衡速度、容量与成本现代CPU采用三级Cache架构各级Cache呈现“速度递减、容量递增”的层级特性L1 Cache最靠近CPU核心容量最小通常每核心32KB~64KB延迟最低1~3ns。分为独立的指令CacheI-Cache与数据CacheD-Cache避免“缓存污染”指令与数据的访问模式差异导致的命中率下降由单个核心独享优先缓存当前指令流和数据流的高频数据L2 Cache容量中等通常每核心256KB~2MB延迟介于L1与L3之间3~10ns指令与数据混合存储同样为单核心独享作为L1 Cache的“后备缓存”——当L1未命中时优先从L2读取数据避免直接访问延迟更高的L3或主存L3 Cache容量最大通常整个CPU共享8MB~64MB甚至更大延迟相对较高10~30ns多核心共享通过MESI等缓存一致性协议保证不同核心Cache数据的同步。它作为L2 Cache的后备缓存多核心共享的高频数据进一步降低主存访问概率。3Cache与内存的数据交互从数据交互的核心逻辑来看Cache与内存的协作围绕CPU访存请求展开核心是“优先从Cache读取Cache缺失再访问内存”具体基础流程可概括为CPU发起访存请求时首先将目标地址发送至Cache控制器尝试从L1 Cache读取数据若L1 Cache命中找到目标数据则直接将数据返回CPU无需访问内存整个过程仅需1~3ns若L1 Cache未命中控制器会依次查询L2、L3 Cache若在某一级Cache命中数据会逐级返回CPU同时更新上级Cache如L3命中则将数据写入L2、L1 Cache方便后续访问只要有任意一级命中则无需经过MDR、MAR寄存器去内存拿数据极大的提高了输出传输效率。若所有级Cache均未命中即“Cache缺失”则需访问主存CPU将地址、数据写入MAR、MDR中然后通过总线交给内存控制器再由内存控制器将地址发送至内存从DRAM中读取目标数据块并行的写入Cache和CPU。通常从L3开始逐级缓存当Cache空间已满写入新数据块时会通过替换算法如LRU淘汰Cache中“最不可能被后续访问”的数据行为新数据腾出空间。这种“分层缓存优先读取”的交互模式能让绝大多数高频访存操作在Cache内完成大幅减少CPU等待主存的时间充分发挥Cache的高速优势弥合CPU与内存的速度鸿沟。其中L1级缓冲中指令和数据分离的特点让指令、数据缓存避免了缓存污染同时指令缓存还能自发的有预取功能、且现代计算机还能通过指令流水线进一步提高运行速度。二、内存条及其编址方法1内存条多DRAM的集合由于DRAM芯片容量有限且位宽固定常见8bit、16bit无法直接匹配CPU的宽位宽32位、64位访存需求因此需要将多个DRAM芯片集成在一个主板---内存条中通过“位扩展”的方式级联。单条内存条的核心设计逻辑将多个DRAM芯片的地址线、控制线全部并联仅将数据线独立拆分后并行拼接形成更宽的总位宽。例如常见的8颗8bit DRAM芯片组成的内存条8颗芯片共享同一组地址线和控制线每颗芯片的8bit数据线对应数据总线的一个位段如芯片1对应bit0~bit7芯片2对应bit8~15……芯片8对应bit56~63最终拼接成64bit的总位宽恰好匹配64位CPU的MDR存储器数据寄存器位宽。而容量上还能将上述步骤重复几次以字扩展的方式扩容。注意这里一定要区分位扩展和字扩展。位扩展是各个DRAM并行连接会产生传输膨胀的效果好比拓宽了高速公路的宽度原本只能一次过1辆车现在一次可以过8辆车。而字扩展则是单纯的提高容量各个DRAM之间是串行连接通过片选线选中一个所以同一时刻只能有一个DRAM芯片被选中即同一时刻只能输出8字节。而前面我们说一次CPU和主存交互是1存储单元实际上是不准确的而应当是1次传输的总量这里的存储单元更多的是物理硬件上的视角即物理地址单元而非计算机中的逻辑地址。因为计算机软件认为1存储单元1字节但由于位扩展的存在一次传输的总量应当是MDR的宽度这里就是8字节所以那软件视角看待硬件是不合理的。而字扩展单纯的提高了容量但是由于指令流水线的存在同样可以看做并行即可以把输出的过程分解成更小的步骤比如1号DRAM正在输出2号就能正在取址宏观上看起来是并行同时输出给MDR的。但实际上仍然是串行只不过这个时间间隔非常小。而这个过程我们就称为突发传输用于Cache行与内存之间的数据交互。2多DRAM芯片的地址编码方式而多个DRAM芯片级联后天然的就出现了如何编码的问题。早期计算机由于容量要求低甚至可能只有一个DRAM芯片多采用顺序编址能利用一下局部性原理提高访存速度。而现代计算机多采用交叉编址能让多个DRAM芯片同时类并行传输向MDR寄存器传递数据以提高数据交互效率。顺序编址连续地址的数据集中在同一个存储体契合局部性原理但只能串行访问交叉编址连续地址的数据分散到不同存储体能让多存储体类似并行工作实际上仍有微小的串行时间差但是可以忽略所以宏观上是并行。3内存条预MDR寄存器的数据交互多个DRAM芯片向MDR并行传输数据的完整过程CPU发起访存请求将目标主存物理地址写入MAR存储器地址寄存器内存控制器接收该地址后通过地址总线将地址同时广播给内存条上的所有DRAM芯片因地址线并联所有芯片接收相同地址内存控制器发送片选信号同时选中这8颗DRAM芯片指令它们根据接收的地址读取对应存储单元的数据8颗DRAM芯片同步响应各自从自身存储单元中读出8bit数据通过各自对应的数据线并行输出到内存总线内存总线上的8路8bit数据同步拼接成64bit完整数据通过内存控制器直接送入64位MDR中MDR暂存该数据后立即通过CPU内部数据通路将数据送入运算单元或通用寄存器完成一次访存。这种设计的核心价值是“并行提升带宽”单颗8bit DRAM芯片一次仅能传输1字节数据而8颗芯片并行传输可一次传输8字节64bit传输效率提升8倍完美匹配MDR的宽位宽需求避免了因单芯片位宽不足导致的传输瓶颈。若计算机支持多通道内存如双通道、四通道还可将多条内存条的数据线进一步并联实现更高位宽的并行传输如双通道可实现128bit并行传输进一步提升内存带宽。三、局部性原理、主存块突发传输1局部性原理时间局部性被访问过的数据短期内大概率会再次被访问比如循环中的变量空间局部性被访问数据的“周边数据”短期内大概率会被访问比如连续的数组元素。Cache正是利用空间局部性将主存中“被访问数据的周边区域”即主存块一次性载入Cache——这一过程称为“突发传输”比逐字节传输效率高得多。2主存块的概念主存块又称Cache行。指内存中被一次性载入Cache的连续数据区域大小通常为32Byte、64Byte等具体由系统架构和Cache设计决定。Cache正是利用空间局部性将主存中“被访问数据所在的主存块”一次性载入Cache。主存块一般是MDR的整数倍但也不能太大。比如两条内存条每一条都由4个DRAM芯片组成则两条内存条同时可以并行传输2*48字节的数据那么MDR就会被设计成8字节即64位。而主存块就会设计成8、16、32、64字节大小本质是多次MDR数据的打包。这个过程是突发传输方式完成的。下篇文章讲解相比逐字节传输能提前缓存后续大概率被访问的周边数据大幅提升访存效率。四、Cache映射数据如何在Cache中存放的1Cache的不同结构与映射方法为了让主存块高效存入Cache需通过映射方式确定Cache行的位置。所以Cache不是单纯的数据中转站而是快递站对每一个Cache行主存块都有一定的编号、控制作用。而映射方式直接决定Cache的结构、冲突率、访问速度与硬件复杂度常见的三种方式各有侧重。由于Cache的容量远小于主存的容量对应的Cache中Cache行的个数也远小于主存块的数量。所以没办法让每个Cache行与主存块一一对应所以映射采用多对一的思想多个主存块会映射到同一个Cache行中。Cache的结构由映射方式与功能需求决定核心包含三部分基础字段有效位标记Cache行是否存储有效数据初始化时为0载入数据后设为1行被替换时若数据被修改则写回主存后设为0标记段存储主存地址的标记部分用于与主存地址比对判断访存是否命中数据段存储主存块的实际数据大小与主存块一致常见32B、64B。此外为适配写策略与替换需求在标记段中还会增加额外字段支持“写回策略”的Cache会增加“脏位”标记数据是否被CPU修改修改过则替换时需写回主存组相联Cache会增加“LRU位”即替换算法位记录组内各行的访问顺序用于替换决策多核共享Cache会增加“共享位”用于MESI等缓存一致性协议保证多核数据同步。1. 直接映射直接映射虽然规则简单但映射比较固定容易形成“冲突”。即特定的地址会抢占某一个Cache行即使其他Cache行时空闲的所以利用率比较低。例如程序频繁访问主存块0、8、16均映射到第0行会持续触发替换缓存命中率极低。不过他形成了一个类哈希桶的效果索引很快访问延迟极低且只需要一个比较器硬件成本低这也是直接映射的优势所在。2. 全相联映射正是为了避免直接映射的冲突问题所以全相联映射才采取了随机插入的方式。无固定的映射关系彻底避免了冲突。所以Cache的空间利用率较高。不过由于他是随机插入的可以类比成链表只能遍历比较时间复杂度高又或者你给每一行都设置一个比较器成本较高一般全相联都是给每一行设计一个比较器让他们同时工作无论是电路设计、还是瞬时功耗都比较高这也是前面说他成本高的原因不仅是设计成本高而且是使用成本高。3. 组相联映射组相联映射方案的冲突概率远低于直接映射硬件复杂度远低于全相联映射缺陷是组内行数路数越多硬件复杂度越高。但相对全相联映射已经极大减少了硬件成本。组相联映射虽然也会给每一行都设计一个比较器但通过时钟树切断的思路让瞬时功耗大大降低即一次只欢迎一个组里面的比较器。同时这样的设计不用考虑同时启动时候的电磁干扰屏蔽等问题使得硬件设计成本大大降低现代计算机的L1、L2、L3缓存均广泛采用组相联映射通过调整路数平衡性能与成本——L1缓存追求低延迟多采用2路或4路L3缓存追求高利用率可采用8路甚至16路。2Cache与内存的完整交互过程Cache与内存的交互围绕“CPU访存请求”展开核心分为“Cache命中”和“Cache未命中”两种场景不同场景下的数据流向与操作逻辑存在显著差异具体流程如下1. Cache命中场景数据不经过主存直接从Cache读取当CPU发起访存请求时命中流程全程在CPU内部与Cache之间完成无需与主存交互步骤如下CPU输出目标内存地址给Cache虚拟地址需先经MMU转换为物理地址地址拆分模块将物理地址拆分为“TAG位、组索引全相联映射无此部分、块内偏移”三部分组索引定位到Cache的目标组直接映射定位到目标行TAG位被送入该组内所有行的比较器比较器将输入的TAG位与Cache行的标记段比对若某一行标记位匹配且有效位为1即判定为“命中”根据块内偏移从命中的Cache行数据段中提取CPU所需的具体字节/字提取的数据通过CPU内部数据通路送入运算单元或通用寄存器同时更新该Cache行的LRU状态位标记为“最近访问”确保后续替换时优先保留。2. Cache未命中场景从主存加载数据到Cache同时传递给CPU访问当标记位比对无匹配项或匹配行有效位为0时判定为“未命中”此时需从主存加载数据到Cache流程分为“加载数据”和“数据使用”两步若Cache已满还需执行“替换淘汰”操作未命中判定后CPU暂停当前访存操作等待数据加载CPU将目标物理地址写入MAR存储器地址寄存器通过地址总线发送至主存控制器控制主存读取对应主存块的数据主存内存条的多个DRAM芯片并行工作读取目标主存块通过数据总线将数据传输至MDR存储器数据寄存器Cache控制器判断当前Cache是否已满若未满直接将MDR中的主存块写入Cache的空闲行利用突发传输效率更高同时设置该行的有效位为1、标记段为当前主存块的标记位若已满则通过替换算法如LRU淘汰Cache中符合条件的旧行再写入新主存块新主存块写入Cache的同时并行的由MDR把该字节数据选取出来通过内部数据通路送入CPU的运算单元或通用寄存器也有书说的是先写到Cache再由Cache送给CPU的串行操作CPU恢复暂停的操作同时更新新写入Cache行的LRU状态位标记为最近访问。五、Cache替换算法高效利用缓存空间的核心策略前面我们讨论的都是内存数据如何保存到Cache行中是以什么结构格式保存的。但是却忽略了一个问题如果Cache行满了该如何选一个淘汰替换呢在直接映射中淘汰的目标是显然确定的但现代计算机是组相联映射只能确定淘汰的组无法确定具体淘汰哪一个Cache行。此时就需要使用替换算法替换算法的核心目标是“淘汰未来最不可能被访问的数据行”最大化缓存命中率。主流替换算法包括随机算法、先进先出FIFO算法、最近最少使用LRU算法及近似LRUPLRU算法具体如下1. 随机算法Random随机选择一行数据淘汰无需记录任何访问信息。优势是实现最简单、硬件开销最低缺陷是完全违背局部性原理可能淘汰近期频繁访问的数据导致命中率大幅下降仅适用于对性能要求极低的场景。2. 先进先出算法FIFO按数据载入Cache的顺序淘汰即淘汰最早载入的一行数据。通过维护一个访问队列实现新数据入队尾淘汰时出队头。优势是实现简单能在一定程度上利用时间局部性缺陷是存在“Belady异常”——当Cache容量增大时命中率反而可能下降。例如访问序列为“1→2→3→1→2→4→1→2→3”此时明显1访问的较多却由于先进先出每次都要重新加载这一缺陷限制了其在高性能Cache中的应用。3. 最近最少使用算法LRU淘汰最近一段时间内“最少被访问”即最久未被访问的一行数据是最契合局部性原理的经典算法。其核心假设是“最近被访问的数据未来被访问的概率更高最久未被访问的数据未来被访问的概率最低”。分为“访问更新”与“淘汰决策”两步。① 访问更新每当某行数据被命中或载入时立即更新其“最后访问时间戳”为当前时刻或更新其在访问序列中的位置为最新② 淘汰决策Cache满时遍历所有有效行找出最后访问时间戳最早的一行淘汰。例如4路组相联Cache某组内4行的最近访问顺序为“行A→行B→行C→行D”行A最新行D最久新数据载入时直接淘汰行D。实际中并不会真的记录一个复杂的时间戳而是通过“LRU状态位”记录组内各行的相对访问顺序。例如2路组相联仅需1个LRU位0表示最新未访问行1最久。4路组相联需2个LRU位通过二进制编码表示4行的相对顺序如00表示行0最新11表示行3最久。数字越小越新数组越大越长时间没有被访问应该最先被替换。当有空闲、未命中时。直接在该组随机位置插入并且更新自己的时间戳为0其余全部1当命中时更新自己的时间戳为0其余全部1。当没有空闲、未命中时会找到最大的一个数把该行替换出去同时让新进来的行置为0其余全部1。不过值得注意的是LRU分为全局LRU和组内LRU。其中组内LRU使用在组相联映射中而全局LRU使用在全相联映射中。而现代计算机多采用LRU的变式PLRU---本质是使用二叉树简化原本的算法对于硬件需求、算法延迟更低。