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，看过后有些东西都忘了，就写一篇来记录下。