Cache工作流程
Cache出现的目的是为了弥补CPU与内存之间速度不匹配的状况，如果要访问的内存地址的内容已经存在于Cache中，那么CPU就无需访问速度较慢的内存。本文通过一个内存访问的例子，简单介绍两种Cache模型，以及它们是如何工作的。
Cache Line
Cache的理论基础是程序的局部性原理，当访问了某个不在Cache中的内存地址后，通过将相关内存地址的数据迁移到Cache中，降低再次需要访问内存的概率。
从内存向Cache迁移数据是以Line Size为基础单位，假如Line Size是32Byte，那么每次迁移都是32Byte。
当给定一个内存地址时，我们怎样让其与Cache Line中的某个具体Byte对应呢？参照内存分页机制，不妨也将内存地址拆分为几组，这就引申出了Set，Tag和Offset三个概念。
整个Cache空间被分为若干个Set，每个Set包含若干个Cache Line，每个Cache Line用Tag标识，当找到对应的Cache Line后，使用Offset来确定在Cache Line中的偏移。
根据每个Set中Cache Line的数量，Cache可以分为直接映射、组相联和全相联三种。
Direct Mapped
在直接映射模式中，每个Set只有1个Cache Line，假设我们的Cache有128Byte，每个Cache Line有32Byte，内存地址是12bit（通常来说是32bit或者64bit，为简单起见使用12bit），那么
Offset = log(32) = 5bit，即使用5bit作为在Cache Line中的索引
Set = log(128/32/1) = log(4) = 2bit，其中1表示每个Set有1个Cache Line
Tag = 12 - 5 -2 = 5bit，剩下的bit用于标识Cache Line
即内存地址被分割为
| Addr | Tag | Set | Offset |
|---|---|---|---|
| 12bit | 5bit | 2bit | 5bit |
| 0x070 | 00000 | 11 | 10000 |
对应的Cache空间布局如下表所示
| Set | Valid | Tag (Line) |
|---|---|---|
| 00 | 0 | 0 |
| 01 | 0 | 0 |
| 10 | 0 | 0 |
| 11 | 0 | 0 |
当我们在访问内存时，首先把内存地址划分为Tag、Set和Offset，然后根据Set选择对应的组，如果Valid字段为1，并且Tag字段匹配，那么Cache命中，否则Cache未命中，需要把内存中1 Line的数据存储到对应的Cache Line。
假如我们有一组待访问的内存地址，那么第一次访问以及第二次访问的命中情况如下表所示。
| Addr | Tag | Set | Offset | 1st | 2nd |
|---|---|---|---|---|---|
| 0x070 | 00000 | 11 | 10000 | M | H |
| 0x080 | 00001 | 00 | 00000 | M | M |
| 0x068 | 00000 | 11 | 01000 | H | H |
| 0x190 | 00011 | 00 | 10000 | M | M |
| 0x084 | 00001 | 00 | 00100 | M | M |
| 0x178 | 00010 | 11 | 11000 | M | M |
| 0x08c | 00001 | 00 | 01100 | H | H |
| 0xf00 | 11110 | 00 | 00000 | M | M |
| 0x064 | 00000 | 11 | 00100 | M | M |
第一次访问Cache的命中率是：2/9 = 22%
第二次访问Cache的命中率是：2/9 = 33%
2-way Set Associative
在2路组相联模式中，每个Set有2个Cache Line，假设我们的Cache有128Byte，每个Cache Line有32Byte，内存地址是12bit（通常来说是32bit或者64bit，为简单起见使用12bit），那么
Offset = log(32) = 5bit，即使用5bit作为在Cache Line中的索引
Set = log(128/32/2) = log(2) = 1bit，其中2表示每个Set有2个Cache Line
Tag = 12 - 5 -1 = 6bit，剩下的bit用于标识Cache Line
即内存地址被分割为
| Addr | Tag | Set | Offset |
|---|---|---|---|
| 12bit | 6bit | 1bit | 6bit |
| 0x070 | 000001 | 1 | 10000 |
对应的Cache空间布局如下表所示
| Way 1 | Way 0 | ||||
|---|---|---|---|---|---|
| Set | LRU | Valid | Tag (Line) | Valid | Tag (Line) |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
注意，由于此时每个Set中有2个Cache Line，那么当Cache未命中时，应该替换哪一个Cache Line呢？这时候就有多种策略可以选择，比较常见的是LRU，即最近最少使用算法。比如我们刚更新过Line0，那么LRU就被设置为1，表示Line1将在下一次未命中发生时被替换。本意是将最不活跃的Line替换出去。
那么，使用同样一组数据，Cache命中情况如下表
| Addr | Tag | Set | Offset | 1st | 2nd |
|---|---|---|---|---|---|
| 0x070 | 000001 | 1 | 10000 | M | H |
| 0x080 | 000010 | 0 | 00000 | M | H |
| 0x068 | 000001 | 1 | 01000 | H | H |
| 0x190 | 000110 | 0 | 10000 | M | M |
| 0x084 | 000010 | 0 | 00100 | H | H |
| 0x178 | 000101 | 1 | 11000 | M | H |
| 0x08c | 000010 | 0 | 01100 | H | H |
| 0xf00 | 111100 | 0 | 00000 | M | M |
| 0x064 | 000001 | 1 | 00100 | H | H |
第一次访问Cache的命中率是：4/9 = 44%
第二次访问Cache的命中率是：7/9 = 77%
可以看出，在没有增大Cache空间的情况下，仅仅改变了Cache的模式，就大幅提高了命中率。
Fully Associative
在全相联模式下，只有1个Set，假设我们的Cache有128Byte，每个Cache Line有32Byte，那么这个Set中将包含4个Cache Line。
Way = 128/32 = 4
对于小空间的Cache来说，似乎不是什么问题，但是当Cache有几百KB甚至几MB，那么就会存在大量的Cache Line，这会造成两个问题
- 由于是通过比较Tag来确定对应的Cache Line，而不是使用索引，比较这么多Tag很低效
- LRU算法需要找到最长时间未被使用的Cache Line，而这一般是硬件完成的，如果Cache Line很多，硬件设计会变得很复杂
因此，几乎没有实际的硬件使用这种Cache模式。
总结
本文简单的介绍了一下Cache模型，以及其工作方式，虽然Cache对于程序员来说是透明，但了解其工作方式可以帮助我们更好的优化代码性能。如果想了解文中例子的具体执行流程，可以观看参考中的两个视频。