柚木

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地址和物理地址的对应关系有很多种。我们先看两个极端的例子:

  • 直接映射(Direct Mapping)

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

图片来自HardwareSecrets

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

  • 全相联映射(Fully Associative Mapping)

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

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

  • n路组相联映射(n-ways Set-Associative mapping)

这里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。敬请期待。

Cache其他文章:

L1,L2,L3 Cache究竟在哪里?

Cache为什么有那么多级?为什么一级比一级大?是不是Cache越大越好?

欢迎大家关注本专栏和用微信扫描下方二维码加入微信公众号"UEFIBlog",在那里有最新的文章。同时欢迎大家给本专栏和公众号投稿!

用微信扫描二维码加入UEFIBlog公众号

参考资料:

[1]: How The Cache Memory Works