CPU Cache

CPU Cache

缓存在现代计算机系统中有很大的作用。无论是CPU内的L1,L2,L3缓存,还是TLB缓存,还是内存上的对于一些应用数据的缓存。可以说缓存无处不在,CPU内的缓存可以让在运行的时候不需要多次去内存中取数据。那么为什么缓存能够为计算机系统带来这么大的好处呢?

归根到底就是,因为局部性(locality):

  1. 时间上的局部性

    时间上的局部性就是,一个数据对象的第一次被使用后,可能接下来多次都会被使用,所以将这个数据缓存到CPU内部的缓存,那么就不需要频繁的访问主存。如以下代码:

    int sum = 0;
    for (int i = 0; i < 100; i++) 
       sum += i;

    明显sum在时间上具有局部性,因为累加求和多次需要sum。

  2. 空间上的局部性

    空间上的局部性是值,如果我们访问了某个数据,那么将来可能它附近的数据也会被访问。比如说一个内存中的数组,我们对数组做一个累加求和的过程。那么讲数组整个加载到CPU缓存中,显然是很好的。

对于应用程序来说,将数据缓存在内存中,那么避免了磁盘IO的慢速,磁盘需要经过寻道,数据传输等操作,时间上开销很大,下面是常见的访问缓存所需要的CPU周期时间:

本文的目的就是讲一下CPU cache内部是如何组织缓存的,TLB是如何组织缓存的。

缓存的组织形式

一个通用的缓存组织形式如下这样的:

缓存组织结构

对于任意的缓存大小C字节,我们将其分为有S个组,每一个组内又将数据分为E个行,每一行中有B个字节的数据。有些抽象,那么举一个具体的例子。比如说有16MB大小的缓存,我们将他分为4个组,那么每个组就是4MB大小,然后每个组分为10行。那么每一行就是可以存放400KB的数据。有效位表示的是,该缓存行是否有效的。

缓存是这样组织的,那么对应的地址要翻译为缓存中的数据,那么就是根据地址来映射到缓存中的数据。下面是一个地址:

将地址划分为了三个部分,分别是Tag,Set Index,Block offset。

  1. Set index

    组索引,缓存是分组的,所以地址中的部分bit用于索引对应的组。

  2. Block offset

    缓存行能存的数据往往是比较大的,比如说一个缓存行可能是128字节的。但是CPU又是按字节寻址的,所以低位的偏移量就是用于在缓存行内寻找到对应的数据的。

  3. Tag

    标记就是类似一种名称,我们用组索引找到组之后,用标记位来遍历组中的每一行,只有标记位和地址中的tag相等且缓存行的valid位有效才算缓存命中

直接映射高速缓存

名字听着挺唬人,其实很简单。就是每一个组只有一个缓存行。下面简要的概括下CPU和缓存的交互过程。假设CPU此时要从地址A中读取一个字w,流程如下:

  1. 首先先从L1 cache中请求这个w,如果命中了,直接返回w
  2. 如果没有命中,那么L1 cache就向内存申请包含着w的内存块
  3. 当包含着w的内存块到达L1 cache的时候,L1 cache从这个内存中将w抽取出来
  4. 然后返回给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,那么什么时候将它更新到内存中呢?简单的来说,有两种思路。

  1. 直写(write-through)

    直写的意思就是,更新了缓存,那么立刻就更新内存中的数据。简单明了,不过它的缺点就是可能会给总线带来比较大的流量。而且,设想一下,在累加的程序中,我们只要保证计算完了之后再写入,明显有较好的效率。

  2. 写回(write-back)

    另一种策略就是,尽可能地推迟更新当要替换这个块的时候,才将数据刷到内存中。这种方法能够显著的降低总线流量,那么额外的开销就是,我们需要设置一个脏位(dirty bit)来表示他已经被修改过了。

上面关注的是,写入命中的情况,那么在写入不命中的时候呢?这里也有两种策略。

  1. 写分配(write-allocate)

    如果在写入不命中的时候,那么将数据加载到缓存。然后再更新缓存。这种策略的出发点是局部性,因为我们可能在将来还要继续更新这个变量。缺点就是每次未命中都需要导致一个内存块从内存中传到缓存。

  2. 非写分配(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的页):

  1. 用高10bit来从页目录(page directory)中找到页表(page table)的物理地址。
  2. 用中间10bit从页表中找到物理页的地址。
  3. 将低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,看过后有些东西都忘了,就写一篇来记录下。

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