Sherlock's blog

有容乃大，无欲则刚

0%

cache基础概念

发表于 更新于
本文是学习cache基础知识过程中的一个笔记。学习的材料是《深入理解计算机系统》和 ARMv8的编程指导手册。这个笔记会梳理cache相关的几个基础概念，比如，cache line， cache set， way，全相连cache，组相连cache，直接映射cache等等。其实 《深入理解计算机系统》这本书里讲的已经很清楚。这里会结合ARMv8手册做一个简单梳理。

cache的存在是为了弥补CPU和内存间性能的gap. 一般的，有数据cache，指令cache。按照
级别分，有L1 cache，L2 cache, L3 cache。下面讲的cache是一个广泛的cache概念，仅仅
用于梳理cache里的其他的基本概念。

Cache，比如L1 data cache, 可以被细分为cache set，中文叫cache组。cache中的每个
cache组大小相等, 每个cache组可以包含一定数目的cache line, 一个set里包含的cache
line的个数和cache way(中文翻译为“路”)的数值是一样的(后面会讲cache way这个概念)，
每个cache line 会包含一定byte, 比如一个cache line 32 byte, 64 byte 或者有可能是
128 byte. 下面是cache set，way, line的示意图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
     ---   +---+-----+-----------------------------------+   
      ^    | v | tag | cache line                        |  每个组的cache line
      |    +---+-----+-----------------------------------+  的个数也是这个cache
set   |    | v | tag | cache line                        |  way(路)的数目
      |    +---+-----+-----------------------------------+
      |    ...
      v    | v | tag | cache line                        |
     ---   +---+-----+-----------------------------------+

           +---+-----+-----------------------------------+
           | v | tag | cache line                        |
           +---+-----+-----------------------------------+
           | v | tag | cache line                        |
           +---+-----+-----------------------------------+
           ...
           | v | tag | cache line                        |
           +---+-----+-----------------------------------+

           ...     

           +---+-----+-----------------------------------+
           | v | tag | cache line                        |
           +---+-----+-----------------------------------+
           | v | tag | cache line                        |
           +---+-----+-----------------------------------+
           ...
           | v | tag | cache line                        |
           +---+-----+-----------------------------------+

           假设这里有S个set, 每个cache line包含B个bypt

基础概念介绍完了，我们看看一个特定内存地址是怎么被映射到cache中的。假设一个内存
地址有m位, 那么中间的s位用来对应set的编号，指定去哪个set中找cache, 其中 2^s = S.
低b bit对应cache line中bypt的偏移, 其中 2^b = B。高 m-s-b bit 就是上面的tag域段。

1
2
3
4
  tag(m-s-b)       index(s bit)        offset(b bit)
|            |                      |                |
|<---------->|<-------------------->|<-------------->|
|            |                      |                |

去找一个内存地址对应的cache时，首先根据index域的值, 找到相应的cache set。然后
根据内存地址tag域的值和cache里tag的值匹配，找到相应的cache line。至于怎么找到
匹配的cache line, 以及找不到匹配的cache line的时候的cache line替换策略, 本文将
不去涉及, 这个主题涉及的范围远超过本文的内容。找到对应的cache line后, 再根据
offset的值找到对应的byte。

有了上述的铺垫，现在可以讲清全相连cache，组相连cache，直接映射cache这几个概念了。
直接映射cache就是只有一个set的cache; 全相连cache就是一个set里只有一个cache line
的cache; 组相连cache就是一个set里有多个cache line的cache。

在ARMv8的编程指导手册cache的章节有如下的示意图。我们现在把上面的概念和下面ARMv8
手册上的示意图联系到一起。下图里，每一行(连同它的背影里的行)组成一个cache set。
所以，下面的图里有几个立体的行，就是有多少个set。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
      --- +----------------------------------------------+
       ^  |                                              |
       |  |                                              |
       |  |                                              |
       |  |                                              |
       |  |      +----------------------------------------------+
       |  |      |                                              |
       |  |      |   +----------------------------------------------+
       |  |      |   |                                              |
       |  |      |   |   +---+-----+-----------------------------------+  ---
       |  |      |   |   | v | tag | cache line                        |   ^
       |  |      |   |   +---+-----+-----------------------------------+   |
       |  |      |   |   | v | tag | cache line                        |   |
       |  |      |   |   +---+-----+-----------------------------------+   |
       |  |      |   |   | v | tag | cache line                        |   |
       v  |      |   |   +---+-----+-----------------------------------+   |  每一行是一个set，
     ---> +------|   |   | v | tag | cache line                        |   |  一共有S行
        \  .     |   |   +---+-----+-----------------------------------+   |
         \  .    |   |   | v | tag | cache line                        |   |
          \  .   |   |   +---+-----+-----------------------------------+   |
           \     |   |   ...                                               |
=> one      \    +---|   | v | tag | cache line                        |   |
   set       \       |   +---+-----+-----------------------------------+   |
              \     -+---| v | tag | cache line                        |   |
               \         +---+-----+-----------------------------------+   |
                \        | v | tag | cache line                        |   v
               ---->     +---+-----+-----------------------------------+  ---

下面再对全相连cache，组相连cache，直接映射cache做下解释。直接映射的cache只有一个
cache set, 所以每次去cache里找一个地址对应的cache都要遍历整个cache。这样，cache
小还可以，cache大了，效率会很差。直接映射cache的最直接的应用是TLB，TLB是MMU页表
的cache(缓存)。一般的DDR的cache都是组相连cache，全相连cache有cache颠簸的潜在性能
影响, 画个具体的图比较容易明白:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
   +------------+              +------------+
A  | ddr        |  --------->  | cache line |  全相连cache，一个set一个cache line
   +------------+         /    +------------+
   | ddr        |  ------/-->  | cache line |
   +------------+       / /    +------------+
   | ddr        |  ----/-/-->  | cache line |
   +------------+     / / /    +------------+
   | ddr        |  --/-/-/-->  | cache line |
   +------------+   / / / /    +------------+
B  | ddr        |  / / / /
   +------------+   / / /
   | ddr        |  / / /
   +------------+   / /
   | ddr        |  / /
   +------------+   /
   | ddr        |  /
   +------------+
   ...

上面的内存块都以是cache line粒度的。可以看到B地址对应的cache line和A地址对应的
cache line是相同的。当对A地址引用后，再对B地址引用，由于cache line中还是A地址
对应的内容，那么对B地址的引用必然会引起cache替换。所以如果有这样的程序，那么性能
将会很差:

1
2
3
4
for (i = 0; i < NUM; i++) {
	tmp = *(A + i) * *(B + i);
	value += tmp;
}

组相连cache因为一个set里有多个cache line, 还可以在set这一维度引入很多处理算法，
减少cache颠簸的发生。

最后以一个具体的cache的示例结束这篇笔记，一个32K 一个cache line 32 byte 4路组相连
cache的示意图: 先计算地址里s, b的数值，2 ^ b = 32, b = 5; S = 32K / (32 * 4) =
256, 2 ^ s = S, s = 8。所以一个内存地址的划分是:

1
2
3
|bit 31 ~ bit 13                        |bit 12 ~ bit 5 |bit 4 ~  bit 0|
+---------------------------------------+---------------+--------------+
|       tag                             |   index       |   offset     |

这个具体的cache有256个组，各个组4路。