Chapter 5. Memory

Cache

存储器\left\{ \begin{array}{l} 随机存储器RAM \left\{ \begin{matrix} 静态随机存储器SRAM \rightarrow cache \\ 动态随机存储器DRAM \rightarrow 主存 \end{matrix} \right.\\ 只读存储器ROM \end{array} \right.\notag

SRAM:信息读出后,仍保持原状态不需再生

!!! note 命中率:CPU欲访问的信息已在cache中的比率

$$
H = \frac{N_c}{N_c + N_m} \notag
$$

$$
平均访问时间 \ T_a = H_{tc} + (1-H)t_m
$$

其中$N_c$是总命中次数,$N_m$是访问主存的总次数(访问主存就是未命中)

$H_{tc}$是命中时的cache访问时间,$t_m$是未命中的主存访问时间(需要加上对cache的访问时间,因为只有访问cache了才知道有没有命中)

cache和主存的映射方式

主存包括主存块号和块内地址

cache包括块号和块内地址,cache和主存的块内地址必须相同(因为cache是主存的复制,它们的大小可以不一样,但是内部结构必须相同);如:

主存地址 = 主存块号 + 块内地址:

2^m^ 块	2^b^ 个字
主存块号	块内地址
m位	b位

cache地址 = cache块号 + cache块内地址:

2^c^ 块	2^b^ 个字
块号	块内地址
c位	b位

注意, $m \gg c$ ,主存必须远大于cache

直接映射

主存中的每一块只能放入cache的唯一位置;如:

cache行号 = 主存块号 \ \% \ cache总行数 \notag

块冲突的概率很高且空间利用率低

!!! example 若主存块号为 $13$ ,cache总行数为 $4 = 2^2$

那么计算得出

$$
\begin{align*}
cache行号 &= 13 \ \% \ 4 = 1 \\
&= 1101 \ \% \ 4 = 1
\end{align*}
$$

我们发现,==如果cache共有$2^c$行,那么主存块号的低$c$位即为对应的cache行号.==

那么我们可以进一步对主存的结构进行划分:把高 $m$ 位划分为 $t = m-c$ 和 $c$ 位,称高 $t$ 位为tag,用来确定我们这一行来自哪个块

t= m-c位	c位	b位
标记(tag)	cache行号	块内地址

同时在cache中也加上t位,表示这一行来自哪个块

全相连映射

允许主存每一个字块映射到cache块的任何一个位置

那我可以直接把主存块号作为标记位

组相连映射

把cache分为Q个大小相等的组,每个主存块可装入固定组内的任意块

cache组号 = 主存块号\ \% \ cache组数 \notag

根据直接映射的规律,我们可以得出:若cache有 $2^Q$ 组,那么主存块号的低 $Q$ 位即为对应的cache组号

m-Q位	Q位	b位
标记(tag)	组号	块内地址

!!! note 假设主存按字节编址,cache共有64行,采用四路组相连映射方式,主存块大小为32字节,所有编号都从0开始.则第2593号存储单元所在的主存块的cache组号是 ==1==

- 首先主存块大小为32字节,那么我们可以知道块内地址$2^b=32$,得到$b=5$,然后64行,四路组相连,那一共有$\frac{64}{4} = 16$组,所以$2^Q=16$,$Q=4$,所以只要把2593转为二进制,取相应位置就可以了

cache中主存块的替换算法

目的是解决cache满了的情况,把可能用不到的块移出去,新的块放进来

随机算法RAND

随机替换cache块

先进先出算法FIFO

选择最早进入的行进行替换

近期最少使用算法LRU

依据局部性原理,选择近期内长久未访问过的cache行

最不经常使用算法LFU

将一段时间内被访问次数最少的存储行替换

cache的写策略

cache写命中

全写法(写直通法,write- through)

如果CPU对cache写命中,那么我需要同时把数据写回cache和主存.缺点:会增加主存的访存次数,降低cache的效率.

因此我们加入一个“wirte buffer缓存队列”来解决这个问题.

!!! note 我并不直接往主存中写数据,而是同时向cache和write buffer中写,然后再从write buffer往主存中写数据

回写法(write back)

如果写命中了,我只把数据写入cache,而不立即写入主存.只有当块被替换时,我才把数据写回主存.

但是这样就带来一个问题:在某一时刻,我们的cache和主存中的数据是不一样的.对此我们可以给每个cache行加一个脏位:

如果脏位为0,就代表我们的cache块没被修改过.
如果为1,就代表被修改过,那么我替换的时候就要把数据写回主存.

cache写不命中

写分配法(write- allocate) + 回写法

加载主存中的块到cache中,然后更新这个cache块

非写分配法(not-write-allocate) + 全写法

只写入主存,与cache无关

Virtual Mechine

由Virtual Mechine Monitor进行管理内存,CPU和I/O
客户端跑在User Mode下