计算机组成原理 408-3-5&6

# Cache 的基本概念和原理

# 存储系统存在问题

• 双端口 RAM、多模块存储器提高存储器的工作速度
• 优化后速度与 CPU 差距依然很大 -> 更高速的存储单元设计 -> 存储器价格上升，容量下降
• 程序访问的局部性原理 -> 存储体系的改善 "Cache - 主存" 层次

注：实际上，Cache 被集成在 CPU 内部，Cache 用 SRAM 实现，速度快，成本高

# 局部性原理

• 空间局部性：在最近的未来要用到的信息 (指令和数据)，很可能与现在正在使用的信息在存储空间上是邻近的
  • Eg：数组元素、顺序执行的指令代码
• 时间局部性：在最近的未来要用到的信息，很可能是现在正在使用的信息
  • Eg：循环结构的指令代码

基于局部性原理，可以把 CPU 目前访问的地址 "周围" 的部分数据放到 Cache 中

# 性能分析

设$t_c$ 为访问一次 Cache 所需时间，$t_m$ 为访问一次主存所需时间

命中率 H：CPU 欲访问的信息已在 Cache 中的比率

缺失 (未命中) 率 M=1-H

Cache - 主存 系统的平均访问时间 t 为：$t=Ht_c+(1-H)(t_c+t_m)$(先访问 Cache，若 Cache 未命中再访问主存)

或者$t=Ht_c+(1-H)t_m$ (同时访问 Cache 和主存，若 Cache 命中则立即停止访问主存)

# 例题：

假设 Cache 的速度是主存的 5 倍，且 Cache 的命中率为 95%，则采用 Cache 后，存储器的性能提高多少？(设 Cache 和主存同时被访问，若 Cache 命中则中断访问主存)？

设 Cache 的存取周期为 t，则主存的存取周期为 5t

• 若 Cache 和主存同时被访问，命中时访问时间为 t，未命中时，访问时间为 5t，平均访问时间为$0.95t+0.05*5t=1.2t$，故性能为原来的$\dfrac{5t}{1.2t}\approx4.17$ 倍
• 若先访问 Cache 再访问主存，命中时访问时间为 t，未命中时，访问时间为 6t，平均访问时间为$T_a=0.95t+0.05*6t=1.25t$，故性能为原来的$\dfrac{5t}{1.25t}=4$ 倍

# 有待解决的问题

基于局部性原理，如何界定周围？

• 将主存的存储空间分块，如：每 1KB 一块。主存与 Cache 之间以块为单位进行数据交换

• 注：操作系统中，通常将主存的 "一个块" 也称为 "一个页 / 页面 / 页框"

• Cache 中的块也称行

• 注：每次被访问的主存块，一定会被立即调入 Cache

# Cache 与主存的映射方式

区分 Cache 中存放哪个块：

给每个 Cache 块增加一个标记与有效位，当有效位为 1 时，标记中指向的即为主存块，当有效位为 0 时，标记无效

# 全相联映射

主存块可以放在 Cache 的任意位置

假设某个计算机的主存地址空间大小为 256MB，按字节编址，其数据 Cache 有 8 个 Cache 行 (即 Cache 块，与主存块大小相等)，行长为 64B

主存块号 (22 位)+ 块内地址 (6 位)

例：CPU 访问 1...1101 (主存块号) 001110 (块内地址)

• 主存地址的前 22 位，对比 Cache 中所有块的标记；
• 若标记匹配且有效位为 1，则 Cache 命中，访问块内地址位 001110 的单元
• 若未命中或有效位为 0，则正常访问主存

# 直接映射

每个主存块只能放在一个特定的位置：Cache 块号 = 主存块号 % Cache 总块数

假设某个计算机的主存地址空间大小为 256MB，按字节编址，其数据 Cache 有 8 个 Cache 行 (即 Cache 块，与主存块大小相等)，行长为 64B

主存块号 (22 位)+ 块内地址 (6 位)

主存块在 Cache 中的位置 = 主存块号 % Cache 总块数

