浅谈缓存

# Cache的基本理论指导

​ 由于计算机内部memery与 processor之间的速度差距过大,导致计算机整体速度降低,memery拖慢了速度。于是人们想出 了一个办法来解决他。缓存Cache诞生了。
​ Cache相对于Memery来说,速度快了很多,速度快意味着造价高,容量小,这是代价,我们没有那么多钱来用Cache来当作 Memery,于是我们尝试,让他作为Processor与Memery的中介。
​ 为什么要Cache,因为Memery太慢了,用Cache的话,容量问题很显然,Cache很小,没有Memery那么大。但是我们的初衷 是什么,用Cache去代替Memery,但是,Cache这个家伙小啊,我们不可能把一个大的东西放进一个小的盒子里面。 这是缓存 面临的最大问题。
​ 重新思考计算机的运转,指令是一条一条执行的,当计算机运转的时候,CPU关心的不是整个Memery,他只要他的东西,他所需要的 只是局部的信息。于是我们开始思考,既然Cache没有Memery那么大,那我们就构建一个一对多的映射,一个Cache地址,去对应 多个Memery地址,问题似乎解决了,是的Cache就是那样工作的。
​ 一对多的问题不好解决,你怎么知道一对多的时候,对应的是哪一个呢?我们是这样子解决的,把Memery的地址映射 Mx到Cache的地址Cx,这是唯一的,但是Cache是一对多啊,我们假设是一对四,然后我们在Cache的地址所指向的位置添 加一个标记,用来指示他目前对应是哪一个Memery地址,不妨说他目前对应的是第三个Memery。现在问题基本解决了。 例如:
​ 有四个Memery地址Mx1,Mx2,Mx3,Mx4,都映射到了Cx,但是Cx上有一个标记,标记说Cx目前存的值等于Mx3 存的值。这样就完美解决了映射的问题。但是新的问题来了,无法逃避,Cache毕竟没有Memery那么大,我现在 要访问Mx1,结果我找到了Cx,Cx却告诉我他现在存的东西不是Mx1,而是Mx3,怎么办??
​ 没办法,这种情况叫miss,只能从Memery找了,我们是这样做的:把从Memery把Mx1以及他附近的其他东西搬过来 搬到Cache,然后更新Cache的标志。回到刚才的例子,也就是把Mx1以及他附近的其他信息的东西搬到了Cx上 然后改掉Cx的标记,说Cx现在不是Mx3了,他现在与Mx1一起了。
​ 如此复杂的操作,真的回使得计算机变快吗?是的,平均性能上提高了,因为Cache和Memery速度差异巨大。不过杨老师曾指出一个 反例,他说,你要是有个恐怖分子,不用我们的Cache,当Cx与Mx1一致的时候你要用Mx2,当Cx变得根Mx2相同了,你 又要用Mx1,那岂不是凉凉?好像确实是这样子的。
​ 为什么说是平均性能的提高呢?有两点,memery使用的时间局部性和空间局部性,当你使用了一个Memery的地址 后,你在不久的将来可能还会使用他 ,你也有肯能使用他附近的其他信息。所以我们把和他相关的东西一股脑都放进 Cache就可以了,但是放多少呢?这个问题,先辈们已经通过统计得出来结论。我们不必关心。

Cache的基本实际实现

​ 之前我们谈到的只是口糊,具体实现的时候,不是一个地址对应一个地址,而是一块对应一块(block), 我们曾谈到,空间局部性,所以说这里不要一个地址对应一个地址的玩了。我们引入block。也就是说 我们把地址Mx1_begin 到Mx1_end这一整块的地址映射到Cx_begin到Cx_end , 然后放一个标记就可以了, 这样的优点很多,比如说省掉了很多标记的记录。。。等等的
​ Cache的地址分为三大块,tag,index,和offset
​ offset指的是一种偏移量,我们之前说过,Cache里面分了很多个block,每一个block都是一个整体,所以 当我们找到了正确的当block当时候,offset用来指向block里面的详细地址。显然,block里面有多少种地址 offset就有多少种值。举个例子,当block是64B的时候,他一共有2^6个byte,我们计算机寻址所关心的只是 哪一个byte,(一般而言,四个byte为一个words)所以我们的offset需要有6个bit,才能恰好指向这2^6个 byte。于是在这种情况下offset为6位
​ index指向我们要找的哪一个block,见杨老师的图

​ 很明显,如果在上述条件下我们的Cache一共有64KB的话,那我们就有 64KB/6B=2^10个block,于是index就是10位的了,可是有一些Cache,特别的有趣,它允许多对多。这就很 头疼了,不过这确实是个好办法。有一定的优点。 多对多是个什么情况呢?类似于这样,有Cx1 Cx2,Mx1,Mx2,Mx3,Mx4,他们很乱,四个Mx都可能映射到 Cx1,也都可能映射到Cx2,注意对比之前的一对多:有Cx,Mx1,Mx2,Mx3,Mx4,四个Mx都可能映射到Cx 多对多多优点的话,不好说,其实是我不知道。这种多对多的骚操作,实现起来更复杂了,他叫n-way set-assoc. 中文名n路集相关。很shit,很神奇。下面是二路集相关(还是杨老师的).

​ 在n路及相关的情况下,index又叫做set,这是他的新名字,这个时候他指向一堆block,换句话说,一堆block共用 一个index。于是,如果刚刚的64KBCache是二路集相关的话,他的index是9位,因为一个index可以指向两个 block。
​ 至于tag,我不是很清楚了。应对考试的话,他的位数用PPA(Physical Page Address )减去index和offset就得到了。
​ 最后剩下的一个是Data Cache entry 他的大小等于Valid bit, Dirty bit, Cache tag + ?? Bytes of Data, 有这些一起组成。Valid bit 一般是一位,他的作用是用来指示这个block是否有用,为什么会没有用呢 我们想到,程序总有启动的时候,当程序刚刚启动的时候,block是无效的,它里面的数据存在,但是 数据却不一定和Memery保持一致。这个问题无法避免,但是可以通过Valid bit解决。Dirty bit是一种懒惰 标记,一般的树形结构,例如线段树,spaly,以及各种可持久化数据结构里面都用这种东西。他用来表明 一种懒惰性,因为Memery慢,因为Cache是用来代替Memery的,当我们读取数据的时候,没有他的用途 单当我们更新数据的时候,我们一定要立即更新Memery吗,不是的,我们可以只更新Cache的block,等 到miss发生的时候,在把它们一起写入Memery即可,所以他叫脏位。是一位。Cache tag就是我们之前说的 标记,用来防止一对多的情况下的那个标记,他等于前面我们算出来的tag的大小。最后一个是Bytes of Data 他恰好等于block的大小,例如64KB的那个Cache,他的大小位64KB=64*8bits=512bits,于是总大小为 1+1+21+512=535bits