1.1 为什么需要 Cache

for (j = 0; j < 100; j = j + 1)
    for( i = 0; i < 5000; i = i + 1)
        x[i][j] = 2 * x[i][j];

1.2 实际系统中的 Cache

1.3 Cache 的分类

• 按照数据类型划分：I-Cache与D-Cache。其中I-Cache负责放置指令，D-Cache负责方式数据。两者最大的不同是D-Cache里的数据可以写回，I-Cache是只读的。
• 按照大小划分：分为small Cache和large Cache。没路组（后文组相连介绍）<4KB叫small Cache, 多用于L1 Cache, 大于4KB叫large Cache。多用于L2及其他Cache.
• 按照位置划分：Inner Cache和Outer Cache。一般独属于CPU微架构的叫Inner Cache, 例如上图的L1 L2 CACHE。不属于CPU微架构的叫outer Cache.
• 按照数据关系划分：Inclusive/exclusive Cache: 下级Cache包含上级的数据叫inclusive Cache。不包含叫exclusive Cache。举个例子，L3 Cache里有L2 Cache的数据，则L2 Cache叫exclusive Cache。

• 数据如何放置
• 数据如何查询
• 数据如何被替换
• 如果发生了写操作，Cache如何处理

2.1 数据如何放置

• 全相连（Fully associative）。可以放在Cache的任何位置。
• 直接映射（Direct mapped）。只允许放在Cache的某一行。比如12 mod 8
• 组相连（set associative）。可以放在Cache的某几行。例如2路组相连，一共有4组，所以可以放在0,1位置中的一个。

2.2 如何在Cache中找数据

2.3 如何替换Cache中的数据

• 随机替换。如果发生Cache miss里随机替换掉一块。
• Least recently used. LRU。最近使用的块最后替换。
• First in, first out (FIFO), 先进先出。

• 不在本 Cache 替换。如果Cache miss了，直接转发访问地址到主存，取到的数据不会写到Cache.
• 在读MISS时替换。如果读的时候Cache里没有该数据，则从主存读取该数据后写入Cache。
• 在写MISS时替换。如果写的时候Cache里没有该数据，则将本数据调入Cache再写。

2.4 如果发生了写操作怎么办

• 通写：直接把数据写回Cache的同时写回主存。极其影响写速度。

• 回写：先把数据写回Cache, 然后当Cache的数据被替换时再写回主存。

• 通写队列：通写与回写的结合。先写回一个队列，然后慢慢往主存储写。如果多次写同一个数据，直接写这个队列。避免频繁写主存。

策略一：基于监听的一致性策略

策略二：基于目录的一致性策略

• SI: 对于一个数据块来讲，有share和invalid两种状态。如果是share状态，直接通知其他Cache, 将对应的块置为无效。
• MSI：对于一个数据块来讲，有share和invalid，modified三种状态。其中modified状态表表示该数据只属于这个Cache, 被修改过了。当这个数据被逐出Cache时更新主存。这么做的好处是避免了大量的主从写入。同时，如果是invalid时写该数据，就要保证其他所有Cache里该数据的标志位不为M，负责要先写回主存储。
• MESI：对于一个数据来讲，有4个状态。modified, invalid, shared, exclusive。其中exclusive状态用于标识该数据与其他Cache不依赖。要写的时候直接将该Cache状态改成M即可。

• 如果其他Cache里有这份数据，如果其他Cache里是M态，先 把M态写回主存再读。否则直接读。最终状态变为S。
• 其他Cache里没这个数据，直接变到E状态。

• 如果发生了处理器读操作，仍然在S态。
• 如果发生了处理器写操作，则跳转到M状态。
• 如果其他Cache发生了写操作，跳到I态。

• 发生了处理器读操作还是E。
• 发生了处理器写操作变成M。
• 如果其他Cache发生了读操作，变到S状态。

• 发生了读操作依旧是M态。
• 发生了写操作依旧是M态。
• 如果其他Cache发生了读操作，则将数据写回主存储，变换到S态。