优化：若 Cache 总块数为$2^n$，则主存块号末尾 n 位直接反映它在 Cache 中的位置，将主存块号的其余位作为标记即可

缺点：其他地方有空闲 Cache 块，但是有些主存块无法使用空闲 Cache 块

例：CPU 访问 1...1101 (主存块号) 001110 (块内地址)

• 根据主存块号后三位确定 Cache 行
• 若主存块号的前 19 位与 Cache 标记匹配且有效位为 1，则 Cache 命中，访问块内地址为 001110 的单元
• 若未命中或有效位为 0，则正常访问主存

# 组相联映射

Cache 块分为若干组，每个主存块可放到特定分组的任意一个位置，组号 = 主存块号 % 分组数

假设某个计算机的主存地址空间大小为 256MB，按字节编址，其数据 Cache 有 8 个 Cache 行 (即 Cache 块，与主存块大小相等)，行长为 64B

主存块号 (22 位)+ 块内地址 (6 位)

优化：若分组数为$2^n$，则主存块号末尾 n 位直接反映分组组数，将主存块号其余位作为标记

例：假设使用了 2 路组相联映射 ——2 块为一组，分四组；CPU 访问 1...1101 (主存块号) 001110 (块内地址)

• 根据主存块号的后 2 位确定所属分组号
• 若主存块号的前 20 位与分组内的某个标记匹配且有效位为 1，则 Cache 命中，访问块内地址为 001110 的单元
• 若未命中或有效位为 0，则正常访问主存

# Cache 的替换算法

全相联映射：Cache 完全满了才需要替换，需要在全局中选择替换哪一块

直接映射：如果对应位置非空，则毫无选择地直接替换

组相联映射：分组内满了才需要替换，需要在分组内选择替换哪一块

# 随机算法 (RAND)

若 Cache 已满，则随机选择一块替换

随机算法 —— 实现简单，但完全没有考虑到局部性原理，命中率低，实际效果很不稳定

# 先进先出算法 (FIFO)

若 Cache 已满，则替换最先被调入 Cache 的块

先进先出算法 —— 实现简单，最开始按 #0#1#2#3 放入 Cache，之后轮流替换 #0#1#2#3FIFO 依然没考虑局部性原理，最先被调入 Cache 的块也有可能是被最频繁访问的

抖动现象：频繁的换入传出现象 (刚被替换的块很快又被调入)

# 近期最少使用 (LRU)

为每一个 Cache 块设置一个计数器，用于记录每个 Cache 块已经有多久没有被访问了。当 Cache 满后，替换计数器最大的

• 命中时，所命中的行的计数器清零，比其低的计数器加 1，其余不变
• 未命中且还有空闲行时，新装入的行计数器置 0，其余非空闲行全加 1
• 未命中且无空闲行时，计数器最大的行的信息块被淘汰，新装行的块的计数器置零，其余全加 1

Cache 块的总数 =$2^n$，则计数器只需 n 位。且 Cache 装满后所有计数器的值一定不重复

LRU 算法 —— 基于局部性原理，近期被访问过的主存储块，在不久的将来也很有可能被再次访问，因此淘汰最久没被访问过的块是合理的。LRU 算法的实际运行效果优秀，Cache 命中率高

若频繁访问的主存快数量 > Cache 行的数量，则有可能发生 "抖动"

# 最近不经常使用 (LFU)

为每一个 Cache 块设置一个计数器，用于记录每个 Cache 块被访问过几次。当 Cache 满后，替换计数器最小的

新调入的块计数器为 0，之后每被访问一次计数器 + 1。需要替换时，选择计数器最小的一行

若有多个计数器最小的行，可按行号递增或 FIFO 策略进行选择

LFU 算法 —— 曾经被经常访问的主存块在未来不一定会用到 (如：微信视频聊天相关块)，并没有很好地遵循局部性原理，因此实际运行效果不如 LRU

# Cache 的写策略

# 写命中

