Cache通常由相联存储器实现。相联存储器的每一个存储块都具有额外的存储信息，称为标签(Tag)。当访问相联存储器时，将地址和每一个标签同时进行比较，从而对标签相同的存储块进行访问。Cache的3种基本结构如下：

全相联Cache

在全相联Cache中，存储的块与块之间，以及存储顺序或保存的存储器地址之间没有直接的关系。程序可以访问很多的子程序、堆栈和段，而它们是位于主存储器的不同部位上。

因此，Cache保存着很多互不相关的数据块，Cache必须对每个块和块自身的地址加以存储。当请求数据时，Cache控制器要把请求地址同所有地址加以比较，进行确认。

这种Cache结构的主要优点是，它能够在给定的时间内去存储主存器中的不同的块，命中率高；缺点是每一次请求数据同Cache中的地址进行比较需要相当的时间，速度较慢。


直接映像Cache

直接映像Cache不同于全相联Cache，地址仅需比较一次。

在直接映像Cache中，由于每个主存储器的块在Cache中仅存在一个位置，因而把地址的比较次数减少为一次。其做法是，为Cache中的每个块位置分配一个索引字段，用Tag字段区分存放在Cache位置上的不同的块。

单路直接映像把主存储器分成若干页，主存储器的每一页与Cache存储器的大小相同，匹配的主存储器的偏移量可以直接映像为Cache偏移量。Cache的Tag存储器(偏移量)保存着主存储器的页地址(页号)。

以上可以看出，直接映像Cache优于全相联Cache，能进行快速查找，其缺点是当主存储器的组之间做频繁调用时，Cache控制器必须做多次转换。

组相联Cache

组相联Cache是介于全相联Cache和直接映像Cache之间的一种结构。这种类型的Cache使用了几组直接映像的块，对于某一个给定的索引号，可以允许有几个块位置，因而可以增加命中率和系统效率。

Cache与DRAM存取的一致性

在CPU与主存之间增加了Cache之后，便存在数据在CPU和Cache及主存之间如何存取的问题。读写各有2种方式。

贯穿读出式(Look Through)

该方式将Cache隔在CPU与主存之间，CPU对主存的所有数据请求都首先送到Cache，由Cache自行在自身查找。如果命中，则切断CPU对主存的请求，并将数据送出；不命中，则将数据请求传给主存。

该方法的优点是降低了CPU对主存的请求次数，缺点是延迟了CPU对主存的访问时间。

旁路读出式(Look Aside)

在 这种方式中，CPU发出数据请求时，并不是单通道地穿过Cache，而是向Cache和主存同时发出请求。由于Cache速度更快，如果命中，则 Cache在将数据回送给CPU的同时，还来得及中断CPU对主存的请求；不命中，则Cache不做任何动作，由CPU直接访问主存。

它的优点是没有时间延迟，缺点是每次CPU对主存的访问都存在，这样，就占用了一部分总线时间。

写穿式(Write Through)

任一从CPU发出的写信号送到Cache的同时，也写入主存，以保证主存的数据能同步地更新。

它的优点是操作简单，但由于主存的慢速，降低了系统的写速度并占用了总线的时间。

回写式(Copy Back)

为了克服贯穿式中每次数据写入时都要访问主存，从而导致系统写速度降低并占用总线时间的弊病，尽量减少对主存的访问次数，又有了回写式。

它 是这样工作的：数据一般只写到Cache，这样有可能出现Cache中的数据得到更新而主存中的数据不变(数据陈旧)的情况。但此时可在Cache 中设一标志地址及数据陈旧的信息，只有当Cache中的数据被再次更改时，才将原更新的数据写入主存相应的单元中，然后再接受再次更新的数据。这样保证了 Cache和主存中的数据不致产生冲突。

Cache 是用来对内存数据的缓存。CPU 要访问的数据在Cache中有缓存，称为“命中” (Hit)，反之则称为“缺失” (Miss)

CPU 访问它的速度介于寄存器与内存之间（数量级的差别）。实现 Cache 的花费介于寄存器与内存之间。

现在 CPU 的 Cache 又被细分了几层，常见的有 L1 Cache, L2 Cache, L3 Cache，其读写延迟依次增加，实现的成本依次降低。

现代系统采用从 Register —> L1 Cache —> L2 Cache —> L3 Cache —> Memory —> Mass storage
的层次结构，是为解决性能与价格矛盾所采用的折中设计。

引入 Cache 的理论基础是程序局部性原理，包括时间局部性和空间局部性。即最近被CPU访问的数据，短期内 CPU
还要访问（时间）；被 CPU 访问的数据附近的数据，CPU 短期内还要访问（空间）。因此如果将刚刚访问过的数据缓存在 Cache中，那下次访问时，可以直接从Cache中取，其速度可以得到数量级的提高。

2. 结构

2.1 Cache 行

Cache 以行大小(Line size)为单位分成若干个行。行 (Line) 是 Cache 的数据存储和管理单元。一个典型的 Cache 行结构为：

http://www.tektalk.org/wp-content/uploads/2011/04/cache.line_.png

其由 Tag 域、Status 域和数据域组成，

Tag 域存放该行数据对应地址的高位。CPU 在索引后，用相应地址与组内所有行的 Tag 相比较，以之区分具体的行。

数据域能容纳的字节数是为行大小 (Line Size)，其为 Cache 与内存之间数据交换的单位。

Status 域则为一些控制位信息（如Valid, Lock 以及Parity check 位等等），不同的Cache 类型，不同的 Cache 实现 Status 域稍有不同，具体的可以参考相应 CPU 手册。

