本节书摘来自华章出版社《计算机存储与外设》一书中的第1章，第1.3节，作者Computer Organization and Architecture: Themes and Variations［英］艾伦·克莱门茨（Alan Clements） 著，沈 立 肖晓强 王苏峰 译，更多章节内容可以访问“华章计算机”公众号查看。
1.3 Cache的组织
下面介绍Cache的组织和结构。一个Cache只是可用存储空间的一小部分。那么什么样的数据可以进入Cache？数据会放在什么位置？相比于主存储器，Cache存储系统的设计以及与计算机系统的集成都要更困难。部分是因为Cache速度快，部分是因为其复杂性高。事实上，直到20世纪80年代，只能在小型机和大型机上见到Cache。直到20世纪80年代后期，随着68020/30以及80386/486微处理器的出现，Cache才开始在个人计算机中出现。今天，已经可以将超过10亿个晶体管集成在芯片中，这样可以确保所有高性能处理器都包含一个大容量的片内Cache。
Cache设计的根本问题是如何构建一个存储体来存放来自大容量主存储器任意位置的一组数据元素。解决该映射问题的方法很多，但实际Cache系统通常使用组相联（set associative）方式进行组织。下面首先介绍两个Cache结构实例，以便读者理解组相联Cache的操作。
1.3.1 全相联映射Cache
在设计任何一种存储系统时需要问的第一个问题是，基本数据单元的大小是多少？主存储器处理单位数据的大小与机器的基本字长相同。例如，具有64位寄存器的64位机器采用64位存储器。如果计算机需要少于一个字的数据，它首先读取整个字，然后再忽略它不想要的位。
虽然计算机可以从Cache中读取一个字，但该字的大小并不是Cache基本存储单元的大小。Cache基本存储单元为包含几个连续字的块（line）。假定Cache是按照字的粒度（granularity）来组织的。当访问某条指令时，如果它不在Cache中，则必须从主存储器中读取。然而，下一条指令又有可能会失效。因此需要比一个字大的Cache基本存储单元。
Cache块（cache line）由一系列连续的字构成，这样从Cache中可以连续读出几条指令从而不会发生失效。当发生失效时，包含该字的整个Cache块将从主存调入Cache。Cache块大小的最优值取决于Cache的总容量、代码的属性以及采用的数据结构。
人们希望Cache对存放在其中的数据不加限制；即Cache中的数据可以来自主存的任何地方。这种Cache使用相联存储器把数据存放在其中的任意位置，此时是根据其值（value）而不是根据其地址/位置（address/location）来访问数据。
图1-7说明了相联存储器的概念。每个数据项有两个值，关键字（key）以及数据元素；例如，最上面一行包含关键字52B1和数据F0000。此时，数据没有排序，一个数据项可以保存在存储器的任意位置。访问关键字是检索数据的主要手段。访问相联存储器时需要将关键字输入存储器，然后将此关键字与存储器中所有关键字进行并行匹配。如果发现了该关键字，该数据就被检索到了（即与关键字关联的数据）。例如，计算机向图1-7中的系统输入关键字F001。该关键字将同时交给存储器中的所有位置进行比较。由于给定F001会发生匹配（即命中），存储器将给出一个命中响应信号，同时将数值42220在数据端口输出。
相联Cache的工作原理看上去与图1-7中的机制相似，用关键字作为处理器访问的地址，数据就存放在该地址处。传统存储器与相联存储器的区别在于，传统存储器包含以0,1,2，…编号连续存储的元素，而相联存储器包含的元素并没有排序或者按顺序存放。
下面详细讨论全相联Cache的部分细节。图1-8所示的相联存储器允许Cache中的任意一块都可以存放来自主存储器的任意一块数据。此例中，存储器被划分成包含两个字的块（每块两个字是为了简单起见，实际的Cache可能每块含有8个或更多的字）。
相联Cache的大小可以任意，Cache中块的数量与主存储器中块的数量之间没有关系。考虑主存储器为16MB，相联映射存储器为64KB。如果一块包含4个32位的字（即块大小为16字节），则主存储器由224/16 = 1M个块构成，而Cache包含216/16 = 4096个块。
相联Cache允许主存储器的任意一块数据存放在其任意一块中。上例中，相联Cache的第i块可以存放来自主存储器中1M块中的任何一个。因此，Cache中第i块需要一个标志（tag）来唯一标识其与主存储器中的某一块相关联。由于在该例中，主存储器有1M块，因此标志应该为20位来代表220个块。
当处理器产生一个地址时，将使用块内地址来定位主存储器或者Cache中一个字的位置（上例中，块内地址为2位）。来自CPU的20位的块地址A23～A04不能用于定位Cache中的块，这是为什么？因为相联存储器将主存储器中1M个块中的任意一个存放于其4096个块中的任意一个，Cache并不知道要访问的块目前是否在Cache中。即使知道块在Cache中，也不知道它到底在哪里。
图1-9说明了为什么针对在Cache中定位一块这个问题找不到简单的解决方案。在该例中，同样使用24位地址总线访问主存中16MB的DRAM和块大小为64KB的相联映射Cache。Cache中每一块有16个字节，对应4个32位的字。CPU可以访问的全部块的总数是224/24 = 220，使用24位地址。该地址由A23～A04（块地址）、A03～A02（块内地址）以及A01～A00（字节地址）组成。因此，需要20位的标志来唯一标识一块。
如何把来自CPU的包含1M个块的地址映射为Cache中包括4096个块对应的地址？图1-9给出了一种解决方案，该方案使用220个字、每个字12位的随机访问存储器来存储指向Cache块的4096个指针。该存储器是稀疏的，因为1M个存储位置中只有Cache中的4096块具有指针。其他位置没有指针是因为当前块在主存储器中而不是在Cache中。当然，为了实现这个机制，需要在查找表中每一行增加一个额外的位来表示当前块是否在Cache中（即“命中/失效”位）。
图1-9所示系统实现起来不便宜，因为需要保存指向Cache的指针构成的存储器容量可能与主存储器一样大或者超过主存储器的容量！此外，查找表必须非常快以避免增加Cache的访问时间。在该例中，64KB的Cache对应的查找表有1M个字，每个字12位（即大小为1.5MB），故该方案是不切实际的。可行的解决方案是使用相联存储器。
相联存储器
相联Cache名称来源于其使用相联存储器来存放标志。相联存储器具有n位输入但并不一定需要对应2n个唯一内部位置。n位输入交给相联存储器并与每个位置上的标志域同时进行比较。如果输入地址与某个正存储的标志相匹配，则输出与该位置关联的数据。否则，相联存储器输出不匹配。
继续前面的例子，相联Cache使用相联存储器保存4096个20位的标志（Cache中的每块对应一个标志）。当CPU进行存储器访问时，地址总线的高20位将作为相联存储器的输入。如果相联存储器包含该标志，则返回相应的Cache块。
由于来自主存储器的块可位于相联Cache中的任意位置，当Cache满了会出现什么情况？需要删除哪个块来为新调入的块提供空间？实际上，相联Cache会保存每块上次被访问的时间，这样就可以将最久没有使用的块淘汰（或使用其他参数来决定将哪一块淘汰出Cache）。Cache的替换策略与虚拟存储器使用的类似（见下一节，例如，最近最少使用（LRU）、先入先出（FIFO），或随机策略等）。最近最少使用算法直观上最好，因为它旨在清除最长时间没有被访问的数据（如果不使用它就丢弃它）。然而，LRU算法不容易实现，因为这样做需要记录每块的最后访问时间。
相联存储器很昂贵，因为它需要大量的并行逻辑将输入关键字（即当前的地址）与当前存储的关键字同时进行匹配。市场上现有的相联存储器都太小，不能用来实现实用的Cache系统。
相联Cache可能会产生两种类型的失效：一种是在第一次访问时的强制失效（compulsory miss）。它是强制的，因为Cache块中初始时是没有数据的。减少强制失效的唯一方法是在访问所需的数据之前预先向Cache中调入数据。当相联Cache已经满了，所需数据不在Cache中的时候，就会产生第二种Cache失效——容量失效（capacity miss）。
1.3.2 直接映射Cache
组织Cache最简单的方法就是采用直接映射（direct mapping），它依赖于一种简单的算法将主存储器中的数据块映射到Cache中的块。在直接映射Cache中，主存块被分为若干个组（set），组的大小与Cache的大小一致。如前面的例子，一台具有16MB内存和64KB Cache的计算机会将存储空间分为16MB/64KB = 256个组。
为说明直接映射Cache是如何工作的，假定主存储器包括32个字，需要5位的地址来访问，Cache的大小为8个字，块大小为2个字。根据前面的定义，组大小为：存储器容量/Cache容量= 32/8 = 4。给定5位地址s0、s1、l1、l0和w，其中s位定义了组，l位定义了块，w位定义了字。图1-10展示处理器当前需要的字是如何根据组地址、块地址以及字地址进行访问的。为了方便讨论，这里只考虑组和块的访问，而不管一块中有多少个字。
图1-10所示的组织形式被称为直接映射Cache，因为Cache中某块的位置与主存储器中块的位置之间有直接的关系。在图1-10给出的例子中，Cache具有2位的块地址，因此具有22=4个块。如果直接映射Cache有b位块地址字段，则Cache就有2b个数据块。
当处理器产生一个地址，就会访问Cache中对应的块。例如，如果处理器生成5位地址01100，则访问第2块。图1-10显示了主存储器中有4个块编号为第2块：第0组的第2块、第1组的第2块、第2组的第2块以及第3组的第2块。假设在这个例子中，处理器访问第1组中的第2块，显然的问题是：系统如何知道Cache中被访问的第2块是来自主存储器中第1组的第2块？
图1-11显示了直接映射Cache是如何解决这个问题的。在Cache中每块都有一个标志来标识该块来自主存储器中的哪个组。当处理器给出的访问地址中块地址为3，Cache中第3块对应的标志将发送给比较器。同时，处理器地址中的组字段也被发送给比较器。如果它们相同，则表明Cache中的块就是所需要的块，发生命中。如果它们不相同，则发生失效，对应Cache块中的数据必须更新。
当访问第i块并发生失效时，Cache中原来的第i块要么被丢弃，要么被写回主存储器，这取决于主存储器的更新是如何组织实现的。后文将对Cache这方面的问题进行研究。
图1-12从另一种观点来描述直接映射Cache，其中主存储器被当成一个组数×块数的矩阵，该例中为4块×4组。矩阵的旁边是Cache，它具有与主存储器相同的块数。当前Cache中的块与主存储器中阴影部分的块相对应。图1-12表明，Cache中的块是如何从组号相同的主存储器的某组中获得的。
图1-13给出了直接映射Cache存储器系统的框架结构。Cache存储体由保存数据的高速RAM构成。Cache标志RAM（cache tag RAM）是一种由高速随机访问存储器和数据比较器构成的特殊设备。Cache标志存储器的地址输入是处理器访问的块地址（line address），该地址用来访问或指向包含该组标志的标志RAM中的位置。将该地址对应Cache标志RAM中的数据送往比较器并与地址总线上的组地址进行比较。如果处理器给出的组字段与被访问块的标志相匹配，Cache标志RAM返回命中信号。
直接映射Cache不需要复杂的块替换算法。如果需要访问组y中的块x且发生了失效，主存储器组y中的块x将被加载到Cache中的第x块。当新块载入时，直接将失效位置对应的块淘汰出Cache。
直接映射Cache的优点是其固有的并行性。由于保存数据的Cache存储器和Cache标志RAM是独立的，它们可以被同时访问。一旦从地址总线给出的标志字段与Cache标志RAM的标志字段相匹配，则命中，从Cache中获取的数据就是有效的。
直接映射Cache的缺点是它对被缓存数据的位置敏感。可以联系地址簿来理解，假设为每个字母保留6个位置。如果你已经有6个朋友的姓是以S开头的，那么下一次再碰到一个人的姓是以S开头时就会出现问题。这很烦人，因为给Q和X预留的位置可能完全是空的而不能用。由于只有一个编号为x的块能够放在Cache中，访问主存储器中其他不同的组中块号为x的块将导致Cache中第x块被替换。
即使Cache没有存满，在访问主存储器不同组中相同块号的两个块时，会导致块在Cache和主存储器间进行交换。该问题会导致较低的Cache利用率和高失效率。这种在即使Cache没有存满时也发生块替换的情况称为冲突失效（conflict miss），这是由于新块和原缓存块之间存在冲突。读者很快会看到，提高直接映射Cache的性能并不难。
虽然在数据组织不恰当时，直接映射Cache的性能会非常差，但实际程序的统计测量结果表明，直接映射Cache在最坏情况下的性能对其平均性能的影响并不明显。
图1-14展示了一个非常简单的直接映射Cache的操作，该系统具有16个字的主存储器和8个字的直接映射Cache。为简化讨论，只考虑对指令的访问。该Cache可以保存来自两个组的一个块。图中在Cache左侧将块编号为0～7，在其右侧编号8～15，用来表明主存储器中8～15块被缓存。假定块大小与字的长度相等，并运行如下代码：
图1-14只显示了取指周期。图1-14a给出了系统的初始状态。图1-14b～d显示取前3条指令，每条都存放在连续的Cache位置。当图1-14d中调用子程序后，转向地址为10的指令。在该直接映射Cache中，块10和块2将映射到相同的Cache块。之后，在图1-14e中，ADD覆盖了Cache块2中的BL指令此时发生了冲突失效，由于目的位置已经被占用，数据不能调入Cache，除非该位置被空出来。
图1-14f中，第11块中的MOV pc,lr指令被装入Cache中第3块。最后，在图1-14g中，程序返回，第3块中的指令B XYZ被装入Cache中的第3块，替换掉以前的块。
图1-14表明，即使在一个简单的系统中，直接映射Cache中的元素可以很容易地被替换。如果上述这段代码循环执行，频繁替换Cache中的数据将降低性能。
1.3.3 组相联Cache
上一节介绍的直接映射Cache很容易实现，不需要块替换算法。然而，它不允许来自不同组但具有相同块号的块被同时缓存。全相联Cache对块存放的位置没有限制，但它需要考虑一旦Cache已满将替换哪个块。此外，容量大的全相联Cache实现起来十分昂贵。组相联（set-associative）Cache结合了上述两种Cache的优点，实现起来代价也不高。因此，它是计算机上常见的Cache组织形式。
直接映射Cache只为每个块i分配了一个位置。如果使用两个直接映射Cache并行工作，就可以使块i进入它们中的任意一个。如果使用n个直接映射Cache并行工作，就可以使块i进入n个位置中的任意一个。这就是n路组相联Cache。
在n路组相联Cache中，给定块可载入Cache中n个可能的位置。通常情况下，n的范围是2～8。图1-15展示了一个四路组相联Cache的结构，它由4个并行操作的直接映射Cache构成。在此情况下，块i可以载入4个直接映射Cache中的任意一个。因此，具有相同块号的不同块在调入Cache时产生的冲突将大大减少。这种方式称为相联（associative），因为来自处理器的块地址被并行送给每个直接映射Cache。然而，一般并不会对成千上万的存储单元同时进行搜索，而只对2～8个直接映射Cache进行并行访问。每个Cache的比较结果（即命中）将被交给或门，其输出结果表示是否有一个Cache命中。
图1-16使用组相联Cache重复了图1-14中给出的例子。两个例子基本相同，只是组相联Cache中的每个直接映射Cache只有4块，但总容量还是8块。图1-16中所示为一个二路组相联Cache，块可以保存在上面或者下面的直接映射Cache中的任意一个。
图1-16中前几步是一样的，直到图1-16e，当地址为10的ADD r1,r2,r1指令映射到第2块（组大小为4）时，该块已经被BL Adder指令占用。在相联的第2个Cache的相应位置是空闲的，因此该指令可以缓存在下面的Cache的第2块，而不必替换上面Cache中的块。图1-16f，MOV pc,lr指令的块号为3，保存在上面的Cache中。然而，当执行主存储器第3块中的B XYZ指令时，上面的Cache的第3块已被占用，故它被缓存在下面Cache的第3块中。
来自IDT应用笔记AN-07《Cache标志RAM芯片简化Cache存储器设计》的表1-1展示了Cache的组织形式对失效率的影响。该失效率已经与直接映射Cache的失效率相除进行了归一化，用来表示相对于直接映射Cache的结果。四路组相联Cache的结果要比直接映射Cache的结果好30%。进一步增加相联度对于性能的改善有限。
来自Freescale半导体公司应用笔记的图1-17展示了不同容量的Cache、使用GCC编译器时相联度和命中率之间的关系。可以看出，Cache容量比较小时，相联度是一个重要因子。当Cache容量达到256KB时，相联度的作用就不十分显著了。
1.3.4 伪相联、Victim、Annex和Trace Cache
由于Cache非常重要，针对它的改进已经进行了大量的研究，特别是针对异常行为的处理（例如，当数据被缓存、替换并再次被缓存，等等）。
在直接映射Cache基础上进行变更可以得到伪相联（pseudo-associative）Cache。当直接映射Cache发生冲突失效时，为失效的块提供一个后备位置（alternative accommodation）。下面文本框中的“流缓冲和条缓冲”部分对冲突失效和其他类型失效的自然属性进行了进一步的讨论。当直接映射Cache发生失效时，伪相联Cache根据旧的地址再计算一个新的地址来存放数据。通常情况下，新的地址是对当前地址高端的一位或几位进行取反操作得到。虽然这是规避直接映射Cache限制一种巧妙方法，但它需要在一次失效以后进行第二次Cache访问。
Victim Cache是一个小的Cache，用来保存最近被替换出Cache的项目（即遇难者（victim））。Victim Cache与原Cache并行访问，理想情况下，它是全相联的。因为它的容量非常小，可以同时搜索的块数有限，因此可以使用全相联的方式构建。
一个小的Victim Cache可以减少直接映射Cache的冲突失效，这是因为它保存的被替换块的块号与刚调入块的块号相同。Victim Cache也可以在主Cache被充满、开始出现容量失效的时候使用。Victim Cache保存了被替换出Cache的块，由于数据既没有在主Cache也没有在Victim Cache中复制，因此并没有浪费空间。
Victim Cache典型应用的例子是嵌套循环。考虑在一个循环内调用了一段程序，循环的起点与被调用程序间有一定的距离。循环开始后，程序被调用。Cache被充满了，就必须替换一些块为新的指令提供空间。当程序执行完返回循环时，Cache又需要替换一些块，依此类推。Victim Cache可以保存被替换的指令并确保它们在循环和函数调用序列被执行时命中。Jouppi针对Victim Cache的研究表明，它可以很小，但十分有效。一些基准测试表明，当使用容量少到4项的Victim Cache时，可以减少80%的冲突失效。Jouppi在研究使用Victim Cache来减少总的失效时，发现不同的基准测试程序的结果差异很大。使用容量为4项的Victim Cache时，各种基准测试程序平均会使失效率降低15%，而其中的某个基准测试程序最多会降低70%。
对Victim Cache的修改是使用选择性（selective）Victim Cache，Victim Cache中的项可能来自Cache中被替换的块或者主存储器。当新的块被预取时，采用一种预测算法来确定它是否应该被载入Cache或是Victim Cache。预测的目的是为了尽量避免Cache污染，即避免载入不会被使用的块。预测机制要求记录每块的历史状态信息。该机制使用了两位指示器：一位用来表示位于Cache中的块从来没有被访问过，另一位表示惯性（inertia）以避免在Cache和Victim Cache间进行过度的交换。
另一个由John和Subramanian提出的特殊Cache为Annex Cache。与Victim Cache一样，Annex是一个专用的Cache，但位于一级Cache的前面。即Victim Cache位于Cache的出口，而Annex Cache位于入口。Victim Cache给替换出Cache的数据第二次机会，而Annex Cache要求想进入Cache的数据证明自己的价值。
Annex Cache有助于防止很少使用的数据进入Cache，从而减少Cache污染。如果Cache为不常使用的数据提供空间而将频繁使用的数据替换出去的话，其效率肯定不高。在启动时，所有数据块以正常的方式进入Cache。最初阶段后，所有进入Cache的数据都需要通过Annex。只有在主Cache发生冲突失效且该失效块已经在Annex Cache中被访问了两次时，Annex Cache中的数据块才会被交换进入主Cache。进入Annex Cache的数据必须被证明在时间或空间局部性上存在价值。在实践中，类似Annex Cache这样的复杂Cache机制是不容易实现的，由于附加功能的复杂性，需要在本来简单的组相联Cache的基础上增加大量的控制电路。