系统加速利器Hardware Cache（一）——三种类型的Cache

Hardware cache的目的

Hardware Cache的是为系统加速而生的，这个是众所周知的事情。不过为了本文内容的完整性，我在此还是先将hardware cache的功能讲一下，不过我会尽量简短一点。

cpu访问hardware cache的速度要远高于访问主内存的速度，为了加快系统运行速度，会将主内存的部分数据放在hardware cache中，这样cpu就不必每次都访问主内存，如果要访问的数据在cache中命中，则直接从cache中读数据或者直接修改cache中的数据即可，从而加快了系统运行速度。至于由于hardware cache的引入，出现的多master环境下内存不一致问题，我们在后面的章节讨论。

这里有两个问题要特别注意：

第一，hardware cache由于比较昂贵，所以一般容量较小，而主内存一般容量很大，所以主内存中的数据不可能全部放在hardware cache中，所以cache中的内容在必要的时候会同步到内存，以便能装入新的内容。

第二，hardware的操作单位是cache line，cache line的长度由芯片设计而定，本文我们以32B cache line分析。

三种类型的cache

我们以32K的cache容量，32B的cache line size来分析。32K的cache容量，每个cache line是32B，所以总共有1024个cache line。

直接映射的cache

直接映射的cache方案中，每个cache line所对应的物理内存都是固定的，映射关系如下：

主内存地址	Cache Line
0 - 31
32 - 63	1
64 - 95	2
96 - 127	3
……	……
32K-32 - 32K-1	1023
32k+0 - 32k+31
32k+32 - 32k+63	1
32k+64 - 32k+95	2
……	……

即主内存每连续32K分成一组，分别映射到cache line0-1024。这样主内存地址0-31和32k+0 - 32k+31都映射到cache line 0。

直接映射的cache line格式如下：

Tag（addr 15 - 31/63）+ Data(32B)
           

到cache这边的地址译码格式如下：

addr 15 - 31/63	addr 5 - 14	addr 0 - 4
tag	cache line 索引	在选定cache line内寻址

cache这边使用物理地址还是虚拟地址依据硬件设计而定，我们在此不加以讨论，统一称地址。

Cpu访问操作处理过程如下：

1. 根据地址的 bit5-14，索引到某个cache line。
2. 将地址的bit15-31/63与cache line的tag比较，如果一致，则cache命中，否则cache没有命中。
3. 如果cache命中，则根据地址的bit0-4在cache line内找到要访问的数据。
4. 如果cache没有命中，则访问主内存，同时可以选择将主内存中的数据按cache line对齐载入到对应的cache line中。

直接映射cache的好处是查找速度快，直接解析地址并索引就可以了。同时直接映射的cache line也有比较致命的问题，因为每个cache line映射到比较多的固定地址，比如cache line 0对应物理地址0-31以及32k+0 - 32k+31，如果本次访问地址0-31，则地址0-31的数据缓存到cache line0，下次访问地址32k+0 - 32k+31，则需要从主内存将数据载入cache line0，下次再访问地址0-31，又需要从主内存载入数据到cache line0，这种情况下，cache形同虚设，因为每次都会访问主内存。

全相联cache

全相联的cache，每一个主内存地址可以缓存到任意一个cache line。

cache line格式如下：

Tag（addr 5 - 31/63）+ Data(32B)
           

到cache这边的地址译码格式如下：

addr 5 - 31/63	addr 0 - 4
tag	在选定cache line内寻址

这里没有cache line索引大概念，依次比较地址的tag与cache line的tag，如果tag一致，则表明cache命中。

全相联的cache也很非常明显的确定，那就是查找速度慢，因为要依次比较cache line，最坏的情况下，需要比较1024次才能命中。

组相联cache

组相连cache结合了直接映射cache和全相联cache的特点，我们以8路组相连为例做说明。

每8个cache line为一组，1024个cache line共分成128组。每个组采用直接映射方案，而组内的8个cache line则使用全相联方案。映射方案如下：

主内存地址	Cache Line
0 - 31	可以缓存到第一组cache lines中的任意一条cache line中
32 - 63	可以缓存到第二组cache lines中的任意一条cache line中
64 - 95	可以缓存到第三组cache lines中的任意一条cache line中
……	……
4k-32 - 4k-1	可以缓存到第一组cache lines中的任意一条cache line中
4k-4k+31	可以缓存到第二组cache lines中的任意一条cache line中
……	……

cache line格式如下：

Tag（addr 12 - 31/63）+ Data(32B)
           

到cache这边的地址译码格式如下：

addr 12 - 31/63	addr 5 - 11	addr 0 - 4
tag	组索引	在选定cache line内寻址

Cpu访问处理过程如下：

1. 根据地址bit5-11索引组
2. 根据地址tag bit12-31/63与组内cache line的tag依次比较，如果有一致的，则命中。
3. 如果cache line命中，则根据地址bit0-4在cache line内找到要访问的数据。
4. 如果cache没有命中，则访问主内存，同时可以选择将主内存中的数据按cache line对齐载入组内任意一条空闲cache line中，如果没有空闲的cache line，则驱逐一个cache line。

组相联cache是直接映射和全相联折中的方案。跟直接映射cache相比，它的查询速度不够，但是cache冲突的概率大大降低；跟全相联cache相比，它的cache冲突的概率大一点，但是它的查询速度比较快。