2.2 相联方式

2.2.1 组相联

通俗地讲就是 Cache 行的分组，比如 4 路组相联，就是 4 行一组，4 行一组。。。。。。

比如 32KB 的 4 路组相联 Cache，行大小为 16Bytes 的话，他就有 32*1024/(16 * 4)= 512 组

CPU 访问组相联 Cache 时，就先用地址索引到组，然后组内同时匹配 Tag，进行路选。一个典型的组相联 Cache如下：

http://www.tektalk.org/wp-content/uploads/2011/04/cache.way_.set_.png

内存逻辑上也按 Cache 行大小分块，按地址由低向高，依次编号。因此 Cache 与内存就会有个映射问题，如：第四个内存行中的数据被CPU访问时，该行将缓存于 Cache 中的哪一行？

组相联的 Cache 是先索引组，其规则为： Cache 组号 = 内存行号 % Cache 总组数

http://www.tektalk.org/wp-content/uploads/2011/04/c2.png

对于上图这个只有 2 个组的 Cache，假设其行大小为 16Bytes，这个组索引的过程，实际上就是用地址的第 5 位(ADDR[4]) 索引的过程，0 就在第一组，1 就在第二组。地址的低 4 位用于行内索引数据 (ADDR[3:0])

尔后，内存行可以映射到该组内的任意行上。缓存数据时，有空占空，如组内所有行被占用，则使用替换算法(LRU,Random, FIFO, LFU)替换掉一行。

2.2.2 直接相联

略. 或可参阅 The MIPS Cache Architecture 的相关部分

2.2.3 全相联

略. 或可参阅 The MIPS Cache Architecture 的相关部分

3. 组相联工作方式

K 路组相联 Cache 的通常工作方式是：先用物理地址或虚拟地址索引组，然后用物理地址 (PA) 或虚拟地址 (VA) 同
时与组内K 行之 Tag 域同时匹配，有匹配则为命中 (Hit)，尔后将命中的行中相应的字传给 Register。

以上述 32KB ，4 路组相联，行大小为 16Bytes 的 Cache 为例，正常工作时其对地址的划分如下所示：

http://www.tektalk.org/wp-content/uploads/2011/04/addr.split_.png

Addr[12:4] 用来索引组，9 bit 可索引 512 组
Addr[3:0] 用来行内索引字节，2^4 = 16 Bytes

VA 索引，PA 匹配 Cache 之工作方式图：

http://www.tektalk.org/wp-content/uploads/2011/04/vipt.match.png

4. 乱弹

在 OS 层面上，我们还有分页的概念，物理内存被分为若干个 Page Frame，其大小以 4KB 始。对 4KB 页大小的系统，其地址的低 12 位被用来索引页内数据

若系统采用 4KB 的 PAGE_SIZE，则第一个 Page Frame 总是会被索引到 cache 的前 256 组，第二个 Page Frame会被索引到 cache 的后 256 组，第三个又会到 cache 的前 256 组。。。。。。（给在前 256 的涂红色，给后 256的涂黑色） 倘若系统在分别 PF 的时候，大多数的都跑到前 256 组去了，那就杯具了。在频繁换页的系统中，Cache的路数总是一定，用完了组内的行，系统就会复用一些行，原来的数据也就被替换，再访问时，就是 cache miss，性能就下来。那如何让系统在 “OS层面上物理页面（Page）的分配能够比较均匀的落在CPU层面上的SET中“？

通俗地说，就是让 OS 在分配页面的时候，让红色的页和黑色的页一样多。这个应该就是 Page Coloring，不知道对不对。

用颜色位更形式化地说：

作为一个理解的便利，请各位看官看看地址的组索引位和行内索引位所表示的空间大小是多少？ 2^13 ＝ 8KB，这个值正是 Cache 一路 (Way Array)的大小： 32KB/4 = 8KB (Way_Size)

因此拿到一个 Cache 在判断系统的 Color 位时，可以借助一个 Way Array 的概念，一路 Cache 的大小就是地址用来索引的低位空间，相当于用地址的低位访问 Cache 的一路内部存储

当 Way_Size > PAGE_SIZE 时，即 log2(Way_Size) > log2(PAGE_SIZE)， 则用于索引一路 Cache 的地址低位较用于页内偏移的低位多了 log2(Way_Size) – log2(PAGE_SIZE)，为了分析的方便，往往将这个多出的位称为颜色位
(color bit)。对于上述的 Cache，若系统采用 4KB 的 PAGE_SIZE，则Addr[12] 即为颜色位。则 OS 在分配页时，保证每种颜色的页一样多即可。如：Addr[13:12] 为颜色位的情形，00, 01, 10, 11 一样多即可。

若 log2(Way_Size) <= log2(PAGE_SIZE)，则数据可以很均衡地进入 Cache 没有谈论的必要的，但可以作为另外一个思路，即：提高系统的 Page Size

5. 摘要

Way_Size ＝ Cache_Size / Ways

当 log2(Way_Size) > log2(PAGE_SIZE) 时，系统具有“颜色位”，其影响为：

1. 用 VA 索引，PA 匹配的 Cache，会存在 Cache alias 问题
2. 用 PA 索引，PA 匹配的 Cache，可以榨取更高的 Cache 命中率；方法可以用 Page Coloring，或者可以提高PAGE_SIZE以消除颜色位。

个人觉得在可能的前提下，提高 PAGE SIZE 比较靠谱，大页的影响，除了在 Cache 上外，在 RISC 的 CPU 上，还能提高 TLB 的命中效率