存储器层次结构
- 存储器层次结构
- 局部性原理
- 程序倾向于使用当前地址附近的数据和指令。
- 时间局部性：最近引用的项目在不久的未来还可能使用。
- 空间局部性：当前地址附近的项目被频繁使用。
- 规律
- 存储技术越快，则单位成本更高、容量更小、耗能更多。
- 利用局部性原理，可以使用不同规模的不同存储技术，更快、更小的存储设备作为慢速设备的缓存。
- 局部性原理
- 内存
- 内存读写
- 总线：CPU 与内存通过总线交流地址、数据、指令。
- 读内存：
- CPU 将地址放到内存总线上。
- 内存从总线读取地址，把内存值放到内存总线上。
- CPU 从总线上读取值，复制到寄存器中。
- 写内存：
- CPU 将地址放到内存总线上，内存读取地址并等待数据。
- CPU 将数据放到总线上。
- 内存读取数据，写入到对应地址中。
- 随机访问存储器
- 类型
- SRAM：存储一个位需要的晶体元件多，通电时可以永久保持状态。
- DRAM：存储一个位需要的晶体元件少，需要不断刷新状态。
- SDRAM：同步的 DRAM，用时钟信号代替异步电路控制。
- DDR SDRAM：双倍的数据频率，在两个时钟边沿触发。
- 结构
- 所有的位按照每组
w位组成超单元，超单元按照行和列的二维形式组织。 - 访问超单元时给出二维索引：
- 先通过 Row access strobe 选择行，把此行复制到行缓冲。
- 在通过 Column access strobe 选择列，把缓冲区中的列复制到数据总线。
- 多组二维单元组成内存模块：
- 所有的位按照每组
- 类型
- 内存读写
- 磁盘
- 结构
- 磁盘有多个盘片，每个盘片有两个表面。
- 每个表面有多个同心圆环，称为磁道。
- 每条磁道被划分为多个扇区，扇区之间存在间隔。
- 容量计算
- 由于不同磁道的扇区数不同，一般使用平均扇区数计算。
- 容量 = 字节数/每扇区 x 平均扇区数/每磁道 x 磁道数/每表面 x 表面数/每盘片 x 盘片数/每磁盘。
- IO
- DMA。
- 结构
- 高速缓存
- 一般结构
- 缓存用一个三元组
(S, E, B)衡量：B为一个缓存行/缓存块的字节长度，与内存的基本读写单元长度相同。E为一个组内的缓存行数，为 2 的e次幂。S为一个缓存的组数，为 2 的s次幂。
- 每个缓存行包括有效位、
t位标签、B字节数据。 - 地址编码：
- 缓存的地址与内存地址相同，但是分为三个部分。
t位标签：与每个缓存行的标签相同，位于最高位部分，用于匹配组内的缓存行。s位组索引：用于匹配存放的组。b位行内索引：用于在缓存行内偏移。
- 缓存用一个三元组
- 组织结构方式
- 直接映射
E = 1，即每一组只有一个缓存行。- 对于一个组内的缓存行，如果标签不同，则原来的单元直接被淘汰。
- 多路组相连映射
E > 1，即每一组可以有多个缓存行。- 在查找缓存时，先确定组，再在组内同时匹配所有缓存行，只要有任意一个标签相同，则缓存命中。
- 没有任何标签匹配时，按照 LRU 规则淘汰缓存行。
- 全相连映射
S = 1，即只有一个组，地址中不需要为组索引编码。- 完全按照标签进行匹配。
- 直接映射
- 写处理
- 如果缓存命中：
- 写回：只更新缓存，直到缓存行要被淘汰时再写入内存。需要使用脏位。
- 写直达：更新缓存时，立即直接写入内存。
- 如果缓存不命中：
- 写分配：把数据装载进入缓存。
- 非写分配：不装入缓存，直接写入内存。
- 通常的组合策略：写回 + 写分配、写直达 + 非写分配。
- 如果缓存命中：
- 面向缓存的优化
- 常见场景下的不命中率：
- 单个变量：
0%。 - 连续一维数组访问：
sizeof(element) / B。 - 连续二维数组行内访问：
sizeof(element) / B。 - 连续二维数组列内访问：
100%，除非整个数组足够小。
- 单个变量：
- 矩阵乘法
c[i][j] += a[i][k] * b[k][j]的最优循环方式是kij或ikj，提升空间局部性。- 此时最好需要用局部变量保存
a[i][k]。
- 此时最好需要用局部变量保存
- 矩阵乘法也可以通过分块优化，提升时间局部性，使得每个块都尽可能保存到缓存中。
- 常见场景下的不命中率：
- 一般结构
- 内存山丘
- 内存山丘是三维图，以循环访问步长和总访问大小为 x 轴和 y 轴，以吞吐量为 z 轴。
- 循环访问步长控制空间局部性，总访问大小控制时间局部性。
