Cache

概念

数据块:Cache和主存被划分为大小相等的块,称为Cache块(行)

• Cache块数小于主存中的块数
• 每块由若干字节组成

标记:每一个Cache数据块有一个标记字段

有效位:每一组Block都有一个有效位,用于指示相应数据块是否包含有效数据

命中率:CPU欲访问的信息已在Cache中的比率称为Cache的命中率,Cache的总命中次数为\(N_c\),访问主存的总次数为\(N_m\),命中率为\(H=\frac{N_c}{N_c+N_m}\)

映射

直接映射

• Cache行号=主存块号 mod Cache总行数
• 假设Cache共有\(2^c\)行,主存有\(2^m\)块,在直接映射方式中,主存的第0块,第\(2^c\)块,第\(2^{c+1}\)块映射到Cache的第0行
• 给每个Cache行设置一个长为\(t=m-c\)的标记(tag)

直接映射的地址结构为:

标记	Cache 行号	块内地址

访存过程

1. 根据访存地址中间的c位(Cache行号)找到对应的cache行
2. 将对应Cache行中的标记和主存地址的高t位标记进行比较
3. 若相等且有效位为1,则访问Cache"命中",此时根据主存地址中低位的块内地址,在对应的Cache行中存取信息
4. 若不想等或有效位为0,则不命中,此时CPU从主存中读出该地址所在的一块信息送到对应的Cache行中,将有效位置1,并将标记设置为地址中的高t位,同时将该地址中的内容送CPU

计算

\(Cache块数=Cache容量/Block大小\)

\(主存块数=主存容量/Block大小\)

\(主存分区=主存块数/Cache块数\)

\(主存地址位数=主存块数对应位数+块内地址位置\)

image-20241113085451710

缺点:

1. 其他地方有空闲的Cache块,但不能使用

全相联映射

• 主存中的每一块都可以装入Cache中的任何位置
• 同时与所有tag进行比较,需要N个比较器
• 数据访问和标记并行执行

地址结构

标记	块内地址

访存过程

1. 将主存地址的高位标记(位数=\(log_2\)主存块数)与Cache各行的标记进行比较
2. 若有一个相等且对应有效位为1,则命中,此时根据块内地址从该Cache行中取出信息
3. 若都不想等,则不命中,此时CPU从主存中读出该地址所在的一块信息送到Cache的任意一个空闲行中,将有效位置1,并设置标记,同时将该地址中的内容送CPU

image-20241113103805490

image-20241111151042631

优点:

1. 存储空间充分利用,命中率高,灵活性

缺点:

1. 查找标记最慢

缺点:

1. 主存地址中的块地址要与Cache中所有Tag比较后,才能知晓是否不命中

组相联映射(可放到特定分组)

• 将Cache分为Q个大小相等的组,每个主存块可以装入固定组的任意一行,即组间采用直接映射,组内采用全相联映射的方式

标记	组号	块内地址

计算

image-20241113085633270

2路组相连映射--2块为1组,分4组

缺失处理

image-20241113092733659

替换处理

image-20241113092832343

替换策略

LRU(近期最少使用算法)

• LRU算法对每个位设置一个计数器(LRU替换位)
• 计数器位数与组大小相关,二路时有1位LRU位(要区分组内的计数器大小,有0,1两个数即可),四路时有2位LRU位(可以有0,1,2,3四个计数)
• 命中时,所命中的行的计数器清零,比其低的计数器加1,其余不变
• 未命中且有空闲行时,新装入的行的计数器置0,其余全加1
• 未命中且无空闲行时,计数值为\(2^{组数}-1\)(就是计数最大)的行的信息块被替换,新装入的行的计数器置0,其余全加1
• 这种计数方式保证了所有的行的计数在0到\(2^{组数}-1\)之间,并各不相同

FIFO(先进先出算法)

容易实现,但未遵循程序访问的局部性原理,最早进入的主存块可能是目前经常要用的

LFU(最不经常使用算法)

将一段时间内被访问次数最少的Cache行换出,每行也设置一个计数器,新行装入后从0开始计数,每访问1次,被访问的行计数器加1,需要替换时比较各特定行的计数值,将计数值最小的行换出

RAND(随机算法)

随机的确定替换的Cache行,实现简单

image-20241113105108759

相关计算问题

直接映射

• 主存地址空间大小,Cache地址空间大小,块大小一般为已知条件
• \(主存块数=\frac{主存地址空间大小}{块大小}=2^m\)
• \(Cache行数=\frac{Cache地址空间大小}{块大小}=2^c\)
• 主存地址结构为:

标记	Cache行号	块内地址
\(m-c\)位	\(c\)位	\(k\)位

全相联映射

• 主存地址空间大小,Cache地址空间大小,块大小一般为已知条件
• \(主存块数=\frac{主存地址空间大小}{块大小}=2^m\)
• \(Cache行数=\frac{Cache地址空间大小}{块大小}=2^c\)
• 主存地址结构为:

标记	块内地址
\(m-k\)位	\(k\)位

组相联映射

• 主存地址空间大小,Cache地址空间大小,组数,块大小一般为已知条件
• \(主存块数=\frac{主存地址空间大小}{块大小}=2^m\)
• \(Cache行数=\frac{Cache地址空间大小}{块大小}=2^c\)
• \(组数=2^r\)
• \(主存组内块数=2^{m-r}\)
• 主存地址结构为:

标记	组号	块内地址
\(m-r\)位	\(r\)位	\(k\)位

Cache总容量计算

假设某个计算机的主存地址空间大小为256MB,按字节编址,其数据Cache有8个Cache行,行长为64B

(1)若不考虑用于Cache的一致维护性位(脏位)和替换算法控制位,并且采用直接映射方式,则该数据Cache的总容量为多少?

每个Cache行对应一个标记项(包括有效位,脏位,替换算法位,标记位)

由于按字节寻址:

\(块内地址位数=\log_2(64)=6\)

\(Cache行号位数=\log_2(8)=3\)

\(标记位数=\log_2(256\times 10^{20})-6-3=19\)

主存地址空间结构为

标记	Cache行号	块内地址
19位	3位	6位

本题每行(总共8行)的存储器容量为:

有效位	标记	每行存储的数据
1bit	19bit	64B=512bit

因此:总容量为\((1+19+512)\times 8=4256\)位