假设我们现在有一个8位的cache

一个32位的存储器

几乎所有的直接映射cache都使用以下的映射方法：

\( (块地址) mod (cache中的块数) \)

所以我们只需要取存储器后面3位来映射到高速缓存

如图所示

由于一个cache可以对应主存中多个不同的地址，如何知道cache中的数据项是否是所请求的字呢？我们在cache中增加一组标记（tag），标记中包含了地址信息，这些地址信息可以用来判断cache中的字是否就是所请求的字。标记只需包含地址的高位，也就是没有用来检索cache的那些位。如上图所示，我们只需记录存储器的高两位，因为低三位已经用来选择cache中的块。

我们还需要一种方法来判断cache块中确实没有包含有效信息，当一个处理器启动时，cache中没有数据，标记域中的值没有意义。甚至在执行了一些指令后，cache中的一些块依然为空，如上图没有上色的高速缓存所示，在cache中，这些块的标记应该被忽略。最常用的方法是增加一个有效位来标识一个块是否含有一个有效地址。如果该位没有被设置，则不能使用该块中的内容。

由上所知，一个cache line的结构如下

接下来我们

上面我们所讲的映射称为直接映射方法，

直接匹配缓存尽管在电路逻辑上十分简单，但是存在显著的冲突问题。由于多个不同的内存块仅共享一个缓存块，一旦发生缓存失效就必须将缓存块的当前内容清除出去。这种做法不但因为频繁的更换缓存内容造成了大量延迟，而且未能有效利用程序运行期所具有的时间局部性。

组相联（Set Associativity）是解决这一问题的主要办法。使用组相联的缓存把存储空间组织成多个组，每个组有若干数据块。通过建立内存数据和组索引的对应关系，一个内存块可以被载入到对应组内的任一数据块上。

还有一个全相联方法，这种缓存意味着内存中的数据块可以被放置到缓存的任意区域。这种相联完全免去了索引的使用，而直接通过在整个缓存空间上匹配标签进行查找。 由于这样的查找造成的电路延迟最长，因此仅在特殊场合，如缓存极小时，才会使用。

直接映射法我们已经讲过，组相联方法其实也很好理解，就是将原本的cache中的块数改为现在的set数

\( (块地址) mod (cache中的set数) \)

一个set中有几个cache line就称为几路组相联，如上图称为二路组相联，一个set中有四个cache line称为四路组相联

如上图所示，在二路组相联下，block为12的存在set0下两个cache line的任意一个，同样的，4、16、20、24的block也可以存在set0下两个cache line的任意一个，在通过索引定位到对应组之后，必须进一步地与所有缓存块的标签值进行匹配，以确定查找是否命中。这在一定程度上增加了电路复杂性，因此会导致查找速度有所降低。

block包含四个部分Block address,Tag,Index和Block offset

Tag作为标记，和cache line中的标记域值相同，index指向所在set，Block offset代表偏移量

检查index其实是多余的，因为用block address其实就可以算出所在set。通过block offset偏移量也可以找到cache中的数据偏移

由上图可知，先有程序计数器给出虚拟地址，二路组相联时，先通过index获取所在set，虚拟地址的tag会跟set中的每一个cache line中的tag进行比较，当valid域有效并且cache line的tag和virtual address的tag相同时，再通过block offset读取后面的data字段，最后传入cpu的data in。当缓存命中时这四步花费2个时钟周期

当缓存未命中时，缓存给处理器发送信号表示数据不可用，所以处理器会从更低一级存储获取数据，对于块的前 8 个字节，延迟是 7 个时钟周期，然后对于块的其余部分，每 8 个字节需要 2 个时钟周期(the latency is 7 clock cycles to the first 8 bytes of the block, and then 2 clock cycles per 8 bytes for the rest of the block)，所以当缓存未命中时代价会很高。因为是二路组相联，所以处理器需要选择哪一个block需要替换，一般有三种替换策略：随机、LRU（最近最少使用）、FIFO（先进先出）。我们后面再讲，大部分使用LRU或者LRU近似算法

本文中使用写回测量，不能将旧块随便丢弃。直写和写回是缓存的两种策略，简单说，直写就是信息被写入缓存中的块和低级内存中的块(the information is written to both the block in cache and to the block in lower-level memory)，写回指信息仅写入缓存中的块。 修改后的缓存块仅在被替换时才写入主存(the information is written only to the block in the cache. the modified cache block is written to main memory only when it is replace)，系统使用1个脏位来标记一个被写入的块，如果”victim“被修改，其数据和地址将被送到victim buffer(If the “victim” was modified, its data and address are sent to the victim buffer)