• 写回法
  • 当 CPU 对 Cache 命中时，只修改 Cache 的内容，而不立即写入主存，只有当此块被换出时才写回主存
  • 未被修改的块不必写回，设置脏位表示是否被修改
  • 减少了访存次数，但存在数据不一致的隐患
• 全写法
  • 当 CPU 对 Cache 命中时，必须把数据同时写入 Cache 和主存，一般使用写缓冲
  • Cache 块被替换时无需写回
  • 访存次数增加，速度变慢，但更能保证数据一致性
  • 写缓冲：SRAM 实现的 FIFO 队列 (在专门的控制电路控制下逐一写回)
  • 使用写缓冲，CPU 写的速度很快，若写操作不频繁，则效果很好。若写操作很频繁，可能会因为写缓冲饱和而发生阻塞

# 写不命中

• 写分配法
  • 当 CPU 对 Cache 写不命中时，把主存中的块调入 Cache，在 Cache 中修改。通常搭配写回法使用
• 非写分配法
  • 当 CPU 对 Cache 写不命中时只写入主存，不调入 Cache。搭配全写法使用
  • 只有读未命中时才调入 Cache

# 多级 Cache

现代计算机常采用多级 Cache

• 离 CPU 越近的速度越快，容量越小
• 离 CPU 越远的速度越慢，容量越大
• 各级 Cache 之间常采用 "全写法 + 非写分配法"
• Cache - 主存之间常采用 "写回法 + 写分配法"

# 页式存储器

4KB 的程序被分为 4 个页，每个页面的大小和物理块的大小相同

页式存储系统：一个程序 (进程) 在逻辑上被分为了若干个大小相等的 "页面"，"页面" 大小与 "块" 的大小相同。每个页面可以离散地放入不同的主存块中。

逻辑地址 (虚地址)：程序员视角看到的地址 (逻辑地址 = 逻辑页号 + 页内地址)

物理地址 (实地址)：实际在主存中的地址

页表 (数据在主存中)：将逻辑页号映射为物理主存块号

CPU 执行的机器指令中，使用的是逻辑地址，因此需要页表将逻辑地址转为物理地址

页表作用：记录每个逻辑页面存放在哪个主存块中

地址变换过程：

• 将逻辑地址拆分为逻辑页号 + 页内地址
• 逻辑页号送入页表基址寄存器 (指明了页表在主存中的存放地址)，根据页表和逻辑页号获取主存块号
• 主存块号愚页内地址成为物理地址去访问主存
• 将近期访问的页表项放入更高速的存储器，可加快地址变换的速度

地址变换过程 (加入快表 (TLB))：

• 将逻辑地址拆分为逻辑页号 + 页内地址
• 逻辑页号先在快表内查询，若命中，直接得到物理地址，若未命中，走上面正常地址变换过程
• 注意区别：快表中存储的是页表项的副本，Cache 中存储的是主存块的副本
• 快表是一种 "相联存储器"，可以按内容寻访

# 虚拟存储器

该部分内容详细请看操作系统

# 页式虚拟存储器

操作系统将程序分为页，新页表如下：

逻辑页号 + 主存块号 + 外存块号 + 有效位 + 访问位 + 脏位

有效位为 1 时，表示该页已经被调入内存，反之则没有

外存块号即将外存分块后的块号

访问位是为了实现页面替换增加的，访问位即一段时间内每一个页面被访问了多少次，依据此可以实现 LFU 算法

脏位即该页面是否有数据修改

操作系统决定哪些页面调入主存，硬件决定哪些主存调入 Cache

# 段式存储器

段式存储器 —— 按照功能模块拆分

• 其余部分与页式存储器相似，只是页被替换成了段

段页式存储器 —— 按照功能模块划分，再将各个段分页：

• 把程序按逻辑结构分段，每段再划分为固定大小的页
• 主存空间也划分为大小相等的页
• 程序对主存的调入、调出仍以页为基本传送单位
• 每个程序对应一个段表，每段对应一个页表
• 虚拟地址 = 段号 + 段内页号 + 页内地址