Cache映射计算

在刷题时经常会遇到 Cache 与主存相关的计算题很长一段时间没看教材具体概念记得不那么清楚了算起来总是概念一大堆分不清谁是谁。网上有很多优秀的文章讲清楚了 Cache 是怎么工作的也通俗解释了三种映射方式但文章看多了反而更乱。这篇文章让我们回到 Cache 计算的主线上来把思路理清楚。Cache映射计算到底在计算啥所有题目的计算基本都是围绕 Cache 工作中最核心的一件事展开把主存中的内容搬运到Cache里供CPU使用。但是当CPU需要使用某一段数据时用的是主存地址去查找。也就是说CPU并不会刻意去用一个类似 “Cache 地址” 的东西找数据而是通过硬件电路把主存地址转换成 Cache 存储器里的地址。这段电路的实现方法就是我们最熟悉的三种映射方式直接映射、全相联映射和组相联映射。需要特别注意Cache 和主存之间数据的搬运是按“块”进行的也就是 Cache 和主存都会被划分成大小相同的若干块。各类映像方法中主存与Cache的关系现在我们假设CPU给出一个主存地址0x1234E8F8来看看在不同的映像关系下如何解读。直接映像在直接映像当中其实就是先算出或者题目直接给了Cache大小为多少块然后主存按照滚动标记的方法标记所有的块。现在假设Cache大小为3块主存有6块那么主存块计算标记号对应Cache块00 % 3 0011 % 3 1122 % 3 2233 % 3 0044 % 3 1155 % 3 22可以看出实际的主存块对应Cache块的计算公式就是主存块号 % Cache块数回到开头给出的主存地址0x1234E8F8在直接映像的规则下我们假设Cache共有1024块块大小为16B容量16KB。现在开始推导主存地址的转换首选块内的数据需要进行标记也就是块内偏移我们按照字节编址也就是需要块大小 16B \(2^4\)B→ 共4位用来表示一个数据在块内的哪个位置。接下来是块号的确认现在已知主存地址需要求得该地址在主存中的块号也就是主存块号 主存地址 ÷ 块大小16 B 0x1234E8F8 ÷ 16。除法在二进制下就是右移 4 位丢掉块内偏移。现在我们得到了主存块号就可以套用上面的公式即主存块号 % Cache块数 0x1234E8F ÷ 1024。1024 2^10在二进制里模2^10就等于只保留这个数的低 10 位。由此我们得到了该地址对应的Cache 块号。现在我们可以完整的解读出主存地址32位高位TagCache 块号索引低位块内偏移18 位10 位4 位块内偏移块大小 16B (2^4)B → 占低 4 位Cache 块号索引Cache 共 1024 (2^{10}) 块 → 占中间 10 位Tag剩余高位 32 - 10 - 4 18 位具体计算过程将0x1234E8F8转为 32 位二进制0001 0010 0011 0100 1110 1000 1111 1000从低位开始取块内偏移低4位1000索引中间10位位4~13即1010001111从⑥⑦⑧取出的具体值装入 Cache 的地址 索引 块内偏移1010001111 100014位二进制结论直接映像时CPU只需取地址中间 10 位找到 Cache 块号再用低 4 位定位块内字节高位 Tag 用于比较确认是否命中。全相联映像与直接映像完全不同全相联映像的核心思想是主存中的任意一块可以放入 Cache 中的任意一块没有任何固定位置的限制。因此主存地址中不再需要“索引”字段来指定 Cache 块号而是把全部高位都当作标记Tag依靠硬件并行搜索来定位数据。还是用同一个例子Cache 共 1024 块块大小 16B主存地址0x1234E8F8。1. 主存地址的划分在全相联映像下主存地址只被切成两部分高位Tag / 主存块号低位块内偏移28 位4 位块内偏移与直接映像一致块大小 16B → 占低 4 位。Tag剩余的全部高位。总地址 32 位减去偏移 4 位得到 28 位。这 28 位的作用是唯一标识一个主存块因为主存总块数 2^28 块远远超出实际主存容量余下高位在实际中会按主存大小截断但地址线保留这些位用于比较。对比直接映像直接映像将中间 10 位用作索引Tag 仅 18 位全相联则取消了索引把索引位也合并进了 Tag使 Tag 变成了 28 位。这就是为什么全相联的标记位数通常更长。2. 如何找到对应的 Cache 块由于地址里不包含任何 Cache 位置信息硬件必须进行“按内容查找”将主存地址中的28 位 Tag同时与 Cache 内所有 1024 个块的标记字段进行比较。同时检查该块的有效位是否为 1。如果某一个块的标记匹配且有效即为命中该块的物理编号 k01023就是目标 Cache 块号。若全部不匹配则发生缺失需要从主存调入该块并放入某个 Cache 块由替换算法决定如 LRU。3. 装入 Cache 的地址命中后CPU 访问 Cache 的地址由两部分组成Cache 块号由匹配电路给出的 k10 位二进制因为 1024 块需要 10 位来表示。块内偏移直接取自原主存地址的低 4 位。因此Cache 地址 {k, 块内偏移}共 10 4 14 位。以0x1234E8F8为例低 4 位块内偏移1000高 28 位 Tag0001 0010 0011 0100 1110 1000 1111即原地址去掉低 4 位硬件将这 28 位 Tag 与所有 1024 个 Cache 块的标记并行比较假设备替换后该块被放入第 513 号 Cache 块二进制1000000001则最终 Cache 地址为1000000001 1000。注意这个 513 号块是从匹配结果中得到的而不是从主存地址中“算出来”的这正是全相联与直接映像最本质的区别。组相联映像组相联映像是直接映像和全相联映像的折中方案Cache 被分成若干组每组内包含若干个块如 4 块/组称为 4 路组相联。主存块先通过取模运算固定映射到某一组类似直接映像但到了该组之后可以放进组内的任意一块类似全相联。这样既避免了直接映像的高冲突又不像全相联那样需要在整个 Cache 中并行搜索。沿用前面的例子Cache 共 1024 块块大小 16B并采用4 路组相联。则组数 1024 ÷ 4 256 组。组内可任意存放组间则是固定的模运算映射。主存地址划分主存地址0x1234E8F832 位被划分为三个字段高位Tag组索引Set Index低位块内偏移20 位8 位4 位块内偏移4 位块大小 16B组索引256 组 → (\log_2 256 8) 位Tag剩余 32 - 8 - 4 20 位映射公式主存块号 主存地址 ÷ 16右移 4 位所在组号 主存块号 % 组数0x1234E8Fmod 256因为 256 (2^8)模运算直接保留主存块号的低 8 位。这 8 位恰好就是地址中紧接着块内偏移的中间 8 位即组索引。具体数值提取将0x1234E8F8展开为二进制0001 0010 0011 0100 1110 1000 1111 1000块内偏移低 4 位1000组索引紧接着的 8 位位 4~111000 1111即0x8F第 143 组Tag高 20 位0001 0010 0011 0100 1110即0x1234E如何找到 Cache 块硬件直接提取地址中的8 位组索引定位到 Cache 的第 143 号组。将该组的4 个块的标记字段与地址中的20 位 Tag同时进行并行比较类似全相联但只比较 4 个块。若某个块的标记匹配且有效位为 1则命中。该块在这一组内的序号0~3即为组内块号。若全不匹配则发生缺失需从主存调入并按替换算法如 LRU选择该组内一个块来存放新数据。装入 Cache 的地址命中后实际的 Cache 地址仍由Cache 块号 块内偏移构成共 14 位。Cache 块号 组号 × 每组块数 组内块号 0x8F × 4 组内块号例如假设该主存块被放在了第 143 组内的第 1 个块组内块号1则 Cache 块号 (143 \times 4 1 573)二进制1000111101。块内偏移不变仍为1000。所以最终 Cache 地址 1000111101 1000。关键要点主存地址中的组索引决定了去哪个组找与直接映像的索引类似但位数由组数决定不再直接对应唯一的 Cache 块。组内搜索得到组内块号再与组号组合才得到最终的 Cache 块号。这种设计用较少的并行比较器仅比较组内几块获得了接近全相联的灵活性是实际处理器中最常见的 Cache 映射方式。