Set Associative Cache

tags: IT铁人

Direct Mapped缺点

上次提到了Direct Mapped的做法，概念上就是取余数决定要放在Cache的哪个block，以下图来说

因为1,5,9 mod 4的结果都是1，所以他们都会对应到Cache Block 1，要是今天发生了1,5,9大量被存取的状况，那麽每次都会发生Cache miss，为了改正这件事发生，只要让Cache Block不要一次只能存取一个Memory Block就好了，这就是Set Associative Cache的由来。

Set Associative Cache

就如刚刚上面提到的，我们在每个Cache Block entry多增加几个Block，通常都是以2的次方来做，形成2-way/4-way/8-way set associatve。

最後还有一个最极端的作法，称为Fully associatve，就是不管甚麽余数了，每个位置每个人都可以用，所以Cache的利用程度会最高。

下图是各种Set associative cache的示意图：

不过提高数字的情况下，一方面同样的Cache Block entry数量就会变少，当一个entry有太多Block时，找Block时就要在进入entry时一个一个检查tag是否正确。

所以基本上miss rate会降低，不过hit time就会增加，所以如何选择set associative cache的类型就是一大课题，要经过实验测试，探讨不同情境下的需求後才比较好做选择。

白话说明Set Associative Cache

我们可以这样子想，假设一间学校的学生是固定的，教室的数量可以自行增加，那如果一个班只有一个学生，那麽我们要找特定同学时只要到对的班级就好了，不过这样子班级的数量就会非常大。

假设一个班级装30位同学，总共有30个班级，那麽我们找到对的班级後，还要一个一个对座号，直到找出对的同学。

怎麽样的分法比较好，取决於班级的管理难易度，如果班级能够很快速地找到特定座号，那麽提高班级中的人数也不一定是坏事，反之则尽量不要增加班级中的人数。

虽然跟Cache的特性还是有些出入，比如说Cache miss後需要替换掉Block，班级通常不会淘汰同学补进新的。不过在找班级以及对照座号的概念其实是差不多的。

找人示意图(图片取自自由时报 占不到教室位子 中年男爆气烙20人要他出来乔)：

Replace

在Set Associative Cache中，因为一个entry中有多个位子，所以当满位并且又有新的Block要进来时，我们就要挑一个Block淘汰掉，选择也是一门学问，可以随机挑选，也可以把最先进来的老屁股使用，不过最常使用的是LRU(Least Recently Used)，也就是要淘汰距离上次使用到的时间最久的Block，以下示范一个例子。

假设这是一个2-way set associative cache，并且共有4个Block(也就是说只有两个entry)。

CPU要求的Block依序如下：3,4,8,5,6,3,9。
在前面四次request後Cache长这样：

後面的6,3,9依序会发生下列的事情：
6会替换4，3原本就在Cache中(Hit)，9会替换比较久没有用到的5。
所以最後Cache内容为：

What's Next?

这次说明了Set Associative Cache的用法以及优缺点说明，还有用白话的方式举例说明，也示范了一下Replace。

下次会提出另一种减少miss rate的方式，由於Cache的做法都是用相同层级的记忆体，也就是说现在只有一层城墙，如果第一层抓不住就宣告失败了。

如果我们有两层以上的城墙，效果会变得怎样呢？