cache

什么是cache

cache是介于processor和memory中间的存储介质。由于memory调用过慢，所以我们避免从memory直接获取数据，且最好每一次获取数据可以多获取一些。又由于大多数data和instruction数据其实地址是连续的，例如访问数组时常常会顺序访问，所以一次性获取连续内存是一个较为高效的手段。cache就是用来存储那些暂时还没有用的数据，而为了方便起见，我们会将当前要process的数据一并存进去之后再从cache调用。

将计算机看作library的话读书的人是processor，图书馆书架上的书是memory，而cache是我们桌子旁边的书。我们并不希望每读一本书都要从茫茫书海中再找一本，而是最好把可能相关的书先搬到自己的桌边。

cache是如何设计的？

我们从最简单的direct mapped cache开始。

read

我们会将地址分为Tag，Index，Offset，如上图所示。

上图为cache内部的储存格式。每一个index对应着一个block，每个block中有多个word，选择哪一个block由index决定，选择哪一个word由offset对应位决定。其中block内的word是内存连续的。valid为0/1，表示当前这个位置是否有数据存储。Tag和Index与地址中的Tag和Index对应，这里有点像hash的思想，我们以Index为hashcode，索引这个位置后比对tag，比较是否的确是这个数据。如果是(read hit)的话就load，如果不是(read miss)的话我们会从memory中将数据加载到cache中。其中miss分为3大类：

1. compulsory misses (cold start misses / first reference misses)：初次read某一个地址，所以地址从未被加载到cache中过。
2. conflict misses (collision misses / interference misses)：虽然不是初次read，但是当前index位置被其他数据覆盖掉了。
3. capacity misses：也是被其他数据覆盖掉了，但是仅在fully associate cache中涉及，将在那一块再解释。

下图为read总结：

write

我们如果想要更改某个地址的内容，有两种解决方案（write policy）：

1. write-through：同时将数据写入cache和memory。（由于速度过慢，经常会配合一个write buffer，先将数据写入buffer再写入memory，这样可以并行运行，不会delay后续指令。）

   

2. write-back：只将数据写入cache，并标记，只有当被标记的cache要被覆盖掉时才写回memory。

write也会存在miss的情况，也就是我们将要write的地址不在cache中，这个也有两种解决方案：

1. 将memory中的内容传入cache，然后再按照write policy做。
2. 直接write到memory。

下图为write总结：

block size trade-off

block size太大容易说明block数量变小，index容易产生hash碰撞，虽然碰撞后不一定miss。
block size太小说明每个block中存储的东西太少，虽然index较难碰撞，但是一旦碰撞就是miss。

其他cache种类

set associative cache

每一个index对应了n个block，n个block不需要内存连续。这种设计可以有效降低miss rate

fully associative cache

不再分index，所有block都可以随意存储。

好处：even lower miss rate

坏处：每次调用数据需要查询整个cache

Block replacement policy

对于上述两种cache，我们需要决定到底覆盖哪一个block，这是由block replacement policy决定的。常见有以下policy：

LRU（Least Recently Used）：选择该组中最后一次被访问最早的block进行替换。

FIFO（先进先出）：选择该组中最早进入缓存的block进行替换。

随机替换：随机选择一个block进行替换。

Multilevel Cache

现代应用中常用多层cache优化系统。

本文图片都是取自NUS CS2100 lecture slides。