目录传送门

4.9 Cache地址映射与变换方法

一、主存与Cache地址映射概述

CPU基于地址访问主存，引入cache之后，又需要凭借相联存储器判断要访问的内容是否在cache中；

现在有一个问题， 主存中的数据如何映射到cache中才能够实现基于相联存储器的快速查找？

本节将介绍三种常见的映射方式：

• 全相联 (fully-associated)
• 直接相联 (direct mapped)
• 组相联 (set-associated)

不同的映射方式，主存数据往cache中搬迁的规则和方法都不同；

二、全相联映射的工作原理

(将地址映射成块号 + 块内地址, 将块号作为比较的标记)

首先要对主存分块，对cache分行，两者的大小一致；

分块后，将主存中原来一维的地址映射成二维的地址；（块号 + 块内地址）

例如：

设每块4个字，主存大小为1024个字,则第61个字的主存地址为:$00001111, 01$(块号 块内地址)

全相联映射: 主存的数据块可映射到Cache任意行, 同时将该数据块地址对应到行标记的存储体中保存。

具体流程：

• CPU获得一个主存地址之后将其剥离出标记部分和块内偏移地址；

• 然后将内存地址的标记与cache中所有行的标记放到多路并发比较电路中进行比较；（之所以要和所有行的标记进行比较是因为主存数据块往cache中搬迁的时候，可能放在cache中的任意一行）

• 如果块号标记命中，块内偏移地址就从命中的cache行中剥离出具体要访问的字送给CPU；

• 如果块号标记没命中，则会根据CPU获得的原始地址再去访问主存，同时将未命中的数据块搬入cache中；

全相联映射的特点：

• Cache利用率高 （主存中数据块可以映射到cache中任意行，所以利用率高）

• 块冲突率低（只要cache中有空行，都不会发生冲突，进而需要页面调度）

• 淘汰算法复杂（由于要比对所有行，所以算法和硬件电路比较复杂）

全相联映射适合小容量cache；

三、直接映射的工作原理

(每一个数据块对应cache中特定行，将区号作为比较的标记)

与全相联类似，直接映射也要主存分块，对cache分行，两者的大小一致；

不同的是， 主存分块后还要以cache行数作为标准进行分区；

图中的cache共有4行， 因此还要对主存每4个块为一个区进行分区；（每一个区的大小和cache的大小对应）
这样就将原来内存中一维的地址变成了三维;（区号,区内块号,块内地址）

例如：

设每块4个字, 主存大小为1024个字, Cache分为4行, 第61个字的主存地址为:$000011, 11, 01$ (区号,区内块号,块内地址)

直接映射算法: Cache共n行,主存第j块号映射到Cache的行号为:$ i = j \\ mod \\ n $；
即主存的数据块映射到Cache特定行;

具体流程：

• CPU要访问的地址被分成了三维的结构（区号 + 区内块号 + 块内地址），在cache中查找时直接根据区内块号去查找特定行；

• 由于行是特定的，因此地址比较器只需要比较访问地址的标记和指定行的标记即可；

• 如果命中，则根据块内偏移地址在指定行中找CPU要访问的字；

• 如果未命中，则再次访问主存，并将对应地址所在的数据块搬到cache的特定行中；

直接映射的特点：

• Cache利用率低 （因为由于特定的映射规则，cache中空行可能不能被完全利用）

• 块冲突率高

• 淘汰算法简单（因为每次比较的都是特定行）

直接映射适合大容量cache；

四、组相联映射的工作原理

组相联映射也要对主存分块，对cache分行，两者的大小一致
除此之外，还要对cache分组（每组中包含k行），本例中假设$k = 4$；
主存分块后还将以Cache组数为标准进行分组;

图中的cache由于只有8行，因此只能分为两组；
主存中也要根据cache中的组数分组，每两个数据块为一组；
这样内存地址从一维变成了三维；（主存组号 + 组内块号 + 块内地址）
组内块号在映射时其实是指映射到cache中的哪一组，因此组内块号等价于cache组号；

例如：

设每块4个字，主存大小为1024个字，Cache分为2组,第61个字的主存地址为:$0000111, 1, 01 $(主存组号, Cache组号，块内地址)

组相联映射算法:
Cache共n组，主存第j块号映射到Cache的组号为: $i = j \\ mod \\ n$；
即主存的数据块映射到Cache特定组的任意行；
（由于组相联指定了特定组而未指定特定行，因此组相联兼有全相联和直接映射的优点）

具体流程：

• 将CPU要访问的地址分成三维的结构（主存组号 + 组内块号 + 块内地址）

• 如果主存的数据块在cache中，那该地址只能在cache中特定组中的某一行；因此多路并发比较器比较的是特定组中所有行的主存组号；

• 如果命中，根据块内偏移地址在特定组中的某一行找到对应的字；

• 如果不命中，则访问主存，并将该字所在数据块搬到特定组中；

组相联映射的兼有全相联和直接映射的优点；
随着k取值的不同，组相联可以退化成全相联和直接映射；
组相联适合中容量的cache；