高速缓存与局部性

    由于CPU寄存器和主存(DRAM)访问速度的巨大差距，硬件厂商们逐渐开始在两者之间插入SRAM高速缓存，也就是我们常听到的L1缓存，或者size更大一点的L2、L3,于是，本文主要描述这种Lx(x=1,2..)缓存的原理。

    高速缓存的英文是cache，台湾人直接将其音译成快取，本人认为无论是从用途还是工作原理，这么解读都是恰到好处的：假设CPU需要通过一个32位的地址读取一个字节进行计算，那就要从L1去快取一下看这个地址是否在里面，详细如下

介绍结构：

地址：

1. 把32位地址分为低9位，中4位，高20位

L1缓存：

1. 把L1分成2^4=16组，每组大小相等，目的是根据32地址的中4位恰好可以索引到其中一组
2. 这里为了简便，假设每组只有一行，那L1缓存实质就是16行，每行的也可以分为3段，高的那段只有一位，叫有效位，判断该行是否存了数据，中间那段叫tag位，也是20位，如果索引位映射到这一行而且这一行的tag位跟32位地址的高20位相等，则标志着缓存命中，剩下的那段叫block，是高level的缓存向低level缓存fetch数据的最小单位，理论上讲，访问速度越慢、离CPU越远的缓存，block应越大，这里的大小为2^9=512字节，目的是32位地址的低9位能定位到每一个字节

对上面的描述做一个通用化，如图

其中t=20,s=4，b=9

其中S=16,B=512,E=1(即每个组只有一行),C=512×1×16=8192字节(即该L1缓存大小8k，这只是打个比方哈)

    那么，这样一个结构跟局部性又有什么关系呢

局部性：programs tend to reference data items that are near other recently referenced data items, or that were recently referenced themselves

    假设s取的是地址的高位而非中间位，就会出现这样一种情况，上图后分析

由于block是缓存间加载的最小单位，因此我们只看地址的高位和中间位

    上述cache被分为四组，地址被分为高二位和中二位，如果s取得是高位，第一批四个block被映射到第一组cache，第二批被映射到第二组，等等，有同学可能会问，cache的确能“存下”四个block呀，没错，数字是对的，但是真正存下的、遵循局部性原理的block只有一个：按上述方式存下的4个block的数组根本不连续，各自为战，其实只发挥了一个block的功能，严重违反了局部性;而如果s取得是中间位，第一批4个block会分别映射到第1、2、3、4组cache上去，这样的cache不仅存下了4组block，而且4组地址的连续的，充分发挥了高速缓存的作用;

所以说，高速缓存这种取中间位作为索引位的结构有助于充分发挥程序的局部性，同时，程序员也应该遵循局部性原理进行编程

    近些年出来的core i3 i7逐渐增加了L2,L3缓存，玩法就变成这样了：当L1上的tag位跟地址的tag位匹配不上时，就去L2上找block，L2比L1更便宜，因此size可以设计得更大，可以存放的block也更多，命中的概率也大一些，详细的步骤就不介绍了，请各位找相关资料了解，总之增加多级别Lx（x=1,2,3..）缓存最终看到的效果就是：越冷的数据会存在x较大的缓存中，频繁使用的数据就会存在于x较小的缓存中，而数据能否得到频繁使用的关键就是：局部性