几句话说清楚2:CPU缓存的组织形式

缓存

缓存和其他存储形式在功能形式上没有太大区别，均是输入一个地址，还你一个数据。但作为一个缓存，要考虑如何在有限的容量下保证较高的命中率以及查找效率(相关阅读)。这个问题从本质上来说，就是如何建立缓存地址与内存地址的映射关系。

组织形式

缓存按照一个Cache Line的长度（主流长度为64Byte）为粒度来组织：

各种不同的映射形式就是在决定内存中某一个特定地址范围内的数据，具体可以放到哪一个Cacha Line里去。

能想出来的方式也无外乎三种：

• 哪个都可以放
• 只能放到第N个（N是内存地址的函数）
• 只能放到第N个至第M个（M也是内存地址的函数）

其实基本上这篇文章可以结束了，很多技术都不是什么新鲜的“创想”，只是给朴素的思想内核穿上了一层“术语”的外衣。

Direct Mapping

这就是上面说的第二种方式，某一个内存地址段的数据，只能放在第N个Cache Line里

• Pros:查找快，一次寻址，有就是有，没有就是没有，不啰嗦（因为只需要验证一个Cache Line中是否存在该地址）
• Cons:命中率低，CPU经常需要相邻地址的数据，而根据规则，同属于第N个Cache Line的数据会互相排斥，不会同时出现在缓存里

Fully Associative

这就是第一种方式，随便放。

• Pros:命中率高，过去和未来一段时间内需要的数据都可以被放在缓存内，同时不用担心被相邻地址上的数据踢出
• Cons:查找慢，确认一个地址是否在缓存里通常需要遍历整个缓存（Miss的情况）

n-Way Set Associative Cache

这就是第三种方式了，颜色相同的内存地址范围和缓存Cache Line互相对应，不能越界。每一个颜色就是一个Way。

但如果单独拿出某一个颜色来看，是Fully Associative的方式。

这么做当然是为了充分发挥前两种方式的优势。既可以存在相邻内存中的数据以提高命中，同时也一定程度上减少了查找范围，提升查找效率。