缓存：初始计算机层： CPU寄存器、DRAM主存储器和磁盘存储。 由于CPU和主存储器的差逐渐变大，在CPU寄存器文件和主存储器之间出现了小的SRAM高速缓冲存储器，被称为L1高速缓存(L1高速缓存)，CPU和主存储器之间的性能差继续变大，L1高速缓存图0-1是存储器分层结构。
图0-1:内存层
图中的每一层都是下一层的缓存。 这意味着，层次的每一层都缓存来自较低层的数据。
1、缓存命中缓存未命中：缓存命中：层k 1所需数据在层k缓存，可以直接读取
缓存未命中：层k 1所需的数据不在层k中。
如果缓存未命中，则必须从存储层的下一层取出请求的块，并将新块存储在组索引位所表示的组中的缓存行中。 对于直接映射缓存，每个组只包含一行。 替换策略很简单。 用新检索到的行替换当前行。
缓存未命中的种类： 1、不强制命中：也就是说，如果第k层缓存为空，则一定不会命中。
2、碰撞未命中：假设发生未命中后，数据缓存在第k层。 如果使用随机放置的方法，这次很难找到，所以硬件通常将包含第k 1层的块限制在包含第k层的子集。 例如，如果通过执行剩余运算选择缓存位置，则在获取剩余的块编号后，相同数字的块将被缓存在同一个位置，从而导致冲突。 例如，进行mod3运算时，第k 1层块编号为4、7的数据块需要缓存。 这样的另一个不好的现象是，如果按照4、7、4、7的顺序读取数据，每次都会发生冲突，无法命中。 即使第k层有足够的空间，这种现象也称为抖动。
3、容量未命中：如果k层容量不足于缓存下需要缓存的数据，则称为容量未命中。
图1-1 :高速缓存(s、e、b、m )的一般组织。 a )缓存是缓存组的数组。 每个组包含一行或多行，每行包含有效位、某些标志位和数据块。 b )缓存的结构将m个地址位分为t个标志、s个组索引位、b个块偏移位。
考虑每个存储器地址有m位，形成M=2^m个不同地址的计算机系统。 如图1-1a所示，这样的机器的缓存被组织成具有S=2^s个缓存组(缓存集)的数组。 每个组包含e个缓存线(cache line )。 每一行由B=2^b字节的块构成，valid bit指示该行是否包含有意义的信息，tag bit是当前块的存储器地址的比特的子集，并且被存储在缓存线中缓存-主存地址映射：直接映射直接映射是最简单、最直接的映射方式。 主存储器中的每个地址对应于高速缓存中的唯一一行。 因为主存储器的容量远大于Cache存储器，所以主存储器中的许多地址都映射到同一个Cache行。
图2-1 :主存与Cache的直接映射关系。
直接映射Cache是一种简单的解决方案，但此设计允许每个主存储块只存储Cache中的特定行。 如果程序同时使用对应于Cache同一行的两个主存储块，则会发生冲突，冲突导致Cache行频繁转换。 这种直接映射引起的Cache存储器内的软件冲突称为thrashing问题。
组关联映射：为了减轻抖动问题，一些Cache使用组关联映射策略。 与组相关联的地址映射和转换将主存和Cache按相同大小划分为组(set )，每组由相同行数组成。
因为主存的容量比Cache的容量大得多，所以主存的组数比Cache的组数多。 采用从主存组到Cache组直接映射的方式。 在主存中组与Cache中组之间建立空间映射方式后，在两组对应组内部采用全相相关映射方式。
在ARM中，采用了与组相关联的地址映射和转换方式。 如果Cache的行大小为2L，则同一行中每个地址的bit[31L] ) ]将相同。 如果Cache中的组大小(每个组中包含的行数)为2S，则虚拟地址位bit[L SL] ) ]用于选择Cache中的组。
图2-2 Cache与主内存组的关联
具有相同组索引的Cache行称为组关联(set associative )。 主存储器中的程序或代码段可以分配给Cache中的组，而不影响程序的执行。 这意味着在Cache行中存储数据或代码的操作不影响程序的执行。
全连通映射：随着Cache控制器连通度的提高，碰撞的可能性减少。 理想的目标是尽可能提高组的相关性，以便主存储地址可以映射到任何Cache行。 这样的Cache被称为全相关Cache。 但是，随着关联度的提高，与之相应的硬件复杂度也在提高。 硬件设计者增强高速缓存相关性的一种方式在于使用内容地址寄存器CAM(Content Addressable Memory )。
CAM使用一组比较器将输入的标签地址与存储在每个有效Cache行中的标签位进行比较。 CAM的工作方式与RAM相反； RAM在得到地址后给出数据； CAM在检测出给定的数据值在存储器中后，给出该数据的地址。 使用CAM，可以同时比较更多地址的标记位，从而可以
增加了可以包含在一个组中的Cache行数。在ARM920T和ARM940T存储器核中，ARM使用了CAM来定位地址中的标签域。ARM920T和ARM940T中的Cache是64组组相联的。图6 所示为ARM940T的Cache结构图。Cache控制器把地址标签域作为CAM的输入，它的输出选择了包含有效Cache行的组。
图2-3 ARM940T64路组相联Cache
访问地址的标签部分被作为4个CAM的输入，输入标签的同时与存储在64组中的所有Cache标签比较。如果有一个匹配，那么数据就由Cache寄存器提供；如果没有匹配，存储器就会产生一个失效（misss）信号。
控制器使用组索引位（set index）在4个CAM中选择一个。被选中的CAM会在Cache存储器中选择一个Cache行，该地址的数据索引部分（data index）在该Cache行中选择出所需的字、半字或者字节。
3、替换算法：当使用全相联和组 相联的时候，如果 要获取的数据不在Cache中，从主存中读取后，需要将数据写入缓存Cache，如果Cache中已经有数据需要将Cache中的数据替换出去，那替换策略该如何呢。
先进先出算法（FIFO）：让最先进入到内存块的数据先退出。这种方式并不能很好的体现程序的局部性原理。
近期最少使用算法（LRU）：在最近的一段时间内，我们使用的最少的块。
参考文献：《CSAPP第3版》