Direct mapped caches(直接映射)

我们假设block的大小为1byte

我们将memory按cache进行分块,可以看到,将memory按cache进行分块后,memory中每个块中的行对应cache中的相应行,即我们可以通过index来知道我们想要的数据在哪里,这里我们的block只有1byte,如果block的大小大于1byte是什么样呢?

当block的大小等于2byte时,我们依然将memory按cache进行分块,这时如果只有index的话,我们只知道数据在哪一行,但不能确定数据的正确位置,因此,我们需要offset来确定数据的具体位置

那我们怎么知道cache中的某一行来自memory中的哪个地址呢?这时我们需要使用tag,我们将memory按cache进行分块后,给每个块加上索引,即这个索引就是tag

我们来看一个例子

假设cache的大小为32byte,memory为4GB,每个block为4byte,那么我们的cache有8行,我们需要2bit来确定offset,3bit来确定index,那么32 - 2 - 3 = 27bit来确定tag,将memory按cache分块后,每一个块中的第一行的后5位都是相同的,为什么?因为第0块和第1块的第一行地址相差32byte,即第0块的第一行地址加上32等于第1块的第一行的地址,那么显然后5位是相同的,即tag不需要32位地址来确定

如何从cache中获取数据?

我们首先添加一个有效位,来确定cache中的该行是否存放有数据

  1. 我们可以通过index来确定数据在cache中的哪一行,
  2. 然后我们检查有效位,若有效位为0,那数据不存在,cache miss,
  3. 若有效位为1,我们比较tag来确定我们想要的数据是否存在,若tag匹配,则cache hit,否则,cache miss,若cache hit,我们可以通过offset来拿到我们想要的数据

当valid为1,而tag不匹配时,即发生了conflict misses,那么我们就需要从memory中拿到相应的数据然后替换改行,然后再从cache中返回相应的数据

Writes

当write hit时,我们有两种方法进行写

  1. write-through,更新cache和memory
  2. wrte-back,只更新cache,并在block中添加dirty bit,当block被替换时,更新memory

Fully associative caches(全相联)

在全相联中,没有index,因为block可以任意放置,所以当我们查找数据时,必须比较所有的tag

在direct mapped中,存在conflict misses,而在fully associative cache中,因为block是随意放置的,以此不存在conflict misses,当cache的大小有限,因此存在capacity misses

Set-associative caches(组相联)

direct mapped caches和fully associative caches都可以看成是set-associative caches的特殊情况,在direct mapped caches中,我们通过index来确定数据在哪一行,而在set-associative caches中,index确定数据在哪一个set,而在每一个set中,都是fully associative,即set中的block可以任意放置,可以看到,direct mapped caches是每一个set中的block数量为1的情形,而fully associative caches是只有一个set的情形

set-associative caches如何获取数据?

  1. 我们通过index来找到正确的set
  2. 在set中比较所有的tag
  3. 如果tag匹配,则cache hit,我们通过offset来拿到我们想要的数据

Block replacement policy

在direct mapped caches中,当发生conflict misses时,我们直接替换block即可

而在set-associative cache和fully-associative cache中,我们使用LRU替换算法

Average memory access time(AMAT)

来看一个例子

cache 一致性问题

在多核处理器中,每个处理器都有自己的cache,通常每个核都有自己的L1, L2 cache,而多个核共享L3 cache和memory

如果processor1从memory中读取了一个数据x,并把他放在自己的cache中,processor2从memory中的相同地方读取了x,并把他放在自己的cache中,如果processor1将x改成了y,如果采用write back,此时,processor1和processor2中的cache的数据是不一样的

如何解决这个问题呢？

MOESI protocol:

我们给cache中的block增加一些状态

  1. shared: 其他cache中可能拥有
  2. modified: 数据是脏的,即memory中的数据和cache中的数据不同,数据没有写回memory,如果block需要被替换,则应先写回memory,其他cache中没有相应的副本
  3. exclusive: 数据是干净的,且只存在于当前cache中
  4. owner: 数据是脏的,且其他cache中可能拥有
  5. invalid: 该 Cache Line 里的数据是无效的, 不能读取，必须重新从内存或其他核心获取。

MOESI 工作流程：

假设我们有三个核， CoreA, CoreB，CoreC

  1. CoreA 读取 x, cache miss , CoreA 发送广播，询问哪个核拥有 x, 没有核拥有 x, 从memory 读取
  2. CoreA 修改 x, 由于是 E 状态，直接修改，不需要通知其他核，然后状态变为 M
  3. CoreB 读取 x, cache miss, CoreB 发送广播， CoreA 嗅探到请求，发现自己是 M, CoreA 不写回内存, 直接把最新的数据通过总线传给 Core B, CoreA 状态变为 O, CoreB 状态变为 S
  4. Core 读取 x, cache miss, CoreC 发送广播，CoreA 处于 O 状态，发送给 CoreC, CoreB 处于 S 状态，不响应，CoreC 状态变为 S
  5. Core B 修改 x, CoreB 状态为 S，Core 发送广播，CoreA 核 CoreC 收到消息，状态变为 I, CoreB 状态变为 M
  6. 如果 CoreB cache 满了，需要移除 x, 由于是 M 状态，需要先写回 memory