存储器

存储器的分类

1. 按在计算机中的作用（层次）分类

主存储器（内存）：

用来存放当前运行的程序和数据，CPU可以直接访问。
包括高速缓冲存储器（Cache）和辅助存储器交换数据。
特点：容量较小、存取速度快、价格较高。

辅助存储器（外存）：

用来存放暂时不使用的程序和数据。
需经主存才能被CPU访问。
特点：容量大、存取速度慢、单位成本低。

高速缓冲存储器（Cache）：

位于主存和CPU之间，用来存放当前CPU经常使用的指令和数据。
特点：存取速度快但容量小、价格高，常做在CPU中。

2. 按存储介质分类

磁表面存储器： 如磁盘、磁带。
磁芯存储器。
半导体存储器： 如MOS型存储器、双极型存储器。
光存储器： 如光盘。

3. 按存取方式分类

随机存储器（RAM）：

存储单元可随机存取，读写方便，主要用于主存和高速缓冲存储器。
分为静态RAM和动态RAM。

只读存储器（ROM）：

内容只能读取不能写入，存储内容不会丢失。
常用于存放固定程序、数据和字符字库。
ROM存储器可分为：可反复写的、不能修改的等。

（串行）顺序访问存储器：

存取时需按固定顺序进行（如磁带）。
特点：存取速度较慢，数据存储密度高，存取时间长。

4. 按信息的可保留性分类

易失性存储器：

断电后，存储信息会立即消失的存储器，称为易失性存储器。
例如：RAM。

非易失性存储器：

断电后信息仍然能够保持的存储器，称为非易失性存储器。
例如：ROM、磁表面存储器和光存储器。

破坏性读出存储器：

若某个存储单元所存储的信息在被读取时被破坏，则称为破坏性读出。
若信息在读取时未被破坏，则称为非破坏性读出。

破坏性读出性能存储器：

每次读取操作后，必须紧接着一个再生操作，以便恢复被破坏的信息。

存储器的性能指标

1. 存储容量

存储容量 = 存储字数 × 字长（如 1M × 8 位）。
单位换算：1B（字节）= 8b（位，bit）。
存储字数表示存储器的地址空间大小，字长表示一次存取操作的数据量。

2. 单位成本

每位价格 = 总成本 / 总容量。

3. 存储速度

存储速度表示数据传输率，通常由存取时间、存取周期 和 主存带宽 共同描述。

存取时间 ( $T_a$ )：
- 指从启动一次存储器操作到完成该操作所经历的时间。
- 分为读出时间和写入时间。
存取周期 ( $T_m$ )：
- 又称读写周期或访问周期，是存储器完成一次完整读写所需的时间。
- 即连续两次独立访问存储器（读/写）所需的最小时间间隔。
主存带宽 ( $B_m$ )：
- 主存带宽表示单位时间内主存储器传输的信息量的最大数量。
- 单位：字/秒、字节/秒（B/s）、位/秒（b/s）。

注意：

存取时间与存取周期不同，存取周期通常大于存取时间。
对于破坏性读出的存储器，存取周期通常远大于存取时间，因为需要再生操作以恢复数据。

多层次存储系统

1. 多级存储系统的基本特点

核心矛盾： 高容量、高速度、低成本三者之间的权衡。
解决方法： 通常采用多级存储结构（如图3.2所示）。
- 位于存储层级的顶层：速度快但容量小；
- 位于底层：容量大但速度慢。

2. 存储系统的层级架构

图3.2展示了多级存储结构，主要包括：
- CPU -> Cache -> 主存 -> 磁盘（外存）
- CPU直接访问Cache，如果没有命中（Cache miss），则从主存或外存提取数据。
图3.3进一步说明了三级存储系统的访问结构：
- CPU首先访问Cache；
- 如果Cache未命中，再访问主存；
- 如果主存未命中，再访问磁盘或外存。

3. 分层设计的原则

每一层存储器作为上一层存储的高速缓存。
从CPU角度：
- 速度优先：Cache接近于CPU，存取速度高；
- 容量次优：主存比Cache容量大，但速度较低；
- 成本控制：外存容量最大，但速度最慢、成本最低。
从主存和辅存分析：
- 主存-辅存层次在速度、容量和单位成本上呈渐近关系。

4. 读写过程与数据管理

存储器分层优化了数据访问效率，保证了大容量和高速访问之间的平衡：
- Cache层： 用于临时存储经常访问的数据，降低主存访问压力；
- 主存和外存层： 用于存放大规模数据，按需调用。

5. 设计注意事项

