CPU Cache
缓存在现代计算机系统中有很大的作用。无论是CPU内的L1,L2,L3缓存,还是TLB缓存,还是内存上的对于一些应用数据的缓存。可以说缓存无处不在,CPU内的缓存可以让在运行的时候不需要多次去内存中取数据。那么为什么缓存能够为计算机系统带来这么大的好处呢?
归根到底就是,因为局部性(locality):
时间上的局部性
时间上的局部性就是,一个数据对象的第一次被使用后,可能接下来多次都会被使用,所以将这个数据缓存到CPU内部的缓存,那么就不需要频繁的访问主存。如以下代码:
int sum = 0; for (int i = 0; i < 100; i++) sum += i;
明显sum在时间上具有局部性,因为累加求和多次需要sum。
空间上的局部性
空间上的局部性是值,如果我们访问了某个数据,那么将来可能它附近的数据也会被访问。比如说一个内存中的数组,我们对数组做一个累加求和的过程。那么讲数组整个加载到CPU缓存中,显然是很好的。
对于应用程序来说,将数据缓存在内存中,那么避免了磁盘IO的慢速,磁盘需要经过寻道,数据传输等操作,时间上开销很大,下面是常见的访问缓存所需要的CPU周期时间:
本文的目的就是讲一下CPU cache内部是如何组织缓存的,TLB是如何组织缓存的。
缓存的组织形式
一个通用的缓存组织形式如下这样的:
对于任意的缓存大小C字节,我们将其分为有S个组,每一个组内又将数据分为E个行,每一行中有B个字节的数据。有些抽象,那么举一个具体的例子。比如说有16MB大小的缓存,我们将他分为4个组,那么每个组就是4MB大小,然后每个组分为10行。那么每一行就是可以存放400KB的数据。有效位表示的是,该缓存行是否有效的。
缓存是这样组织的,那么对应的地址要翻译为缓存中的数据,那么就是根据地址来映射到缓存中的数据。下面是一个地址:
将地址划分为了三个部分,分别是Tag,Set Index,Block offset。
Set index
组索引,缓存是分组的,所以地址中的部分bit用于索引对应的组。
Block offset
缓存行能存的数据往往是比较大的,比如说一个缓存行可能是128字节的。但是CPU又是按字节寻址的,所以低位的偏移量就是用于在缓存行内寻找到对应的数据的。
Tag
标记就是类似一种名称,我们用组索引找到组之后,用标记位来遍历组中的每一行,只有标记位和地址中的tag相等且缓存行的valid位有效才算缓存命中。
直接映射高速缓存
名字听着挺唬人,其实很简单。就是每一个组只有一个缓存行。下面简要的概括下CPU和缓存的交互过程。假设CPU此时要从地址A中读取一个字w,流程如下:
- 首先先从L1 cache中请求这个w,如果命中了,直接返回w
- 如果没有命中,那么L1 cache就向内存申请包含着w的内存块。
- 当包含着w的内存块到达L1 cache的时候,L1 cache从这个内存中将w抽取出来
- 然后返回给CPU
PS:之所以是取包含着w的内存块,我猜可能是和内存对齐有关。因为CPU在取数据的时候一次性取多个字节的,所以并不一定只是取字w到缓存。
下面是取数据的具体流程:
选择对应的组:
假设此时我们给出的组索引时1,那么自然选择第一个组。
选择对应的行:
组选择好了以后,我们去查看行里面的tag是否和地址中的tag位相符。注意选择行的时候第一步就是要判断valid位是否被置位。如果行也是对的,那么接下来就是由地位bits来索引对应的字节。上图中,100就表示从缓存中的第四字节开始取数据。
未命中的情况:
如果缓存没有命中,因为tag的不匹配。那么就需要从内存中或者是,L2 cahe,L3 cache甚至是内存中获得对应的缓存数据。新的数据读进来之后,那么替换就是一个问题,对于直接映射高速缓存来说(只有一行),直接替换即可。
为什么用中间的位来作为索引
观察上面的地址,可以发现使用的是地址的中间bits作为组索引,为什么呢?
还是因为局部性。如下图中,我们以中间bits作为组索引的话,那么相邻的内存块会被映射到不同的组当中。如果以高位bits作为组索引。那么会导致连续的内存块都映射到同一个组当中,会造成频繁的缓存替换。如果一个程序具有良好的空间局部性,那么显然以中间位作为索引是更好的。
组相联高速缓存
又是一个听着挺唬人的东西,实际上就是每个组包含了更多的缓存行。总体来讲,在组相联高速缓冲中,获取缓存数据和之前没有太大的差别。也是分为:选择组,行匹配,加上offset,然后获得对应的数据。
稍微有些不同的是,此时每一个组包含更多的缓存行,所以在缓存未命中的时候,哪个行被替换就成为了问题。通常来说,由LRU,LFU等策略。LRU说的是最久未使用的替换出去,LFU说的是过去一段时间内使用次数最少的被替换出去。
因为一个组当中有多个缓存行,所以我们要根据遍历当前组的所有行,直到遇到Tag相匹配的才行。
So the cache must search each line in the set for a valid line whose tag matches the tag in the address. -- CSAPP
全相联高速缓存
在这种情况下,只有一个组。因此地址中的Set index已经没有用了。地址总共分为两个部分:Tag和Block Offset
全相联高速缓存的好处就是:不再需要进行组的索引,效率上可能稍有提升。那么另外一个问题就是,如果缓存内行过多,遍历所有的行可能开销较大。因此全相联的高速缓存只能用于较小的高速缓存,例子就是TLB。
有关写的问题
到目前为止呢,我们都是关注,缓存的读问题,就是缓存的命中与不命中问题。写的情况就复杂一些了,如果我们写入的时候先写入了缓存中的副本w,那么什么时候将它更新到内存中呢?简单的来说,有两种思路。
直写(write-through)
直写的意思就是,更新了缓存,那么立刻就更新内存中的数据。简单明了,不过它的缺点就是可能会给总线带来比较大的流量。而且,设想一下,在累加的程序中,我们只要保证计算完了之后再写入,明显有较好的效率。
写回(write-back)
另一种策略就是,尽可能地推迟更新,当要替换这个块的时候,才将数据刷到内存中。这种方法能够显著的降低总线流量,那么额外的开销就是,我们需要设置一个脏位(dirty bit)来表示他已经被修改过了。
上面关注的是,写入命中的情况,那么在写入不命中的时候呢?这里也有两种策略。
写分配(write-allocate)
如果在写入不命中的时候,那么将数据加载到缓存。然后再更新缓存。这种策略的出发点是局部性,因为我们可能在将来还要继续更新这个变量。缺点就是每次未命中都需要导致一个内存块从内存中传到缓存。
非写分配(not-write-allocate)
这种策略就是,如果发生未命中,那么直接将数据写入到内存中,绕开读入缓存这一步
真实的缓存结构
下面就是引用下书中的例子,帮助一下加深记忆。要知道,L1 Cache,L2 Cache是各个CPU独有的。进一步地,L1 Cache又分为L1 Data Cache和L2 Instruction Cache。而L3 cache是所有的CPU共享的,因此它的容量通常也比较大。
他们的容量以及块的大小如下:
TLB
TLB(Translation Lookaside Buffer)可以说是页式内存中比较重要的一环了。它位于CPU的MMU(memory management unit)中,提供了虚拟页到物理页之间的映射缓存。在页式内存中,将虚拟地址转为物理地址,需要经过如下步骤(假设在32bit的地址空间中,4kb的页):
- 用高10bit来从页目录(page directory)中找到页表(page table)的物理地址。
- 用中间10bit从页表中找到物理页的地址。
- 将低12bit和物理页地址加起来得到真正的物理地址。
PS:实际上得到的并不是真的是物理地址,因为这些页表项的低位bit还有一些flag信息。因此还需要低位取0才是真的物理地址。
可以看到,如果可以直到物理页地址,那么地址翻译的过程会显著变快。这就是TLB的用处,在前文中说过了CPU内部的缓存组织方式,接下来看下TLB是怎么样的。
TLB通常具有较高的相联度,也就是说它的组比较少,组内的缓存行比较多。
虚拟地址的高20位是虚拟页的页号,低12位是偏移。将虚拟页号进一步拆开为Tag和TLB index,和之前的缓存组织方式类似。
TLB的缓存块大小通常是比较小的,因为每一个块的大小主要的存储信息就是物理页PTE(page table entry)的信息。下面引用书上的一个例子,来解释TLB和地址翻译组合在一起的情形。
A TLB is a small, virtually addressed cache where each line holds a block consisting of a single PTE
注意,下文中页的大小是64字节!!!。
TLB内容如下,4组,每组4缓存行。
需要翻译的地址为0x3d4,虚拟页号为0x0f,将其拆为组索引(TLBI)和Tag(TLBT),放到上图中。我们就找到了0x3d4所属的物理页的页号是0x0d。:
知道物理页号之后,0x0d << 6 == 0x340+0x14 == 0x354,所以得到了最终地址0x354:
最后呢,得到物理地址之后,我们还要去看地址要访问的数据是否在缓存中等操作。
TLB命中与未命中
再附上两幅图来表示TLB命中和不命中的情形。如果TLB命中了,那么直接获得页号然后和offset结合起来,由MMU产生物理地址,接着再去缓存或者内存中获取需要的数据。
那么在TLB未命中的情况下,那么就需要从L1 Cache中获得所对应的页物理地址,接着再将PTE放到TLB中,再重新从TLB中获得PTE,然后翻译为物理地址。
Summary
粗略的对缓存的结构以及TLB做了简要的介绍,本文的大部分内容都是参考自caspp,看过后有些东西都忘了,就写一篇来记录下。