高速缓存
高速缓存
程序访问的局部性
最早期的计算机，在执行一段程序时，都是把硬盘中的数据加载到内存，然后 CPU 从内存中取出代码和数据执行，在把计算结果写入内存，最终输出结果。随着程序运行越来越多，就发现一个规律：内存中某个地址被访问后，短时间内还有可能继续访问这块地址。内存中的某个地址被访问后，它相邻的内存单元被访问的概率也很大。
人们发现的这种规律被称为程序访问的局部性。程序访问的局部性包含 2 种：
- 时间局部性：某个内存单元在较短时间内很可能被再次访问
- 空间局部性：某个内存单元被访问后相邻的内存单元较短时间内很可能被访问
出现这种情况的原因很简单，因为程序是指令和数据组成的，指令在内存中按顺序存放且地址连续，如果运行一段循环程序或调用一个方法，又或者再程序中遍历一个数组，都有可能符合上面提到的局部性原理。那既然在执行程序时，内存的某些单元很可能会经常的访问或写入，那可否在 CPU 和内存之间，加一个缓存，CPU 在访问数据时，先看一下缓存中是否存在，如果有直接就读取缓存中的数据即可。如果缓存中不存在，再从内存中读取数据。
事实证明利用这种方式，程序的运行效率会提高 90%以上，这个缓存也叫做高速缓存 Cache。
缓存详解
缓存是 CPU 体系结构中最重要的元素之一。要编写高效的代码，开发人员需要了解其系统中的缓存如何工作。高速缓存是较慢的主系统内存的非常快的副本。高速缓存比主存储器要小得多，因为它与寄存器和处理器逻辑一起包含在处理器芯片内。从计算的角度来看，这是主要的房地产，并且其最大大小在经济和物理上都有限制。随着制造商发现越来越多的方法将越来越多的晶体管填充到芯片中，高速缓存的大小已大大增加，但是即使最大的高速缓存也只有几十兆字节，而不是主存储器的千兆字节或硬盘的数兆字节。
缓存由镜像主内存的小块组成。这些块的大小称为行大小，通常为 32 或 64 字节。在谈论缓存时，谈论行大小或缓存行是很常见的事，它指的是镜像主内存的一块。高速缓存只能以高速缓存行的倍数加载和存储内存。缓存具有自己的层次结构，通常称为 L1，L2 和 L3。L1 高速缓存是最快和最小的；L2 更大，更慢，L3 更大，更慢。
L1 缓存通常进一步分为指令缓存和数据，在引入中继的基于哈佛 Mark-1 的计算机之后被称为“哈佛架构”。拆分缓存有助于减少流水线瓶颈，因为较早的流水线阶段倾向于引用指令缓存，而较后的阶段则倾向于数据缓存。除了减少对共享资源的争用之外，为指令提供单独的缓存还允许使用指令流性质的替代实现。它们是只读的，因此不需要昂贵的片上功能（例如多端口），也不需要处理子块读取操作，因为指令流通常使用更常规大小的访问。
在正常操作期间，处理器会不断要求高速缓存检查高速缓存中是否存储了特定的地址，因此高速缓存需要某种方法来非常快速地查找其是否存在有效行。如果可以将给定地址缓存在缓存中的任何位置，则每次进行引用以确定命中或未命中时都需要搜索每个缓存行。为了保持快速搜索，这是在高速缓存硬件中并行完成的，但是对于合理大小的高速缓存而言，搜索每个条目通常过于昂贵。因此，可以通过限制特定地址必须驻留的位置来简化缓存。这是一个权衡；高速缓存显然比系统内存小得多，因此某些地址必须别名。如果两个彼此互为别名的地址一直在不断更新，则它们将争用缓存行。
-
直接映射的缓存（Direct mapped caches）将允许缓存行仅存在于缓存中的单个条目中。这是最简单的在硬件中实现的方法，由于两个阴影地址必须共享同一条缓存行，因此无法避免混淆现象。
-
完全关联高速缓存（Fully Associative caches）将允许高速缓存行存在于高速缓存的任何条目中。由于可以使用任何条目，因此可以避免别名问题。但是在硬件中实现非常昂贵，因为必须同时查找每个可能的位置以确定值是否在缓存中。
-
集合关联缓存（Set Associative caches）是直接关联和完全关联缓存的混合，并且允许特定的缓存值存在于缓存内的某些行子集中。高速缓存被划分为偶数部分，称为方式，并且可以以任何方式定位特定地址。因此，n 路集关联缓存将允许在行大小为 set n 的总块 mod n 中的任何条目中存在一条缓存行。上图中“缓存关联性”显示了一个示例的 8 元素，4 路集关联缓存。在这种情况下，这两个地址具有四个可能的位置，这意味着在查找时仅必须搜索一半的缓存。方式越多，可能的位置就越多，混淆现象就越少，从而导致总体上更好的性能。
一旦缓存已满，处理器就需要清除一行来为新行腾出空间，处理器可以通过多种算法选择逐出哪条线。例如，最近最少使用（LRU）是一种算法，其中丢弃最旧的未使用的行以为新行腾出空间。当仅从高速缓存中读取数据时，无需确保与主内存的一致性。但是，当处理器开始写入高速缓存行时，它需要就如何更新底层主内存做出一些决定。
-
直写式高速缓存（Write-through）将在处理器更新高速缓存时将更改直接写入主系统内存。这是较慢的，因为如我们所见，写入主存储器的过程较慢。
-
回写缓存（Write-back）会将更改延迟写入 RAM，直到绝对必要为止。明显的优点是，写入缓存条目时需要较少的主存储器访问。已写入但未提交给内存的缓存行称为脏行。缺点是，当退出缓存条目时，它可能需要两次内存访问（一次写入脏数据主内存，另一次加载新数据）。
如果一个条目同时存在于较高级别和较低级别的高速缓存中，则我们说较高级别的高速缓存是 Inclusive；否则，如果具有一行的较高级别的高速缓存消除了具有该行的较低级别的高速缓存的可能性，我们说它是排他的（Exclusive）。
缓存寻址
到目前为止，我们还没有讨论过缓存如何确定给定地址是否驻留在缓存中。显然，高速缓存必须保留当前驻留在高速缓存行中的数据的目录。缓存目录和数据可能位于同一处理器上，但也可能是分开的，例如在具有核心 L3 目录的 POWER5 处理器的情况下，但是实际上访问数据需要遍历 L3 总线才能访问 核心内存。这样的安排可以促进更快的命中/未命中处理，而不会产生将整个缓存保留在内核中的其他成本。
需要并行检查标签以降低等待时间。更多的标记位（即，较少的设置关联性）需要更复杂的硬件来实现。另外，更多的集合关联性意味着更少的标签，但是处理器现在需要硬件来多路复用许多集合的输出，这也可能增加延迟。
为了快速确定地址是否位于缓存中，将其分为三个部分：标签，索引和偏移量。偏移位取决于高速缓存的行大小。例如，一个 32 字节的行大小将使用地址的最后 5 位（即 25）作为行的偏移量。索引是一个条目可能驻留的特定缓存行。例如，让我们考虑一个具有 256 个条目的缓存。如果这是一个直接映射的缓存，我们知道数据可能仅驻留在一条可能的行中，因此偏移量后的下一个 8 位（28）描述了要检查的行-0 到 255 之间。
现在，考虑相同的 256 元素高速缓存，但是分为两种方式。这意味着有两组 128 行，并且给定地址可以位于这两个组中的任何一个中。因此，仅需要 7 位作为索引即可偏移到 128 个条目的路径中。对于给定的高速缓存大小，随着方法数量的增加，由于每种方法都会变小，因此减少了作为索引所需的位数。高速缓存目录仍然需要检查高速缓存中存储的特定地址是否是它感兴趣的那个地址。因此，该地址的其余位是高速缓存目录对照传入的地址标记位进行检查以确定是否存在标记位。缓存命中与否。“缓存标签”中说明了这种关系。
当存在多种方式时，此检查必须在每种方式中并行进行，然后将其结果传递到多路复用器，该多路复用器输出最终的命中或未命中结果。如上所述，高速缓存的关联性越高，索引所需的位越少，而标记位则越多-到完全关联的高速缓存的极端（其中没有位用作索引位）。标签位的并行匹配是高速缓存设计的昂贵组件，并且通常是高速缓存可以增长多少行（即，多大）的限制因素。