缓存一致性问题：
- Cache与主存间可能出现数据不一致情况，因此需要额外的缓存控制机制。
主存分配：
- 主存作为外存与Cache间的桥梁，其访问速度决定整体性能。

6. 数据调动机制

主存与Cache之间的数据调动是由硬件自动完成，对程序员是透明的。
主存与辅存之间的数据调动需要操作系统和硬件协同完成，但对应用程序员来说同样是透明的。

7. 虚拟存储系统

在存储层次的扩展中发展出了虚拟存储系统。
虚拟存储系统通过将程序员逻辑地址与物理存储器地址映射，使得逻辑地址空间大于实际物理地址空间。

注意事项：在Cache-主存层或主存-辅存层中，上一层的内容仅是下一层内容的副本或子集。

高速缓冲存储器

由于程序的转移概率不会很低,数据分布的离散性较大,所以单纯依靠并行主存系统提高主存系统的频宽是有限的。这就必须从系统结构上进行改进,即采用存储体系。通常将存储系统分为“Cache-主存“层次和“主存-辅存“层次。

程序访问的局部性原理

程序访问的局部性包括 时间局部性 和 空间局部性：

时间局部性：

指在最近的未来要用到的信息，很可能是现在正在使用的信息。
原因：程序中存在循环，当前正在使用的信息会被重复访问。

空间局部性：

指在最近的未来要用到的信息，很可能与当前信息在存储空间上邻近。
原因：指令通常顺序存放，数据一般是按顺序和块状存储在一起。

高速缓存（Cache）技术 利用局部性原理，把程序正在使用的部分数据存放在一个 高速、容量较小 的 Cache 中，CPU 访问 Cache 的效率高，大多数指令和数据命中 Cache，从而提升程序执行速度。

示例分析（例 3.2）

数组访问的空间局部性和时间局部性

对于数组 a 的访问，考虑以下两个程序：

程序A（按行遍历数组）：

int sumarrayrows(int a[M][N]) {
 int i, j, sum = 0;
 for (i = 0; i < M; i++)
     for (j = 0; j < N; j++)
         sum += a[i][j];
 return sum;
}

程序B（按列遍历数组）：

int sumarraycols(int a[M][N]) {
 int i, j, sum = 0;
 for (j = 0; j < N; j++)
     for (i = 0; i < M; i++)
         sum += a[i][j];
 return sum;
}

程序A和程序B分析

假设数组 a 为 M=2048，N=2048 的二维数组，每个元素占 4字节，程序的执行和存储情况如下：

1. 空间局部性分析

程序A（按行访问）：
访问顺序为 a[0][0], a[0][1], ..., a[0][2047]; a[1][0], a[1][1], ..., a[1][2047]
- 访问顺序与内存中的存储顺序一致，因此具有 良好的空间局部性。
程序B（按列访问）：
访问顺序为 a[0][0], a[1][0], ..., a[2047][0]; a[0][1], a[1][1], ..., a[2047][1]
- 访问顺序与内存存储不一致，导致空间局部性较差，访问主存较多，性能下降。

结论：

程序A的空间局部性较好。
程序B由于访问不连续，每访问一个元素会导致 Cache 未命中，性能较差。

2. 时间局部性分析

程序A 和程序B：
- 两者都在内层循环中重复访问变量 sum 和索引变量 i, j，因此时间局部性一致。
- 内循环较短，指令也连续，时间局部性较好。

总结

空间局部性：

程序A（按行访问）空间局部性好。
程序B（按列访问）空间局部性差。

时间局部性：

程序A 和程序B 的时间局部性一致。

性能影响：

程序A 执行速度快，因为空间局部性好，Cache 命中率高。
程序B 执行速度慢，Cache 命中率低，每次访问都要从主存加载数据。

高速缓存（Cache）原理整理

Cache 结构与基本概念

定义：

Cache 位于存储器层次结构的顶层，通常由 SRAM 组成。
其目的是 提高 CPU 访问数据的速度，减少访问主存的时间。

Cache 与主存的关系：

块：主存和 Cache 被划分为相等大小的块。
- Cache 中的块称为 Cache 行。
Cache 容量远小于主存，因此只保存主存中 近期活跃的部分数据。
数据交换单位：
- Cache 与主存之间交换数据以块为单位。
- CPU 与 Cache 之间交换数据以字为单位。

Cache 访问流程：

当 CPU 访问数据时，先检查所需数据是否在 Cache 中。
- Cache 命中：直接读取数据。
- Cache 未命中：从主存读取数据，并将该块数据加载到 Cache 中（可能会替换旧数据）。
如果 Cache 已满，替换策略决定如何更新 Cache（例如：LRU 替换策略）。

