按『个人 Wiki』风格整理的学习笔记
推荐译法：
| 英文 | 中文 |
|---|---|
| memory | 存储器、记忆体 |
| hierarchy | 等级体系、层次结构 |
| main memory | 主存（储器）、内存（条） |
| virtual memory | 虚拟内存（空间） |
| cache (memory) | 缓存器 |
| caching, staging | 缓存、暂存 |
| store, write, output | 存（储）、写（出） |
| retrieve, read, input | 取（出）、读（入） |
速度较快，但价格昂贵，用于缓存器 (cache)。
SRAM 将每个位存储于具有两个稳定状态的单元 (cell) 中， 后者由含有六个晶体管的电路来实现，能够在通电时保持其所处的状态，对扰动不敏感。
速度较慢，但价格便宜，用于主存储器 (main memory)。
DRAM 将每个位以电荷形式存储于电容 (capacitor) 中，后者对扰动很敏感。 因此，存储系统必须周期地读、写其中的信息，以避免扰动破坏 DRAM 中的信息。
每区块 DRAM 芯片被划分为 $d$ 个超级单元 (supercell)，每区块超级单元含 $w$ 个存储单元，故整区块 DRAM 芯片可存储 $d\times w$ 位信息。
所有超级单元被编为 $r$ 行、$c$ 列（含 $d = r \times c$ 个元素）的二维数组。
信息通过针脚 (pin) 传入、传出 DRAM：
读取第 $(r, c)$ 个超级单元中的数据分两步完成：
| RAS | CAS |
|---|---|
这种二步寻址方式可以节省所需地址针脚对数量。
DRAM 芯片被打包为存储模区块 (memory modules)，俗称内存条，后者可插入主板 (motherboard) 的扩展槽中。
每个超级单元只能存储 1 字节信息，故每个 8 字节数据（void * 或 double）需由分布在 8 区块芯片上、具有相同二维地址的 8 个超级单元来存储。
位于存储模区块上的存储控制器 (memory controller) 负责
DRAMs 及 SRAMs 仅能在通电时保存信息，因此是易变的 (volatile)。 能够将信息保存到断电后的存储设备被称为非易变的 (non-volatile)，它们在历史上也被称为只读存储 (read-only memory, ROM)。
| ROM 类型 | 写入次数 |
|---|---|
| programmable ROM (PROM) | $1$ |
| erasable PROM (EPROM) | $10^3$ |
| electrically EPROM (EEPROM) | $10^5$ |
总线 (bus)：连接 CPU 与主存储器或读写设备的共享电路。
硬盘 (disk) 的存储量大（RAM 的数千倍），但读写速度慢（DRAM 的数十万倍、SRAM 的数百万倍）。
| 盘片（俯视图） | 柱面（侧视图） |
|---|---|
机械部件：
时间参数：
硬盘控制器 (disk controller)
读写总线被设计为独立于 CPU，并且被所有所有设备共享：
硬盘读取步骤：
固态硬盘 (solid state disk, SSD) 是一种基于闪存 (flash memory) 技术的存储设备。
数据以页面 (page) 为单位进行读写。各页面只有在其所属区块 (block) 被擦除 (erase) 后才能写入；被擦除的区块内，各页面可以被写入一次。每个区块大约可以被写入 $10^5$ 次；整区块 SSD 大约可以使用十年（连续读写）到几万年（日常读写）。
| 固态硬盘 | 机械硬盘 | |
|---|---|---|
| 介质 | 闪存芯片 | 磁性盘片 |
| 映射 | 闪存翻译层（逻辑区块 ↦ 区块、页面） | 硬盘控制器（逻辑区块 ↦ 盘面、扇区） |
| 优点 | 安静、抗震、省电、快速 | 便宜 |
| 缺点 | 可能磨尽 (wear out)、昂贵 | …… |
int sumvec(int v[N]) {
int i, s = 0;
for (i = 0; i < N; i++)
s += v[i];
return s;
}
s 有时间局部性，无空间局部性。v 有空间局部性，无时间局部性。$k$-步访问模式 (stride-$k$ reference pattern)：对一段连续存储的元素，每访问完其中一个，向前跳 $k$ 步。
二维数组有以下两种访问顺序：
指令与数据类似，运行时也需要由 CPU 从内存中读取，因而也可以分析其局部性。
一般而言，循环体越短、循环次数越多，局部性越好。
| 级别 | 名称 | 缓存对象 | 延迟（时钟周期） |
|---|---|---|---|
| 0 | 寄存器 | 4 或 8 字节词 | 0 |
| 1 | L1 缓存器 | 64 字节区块 | 4 |
| 2 | L2 缓存器 | 64 字节区块 | 10 |
| 3 | L3 缓存器 | 64 字节区块 | 50 |
| 4 | 主存储器 | 4 KB 页 | 200 |
| 5 | 本地磁盘 | 扇区 | 100,000 |
| 6 | 分布式文件系统 | 文件 | 10,000,000 |
| 7 | 互联网服务器 | 网页 | 1,000,000,000 |
基本概念：
当程序需要从第 $k+1$ 级存储器中读取数据 $d$ 时，存储系统会先在第 $k$ 级存储器中查找。
缓存命中 (cache hit)：若数据 $d$ 恰好属于第 $k$ 级存储器中的某区块，则无需访问第 $k+1$ 级存储器。
缓存丢失 (cache miss)：若数据 $d$ 不属于第 $k$ 级存储器中的任何区块，则需访问第 $k+1$ 级存储器。
访问完第 $k+1$ 级存储器后，可能需要修改第 $k$ 级存储器（替换其中某区块的数据）。 常用的替换策略 (replacement policy)有
各级存储器都需要有某种（硬件或软件）机制来管理缓存，其任务包括划分区块、判断是否命中、丢失后替换区块。
| 描述 | 总数（个或字节） | 位数 |
|---|---|---|
| 物理地址 | $M$ | $m=\log_2M$ |
| 缓存集 / 缓存器 | $S$ | $s=\log_2S$ |
| 缓存线 / 缓存集 | $E$ | |
| 区块偏移 / 缓存线 | $B$ | $b=\log_2B$ |
| 缓存线标签 | $t=m-s-b$ | |
| 缓存线有效性 | $1$ | |
| 缓存器容量 | $C=B\times E\times S$ |
缓存可以按 $E$ 值来分类：
以地址 $A$ 中（从右向左）第 $b$ 位起的 $s$ 位所表示的无符号整数，作为缓存集的序号。
该缓存集内只有一条缓存线。
若该缓存线的有效位非空，且地址 $A$ 中最高（左端）的 $t$ 位所表示无符号整数等于该缓存线的标签，则为缓存命中，否则为缓存丢失。
若缓存命中，则以地址 $A$ 中最低（右端）的 $b$ 位所表示无符号整数，作为所读数据词在当前缓存线内的的偏移量（起始字节编号）。
若缓存丢失，则需从下一级存储器读取数据，并替换当前（无其他可选）缓存线内的数据。
对于直接映射的缓存，冲突丢失容易在访问元素个数为 $2^n$ 的数组时发生。
float dotprod(float x[8], float y[8]) {
float sum = 0.0;
for (int i = 0; i < 8; i++)
sum += x[i] * y[i]; /* y[0,4) 可能冲掉 x[0,4) */
return sum;
}
解决办法：在数组末尾补若干占位字节。
同直接映射的缓存之缓存集选择。
每个缓存集可以被视为一个小型关联存储器 (associative memory)：
当前缓存集内的任意一条缓存线都可能命中，故缓存器需遍历各缓存线。
因 $S=1$ 即 $s=0$，故 $m=t+b$ 即地址只分缓存线标签与区块偏移量两部分。
同集合关联的缓存之缓存线匹配及数据词选择。
由于硬件实现困难，完全关联的缓存通常规模较小。
相对于读入操作，写出操作有其额外的问题：
对于写出命中 (write hit)，可采取的策略有
对于写出丢失 (write miss)，可采取的策略有
建议：在没有文档可查的情况下，可假设缓存系统采用向回写出及写出分配策略。
Intel Core i7 处理器的三级缓存性能如下（三者的 $B$ 值均为 64 字节）：
| 名称 | 归属 | $C$ | $E$ | $S$ |
|---|---|---|---|---|
| L1 指令缓存 | 单核独享 | 32 KB | 8 | 64 |
| L1 数据缓存 | 单核独享 | 32 KB | 8 | 64 |
| L2 统一缓存 | 单核独享 | 256 KB | 8 | 512 |
| L3 统一缓存 | 多核共享 | 8 MB | 16 | 8192 |
在 Linux 系统中，可以用 lscpu 命令查看上述信息：
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
Stepping: 3
CPU MHz: 800.000
CPU max MHz: 4000.0000
CPU min MHz: 800.0000
BogoMIPS: 7183.69
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 8 MiB
NUMA node0 CPU(s): 0-7
Vulnerability ...
性能参数
$B$ 值大，有利于空间局部性，不利于时间局部性、丢失罚时。
$E$ 值大，有利于减少冲突丢失，但实现复杂、速度较慢。
存储器级别越低（丢失罚时越大）越适合用大的 $E$ 值。
存储器级别越低（写出用时越多）越适合用写回策略。
一般建议：关注核心函数内层循环；降低内存循环丢失率。
读取吞吐量 (read throughput) 或读取带宽 (read bandwidth)，即程序在单位时间内读取的数据量，常以 MB/s 为单位。
存储器系统的性能由程序的时间局部性与空间局部性共同决定，最大可相差若干数量级。
/* Version ijk (medium) */
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
sum = 0.0;
for (k = 0; k < n; k++)
sum += A[i][k] * B[k][j]; /* 2 loads, 0 stores, 1.25 misses */
C[i][j] += sum;
}
/* Version jki (worst) */
for (j = 0; j < n; j++)
for (i = 0; i < n; i++) {
Bkj = B[k][j];
for (k = 0; k < n; k++)
C[i][j] += A[i][k] * Bkj; /* 2 loads, 1 stores, 2.00 misses */
}
/* Version kij (best) */
for (k = 0; k < n; k++)
for (i = 0; i < n; i++) {
Aik = A[i][k];
for (j = 0; j < n; j++)
C[i][j] += Aik * B[k][j]; /* 2 loads, 1 stores, 0.50 misses */
}
丢失率比访存次数更宜作为性能指标。