本文参考了:
简述
上篇文章 讲了 cache 的一些基本知识,提到了一种最基本的 cache 组织策略:Direct Mapped Cache。这种策略优点是实现简单,速度快(这里指的速度快是说定位 cache 位置的速度,因为一个 main memory address对应在 cache 中的位置是固定的),但是有一个严重的缺陷,就是 cache miss 率高。为什么呢?还是看下面这个图,假如 CPU 恰好依次需要0、4、8、12这四个 main memory address 的速度,之后的 block 都会把前面 block 的挤占掉!(尽管现在 cache 中还有很多空余空间)
本文将介绍另外两种 cache 组织策略:Fully Associative Cache
和 Set Associative Cache
。
Fully Associative Cache
Fully Associative Cache是解决了Direct Mapped Cache cache miss
高的缺陷。它是怎么实现的呢?
对比一下Direct Mapped Cache的示意图,Fully Associative Cache中就没有 index 这个位了,main memory 中的一个block 可以被 map 到 cache 中的任意位置。这种方法,定位main memory block 在 cache 中位置是通过 tag 位来判断的。因为没有 index,所以在 cache 中定位的时候,就需要对比 cache 中每一条记录的 tag,That’s a lot of comparators!
所以,Fully Associative Cache只适用于小的 cache,比如某些 Intel CPU 中的 TLB cache就是Full Associative
的。这里说的小
是非常小
,顶多也就几十个 entry。虽然这种方法应用也不是很广泛,但是给了我们一种很好的思路:Direct Mapped Cache 定位快,但是 cache miss 几率高;Fully Associative Cache 定位慢,但是 cache miss 率低。那么,可以取一个中间值,使得定位 速度足够快,同时cache miss几率足够低。
Set Associative Cache
Set Associative Cache是Direct mapped cache 和 Fully associative cache的一种取舍。cache 被分成了多个 set,每个 set 里面有多个 cache line。一个 memory block 会先被 map 到其中一个 set,然后置于此 set 中的任一cache line。
Direct mapped cache 可以看做 n * 1的矩阵(n 个set,每个 set 含有一个 entry),Fully associative cache可以看做1 * m 的矩阵,而Set Associative Cache就是 n * m 的矩阵。Direct mapped cache实质上可以看作是 1-way Associative Cache,而Fully associative cache是 m-way Associative Cache。
那么现实生活中,该采用 ?-way Associative Cache呢?一般选择8-way 就足够了,下图的数据可以得到一个直观地感觉。
总结一下
Direct Mapped Cache实现最简单,但是 cache miss 率太高,实际生产几乎不会使用。Fully Associative Cache cache miss 几率最低(理论上可以达到0),但是如何快速定位cache line 所在位置成了个大问题,所以只适用于很小的cache,比如TLB cache
。Set Associative Cache是二者的权衡,普遍采用的是8-way Associative Cache。