Cache 命中率：

命中率 $H$ ：Cache 命中的次数占总访问次数的比例。

H=\frac{N_c}{N_c+N_m}
- $N_c$ ：Cache 中的访问次数。
- $N_m$ ：主存的访问次数。

平均访问时间：

Cache 命中时间 $T_c$ ：访问 Cache 的时间。
主存访问时间 $T_m$ ：访问主存的时间。
系统的平均访问时间：

T=H \cdot T_c+(1-H) \cdot T_m

注意：某些计算机中也采用同时访问Cache和主存的方式，若Cache命中，则主存访问终止；否则访问主存并萧换Cache。

示例分析：Cache 提高性能的实例

示例 3.3：Cache 性能计算

假设：

主存访问时间是 Cache 访问时间的倍。
Cache 命中率为 $95\%$ （即 $H = 0.95$ ）。

问题：Cache 加速后系统的平均访问时间如何？

解答：

主存访问时间 $T_m = 5T_{co}$ 。
平均访问时间 $T$ 计算为：

\begin{aligned} T &= H \cdot T_c + (1 - H) \cdot T_m \\ \text{代入} \, H = 0.95, \, T_m = 5T_c: \\ T &= 0.95 \cdot T_c + (1 - 0.95) \cdot 5T_c \\ T &= 0.95T_c + 0.05 \cdot 5T_c \\ T &= 0.95T_c + 0.25T_c = 1.2T_c \end{aligned}

结论：

Cache 加速后，系统的平均访问时间仅为 1.2倍的 Cache 访问时间。
相比于不使用 Cache（直接访问主存 $5T_c$ ），性能提高了 $\frac{5}{1.2} \approx 4.17$ 倍。

Cache 的主要问题与策略

Cache 命中判断：

如何快速判断一个地址是否在 Cache 中？

地址映射：

如何将主存地址映射到 Cache 地址？

Cache 替换策略：

当 Cache 满了时，如何选择被替换的块？（常用策略包括 LRU、FIFO 等）

Cache 写策略：

如何保证主存和 Cache 数据一致？
- 写直达法（Write Through）：数据同时写入 Cache 和主存。
- 写回法（Write Back）：数据先写入 Cache，必要时再写回主存。

总结

Cache 提高了 CPU 的数据访问效率，通过 空间局部性 和 时间局部性 原理，将近期活跃数据存放于高速 Cache 中。
平均访问时间依赖于 命中率 和 主存访问时间，命中率越高，性能提升越显著。
Cache 策略（如替换策略和写策略）影响 Cache 的有效性和数据一致性。

Cache和主存的映射方式

Cache行中的信息是主存中某个块的副本，地址映射是指把主存地址空间映射到Cache地址空间，即把存放在主存中的信息按照某种规则装入Cache。

由于Cache行数比主存块数少得多，因此主存中只有一部分块的信息可放在Cache中，因此在Cache中要为每块加一个标记，指明它是主存中哪一块的副本。该标记的内容相当于主存中块的编号。为了说明Cache行中的信息是否有效，每个Cache行需要一个有效位。

1. 直接映射

直接映射的定义

直接映射 是一种简单的 Cache 映射方式：主存中的每一块只能映射到 Cache 中的一个特定位置。
如果发生“块冲突”（两个主存块映射到同一个 Cache 行），原来的块将被替换出 Cache（即无条件替换）。

直接映射的关系公式

Cache 行号的计算公式为：
$\text{Cache 行号} = \text{主存块号} \bmod \text{Cache 总行数}$

假设：

Cache 共有 $2^c$ 行，
主存共有 $2^m$ 块。
映射规则：
- 主存的第 $0$ 块、第 $2^c$ 块、第 $2^c+1$ 块 …… 能映射到 Cache 的第 $0$ 行。
- 主存的第 $1$ 块、第 $2^c+1$ 块 …… 能映射到 Cache 的第 $1$ 行，依此类推。
主存地址的结构
主存地址被划分为三部分：

标记（tag）：高位地址，标识主存块。
Cache 行号：中间位地址，确定主存块映射到哪个 Cache 行。
块内地址：低位地址，确定块内数据的位置。

CPU 访问流程：

确定 Cache 行：
根据地址中的 c 位（Cache 行号），定位到对应的 Cache 行。
标记比较：
比较当前主存地址中的高位 tag 和 Cache 行中的标记：

