Cache是怎么组织和工作的？

我的习惯是想到哪里，写到哪里，只管挖坑不管填，近期更是工作繁忙，没有更新Cache部分的内容，实在抱歉。承蒙很多朋友催稿，由此可见Cache的关注度还是不错的，今天带来Cache的第二篇内容。

我们经常能够看到2-ways，4-ways cache，它是什么意思呢？Cache和内存地址是怎么对应起来的呢？今天我们就介绍这个内容。

在CPU中， Cache Memory 处于 Memory Hierarchy 的最顶端，其下是内存和外存。

那么CPU是如何访问Cache的呢？和访问内存类似，CPU微架构也对各级Cache地址空间进行了编码，只是这些编码并不能够被软件所体察。为简化起见，我们忽略各级Cache的区别，仅仅讨论一般意义上Cache的访问。

Cache的组成和访问方式

在现代大多数处理器中，Cache被分为很多行（Cache Line），Cache Line大小不一，从16Byte到128Byte不等，一般大小是64个Byte，我们在这之后都认为Cache Line有64B组成。我们假设有512KB的Cache，就可以划分成8192个Cache Line

那么一个地址访问如何映射到Cache中去呢？我们都知道地址分为逻辑地址（虚拟地址）、线性地址和物理地址。一个虚拟地址变换成物理地址的简单过程如下图，我就不详细说明了：

变换过程中线性地址到物理地址需要用到页表（page table）。页表由很多项组成，每一项叫一个页表项，整个页表由操作系统维护，并放置在内存中（或磁盘中）。从上文（L1，L2，L3 Cache究竟在哪里？）我们知道，一次内存访问需要数百个时钟周期，如果每次地址转换都要查看内存页表也太浪费时间了。现代计算机为了加速这一过程，引入了翻译后援缓冲器TLB。TLB可以看作页表的Cache，CPU每次转换地址都会查看TLB，如果有了就不用去取内存页表了。

那么TLB和Cache有什么关系呢？可以说TLB命中是Cache命中的基本条件。TLB不命中，会更新TLB项，这个代价非常大，Cache命中的好处基本都没有了。在TLB命中的情况下，物理地址才能够被选出，Cache的命中与否才能够达成。如下图：

n-ways Set-Associative Cache

从前文可以看出知道物理地址，那就能够知道Cache命中与否。那么Cache地址和物理地址的对应关系有很多种。我们先看两个极端的例子：

直接映射可以理解为每个地址都可以立刻直接且只能映射到某个Cache Line上。还是举前面那个512KB Cache的例子。假设我们有1GB物理内存，我们把它们分成8192份，每份就是128KB。则我们的直接映射Cache算法就是每个128KB块里面所有的地址都只能映射到相应的Cache Line中。我们判断Cache命中的算法就很简单，直接地址/128KB，商就是Cache Line的地址，如果里面的确是该地址就命中，否则就不明中，简单高效，运算十分迅速。意义图如下：

图片来自HardwareSecrets

这样做看起来很高效，哪有那些坏处呢？那就是Cache Miss率极高，因为数据的相关性和局限性，同一时刻需要用的数据大部分都在附近，会造成Cache频繁换进换出，造成颠簸。一个改进的做法是用inteleave，但也会造成Cache Miss很大，冷热不均。

2

全映射就是所有Cache Line可以对应说有地址。这样Cache就不会造成冷热不均，Cache Miss减小了很多，但与此同时带来了另外的问题，那就是查找Cache命中与否的代价(Over head)很高。一条不命中的寻找，要遍历整个Cache，才能最终确定下来。

直接映射在Cache刚刚发明时大行其道，但随着Cache的发展，它的问题也被暴露了出来，于此同时全相连也不是很好的解决办法。人们退而求其次，在两个极端方法直接寻找平衡，提出了n路组相联映射(n-ways Set-Associative mapping)：

3

这里n路，是指将Cache分成n个组（set），每一组对应一个地址。也就是说一个地址可以映射到n个Cache Line中。我们举个4 ways的例子。我们先把Cache每4个分成一组：

同样的1GB内存也做出调整：

图片来自HardwareSecrets

可以看出和直接映射很像，不同点在于一个在一组中，第一个没找到，可以找下一个，直到该组的最后一个。这样，可以结合两者的优点。

现实的选择

n-ways Set-Associative，这个n=1，就是直接映射；n=cache大小，就是全相关映射。我们从上面知道两者都不好，而n最好取中间某个值。那么n到底该选几呢？这比较复杂，和Cache的速度和大小、内存的速度、主频等等很多都相关，在很多情况下都是个经验值，也是大量pre-silicon实验的结果。

我们来看看现实生活中L1，L2和L3都是几路相连映射：

AMD

Intel

从中我们可以看出各级Cache选择几路都不一样，而且不同代际之间也会微调。Intel都是2的幂，而AMD则会有3路之类的奇葩路数。

下一篇将介绍Cache的大小对性能有什么影响，为什么不能做出Cache奇大的CPU。敬请期待。

参考资料：

[1]: How The Cache Memory Works