若相等且有效位为 1，则“命中”，CPU 可直接从 Cache 读取数据。
若不相等或有效位为 0，则“未命中”，需要从主存读取数据：
- 将主存中的块调入 Cache 对应的行中。
- 更新有效位为 1，标记为当前地址的 tag。

数据传送：
CPU 从 Cache 或主存中获取数据。

总结优缺点

优点：实现简单、硬件成本低。
缺点：不够灵活，容易发生块冲突，空间利用率较低。

2. 全相联映射

全相联映射的定义

在 全相联映射 中，主存的每一块可以装入 Cache 中的 任意位置。
每个 Cache 行都有一个 标记（tag），用于标识当前行存放的是主存中的哪一块数据。

CPU 访问过程

标记比较：
CPU 访问时，需要将当前访问地址中的标记与 Cache 中 所有行的标记 进行比较。
命中与未命中：

若标记相等且有效位为 1，则 Cache 命中，CPU 直接从 Cache 中读取数据。
若所有标记均不匹配，则 Cache 未命中，需要从主存中加载相应数据块到 Cache。

全相联映射的特点

优点：

灵活性高：主存中的每一块可以装入 Cache 的任何一行，减少了块冲突的概率。
Cache 冲突概率低，空间利用率高，命中率高。

缺点：

标记比较速度慢：需要与 Cache 中的 所有行的标记 进行比较，开销较大。
硬件实现成本高：通常需要昂贵的并行硬件，如内容寻址存储器（CAM）。

全相联映射的地址结构
主存地址被划分为两部分：

标记（tag）：用于标识主存块。
块内地址：用于确定块内数据的位置。

示意结构：

主存地址示意：
$\text{标记（高位）} \quad \text{块内地址（低位）}$

总结

全相联映射 提供了较高的灵活性和命中率，适用于对性能要求较高的场景。
但由于需要进行多路标记比较，硬件实现复杂且成本较高，常用于较小容量的 Cache。

3. 组相联映射

组相联映射的定义

组相联映射 将 Cache 分成 $Q$ 个大小相等的组，每个主存块可以装入 固定的组 中的任意一行。
映射方式：
- 在组内：采用 全相联映射。
- 在组间：采用 直接映射。
特殊情况：
- 当 $Q = 1$ 时，组相联映射退化为 全相联映射。
- 当 $Q = \text{Cache 行数}$ 时，组相联映射退化为 直接映射。

组相联映射的关系公式

组号计算：

\text{Cache 组号} = \text{主存块号} \bmod \text{Cache 组数} (Q)

每组有 $r$ 个 Cache 行。

主存地址的结构
主存地址被划分为三部分：

标记（tag）：标识主存块的高位地址。
组号：决定主存块映射到哪个组。
块内地址：定位块内数据的位置。

CPU 访问 Cache 的流程

根据组号定位组：
根据访问地址中的组号定位到对应的组。
标记比较：
在组内对 所有行的标记 进行比较：

命中：若标记匹配且有效位为 1，CPU 直接从 Cache 读取数据。
未命中：若标记不匹配或有效位为 0，需从主存中读取数据块，替换组内一行（根据替换算法，如LRU）。

数据传送：
将主存数据送入 Cache 并传给 CPU，同时更新标记和有效位。

示例
假设：

主存地址大小：28 位，主存块大小为 64B。
Cache 行数：8 行，分为 2 组（ $Q = 2$ ），每组 $r = 4$ 行。

主存地址分解：

块内地址：6 位（ $2^6 = 64$ B）。
组号：3 位（ $2^3 = 8$ 行，分为 2 组）。
标记：19 位（ $28 - 6 - 3 = 19$ ）。

标记计算：

主存地址：0000 0001 0010 0011 0100 0110
- 标记：0000 0001 0010 0011 010
- 组号：001
- 块内地址：0110 0100

直接映射与组相联映射对比：

直接映射：通过 $\text{地址} \bmod \text{Cache 行数}$ 定位行。
组相联映射：通过 $\text{地址} \bmod \text{组数}$ 定位组，然后在组内搜索。

优缺点总结

优点：

缓解了直接映射中的 冲突问题。
实现成本低于全相联映射。

缺点：

比直接映射复杂，需要组内进行标记比较。
硬件成本和访问速度介于直接映射和全相联映射之间。

三种映射方式对比

直接映射：

命中率较低，容易发生冲突。
实现简单，速度快。

全相联映射：

命中率最高，灵活性强。
标记比较复杂，成本高。

组相联映射：

结合了两者的优点，性能较高且成本适中。
适用于大多数场景。