作者: andylin02学习章节: 第 6 章 存储器层次结构关键词 随机访问存储器(SRAM/DRAM)非易失性存储器(ROM/Flash)局部性原理存储器层次结构高速缓存直接映射组相联全相联写策略分块存储器山Cache Lab引言跨越存储墙“一个编写良好的程序倾向于展示出良好的局部性。”—— CSAPP 作者在计算机系统模型中CPU 执行指令而存储器系统为 CPU 存放指令和数据。如果你需要的数据在 CPU 寄存器中访问它只需要 0 个周期如果在高速缓存中需要 4~75 个周期如果在主存中需要上百个周期而如果存储在磁盘上则需要大约几千万个周期CPU 与存储器之间的这种速度差距被称为存储墙Memory Wall——处理器的性能每年都在提升而主存的访问速度提升却相对缓慢。存储器层次结构正是为了解决这一矛盾而设计的核心思想通过在不同速度、不同容量的存储设备之间建立层级关系用局部性原理来弥合 CPU 与存储器之间的速度鸿沟。本章结构速览6.1 存储技术SRAM、DRAM、ROM、Flash、磁盘、SSD6.2 局部性时间局部性与空间局部性6.3 存储器层次结构核心思想与工作原理6.4 高速缓存存储器组织结构、映射方式、写策略6.5 编写缓存友好的代码分块技术、循环优化6.6 存储器山量化程序性能Cache Lab 配套实验Part A 缓存模拟器 Part B 矩阵转置优化一、存储技术1.1 随机访问存储器RAMRAM 分为两类静态的和动态的。SRAM 比 DRAM 更快但也贵得多。SRAM 用作高速缓存存储器既可以在 CPU 芯片上也可以在片下。DRAM 用作主存以及图形系统的帧缓冲区。静态 RAMSRAMSRAM 将每个位存储在一个双稳态的存储器单元中每个单元通常由 6 个晶体管实现。双稳态意味着电路可以无限期地保持在两个不同的电压状态之一其他任何状态都是不稳定的。只要有电SRAM 就会永远保持它的值。即使受到干扰当干扰消除时电路也会恢复到稳定值。动态 RAMDRAMDRAM 将每个位存储为对一个电容的充电每个单元由一个电容和一个访问晶体管组成。由于电容会漏电DRAM 需要定期刷新通常每 64ms。DRAM 对干扰非常敏感——当电容的电压被扰乱后它永远不会恢复。SRAM vs DRAM 对比特性SRAMDRAM每位晶体管数61相对访问时间1×10×需要刷新否是干扰敏感否是相对花费1000×1×主要应用高速缓存主存、帧缓冲区核心洞察SRAM 用晶体管密度换取了速度DRAM 用速度和稳定性换取了容量——这是典型的工程权衡。┌─────────────────────────────────────────────────────────────────────┐ │ DRAM 芯片组织结构 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ DRAM 芯片划分为 d 个超单元每个超单元包含 w 个 DRAM 单元 │ │ w 一般为 8。超单元按 r 行 c 列组织rc d。 │ │ │ │ ┌─────────────────────────────────────────┐ │ │ │ 列地址 │ │ │ │ ↓ │ │ │ │ ┌────┬────┬────┬────┐ │ │ │ 行 │ │(0,0)│(0,1)│(0,2)│(0,3)│ ← 行 0 │ │ │ 地 │ ├────┼────┼────┼────┤ │ │ │ 址 │ │(1,0)│(1,1)│(1,2)│(1,3)│ ← 行 1 │ │ │ │ ├────┼────┼────┼────┤ │ │ │ → │ │(2,0)│(2,1)│(2,2)│(2,3)│ ← 行 2 │ │ │ │ ├────┼────┼────┼────┤ │ │ │ │ │(3,0)│(3,1)│(3,2)│(3,3)│ ← 行 3 │ │ │ │ └────┴────┴────┴────┘ │ │ │ └─────────────────────────────────────────┘ │ │ │ │ 读取超单元 (2,1) 的步骤 │ │ 1. 内存控制器发送行地址 i2DRAM 将整个第 2 行复制到内部行缓冲区 │ │ 2. 内存控制器发送列地址 j1DRAM 从行缓冲区中复制超单元 (2,1) │ │ 发送给内存控制器 │ │ │ └─────────────────────────────────────────────────────────────────────┘内存模块每个 DRAM 芯片被连接到内存控制器。多个 DRAM 芯片封装在内存模块中插到主板的扩展槽上。常用的是双列直插内存模块DIMM以 64 位为块与内存控制器交换数据。1.2 非易失性存储器ROMROM 设备断电后仍能保持数据。由于历史原因它们被统称为只读存储器但实际上有些 ROM 是可写的ROM 类型擦写方式擦写次数PROM一次可编程用高电流熔断1EPROM紫外线整块擦除~1000EEPROM电子信号擦除~10^5Flash基于 EEPROM以块为单位擦除104~106存储在 ROM 设备中的程序通常被称为固件Firmware包括 BIOS、磁盘控制器固件等。固态硬盘SSD基于闪存技术将闪存翻译层和多个闪存芯片封装在一起。1.3 机械磁盘从磁盘上读信息的时间为毫秒级比从 DRAM 读慢了 10 万倍比从 SRAM 读慢了 100 万倍。┌─────────────────────────────────────────────────────────────────────┐ │ 机械磁盘访问时间 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ T_access T_seek T_rotation T_transfer │ │ │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ T_seek寻道时间 ≈ 3-9 ms │ │ │ │ → 移动传送臂将读/写头定位到目标磁道 │ │ │ ├─────────────────────────────────────────────────────────────┤ │ │ │ T_rotation旋转时间 ≈ 4-8 ms │ │ │ │ → 等待磁盘旋转到目标扇区平均半圈 │ │ │ ├─────────────────────────────────────────────────────────────┤ │ │ │ T_transfer传送时间 ≈ 0.02 ms │ │ │ │ → 读取整个扇区内容到控制器缓冲区 │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ │ │ 磁盘访问时间主要由机械运动决定毫秒级比 CPU 操作慢了 │ │ 数百万倍这也是为什么使用内存可以极大加速程序运行的根本原因。 │ │ │ └─────────────────────────────────────────────────────────────────────┘1.4 固态硬盘SSDSSD 是一种基于闪存的存储技术。一个固态硬盘中封装了一个闪存翻译层和多个闪存芯片。闪存翻译层是一个硬件/固件设备负责处理来自 CPU 的请求并管理闪存芯片的读写。SSD 没有机械运动部件因此随机访问速度远快于机械硬盘但寿命有限闪存擦写次数限制。1.5 连接 CPU 与存储器的典型总线结构一条总线是由多条并排的电线组成的一束线传输地址、数据和控制信号多个设备共享多条总线。┌─────────────────────────────────────────────────────────────────────┐ │ CPU 到主存的访问流程 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ CPU 执行 movq A, %rax │ │ │ │ ┌──────┐ ┌──────────┐ ┌──────────┐ │ │ │ CPU │─────→│ 系统总线 │─────→│ I/O桥 │ │ │ └──────┘ └──────────┘ └────┬─────┘ │ │ │ ▲ │ │ │ │ │ │ │ │ │ │ ┌───┴───┐ │ │ │ └──────────│内存总线│ │ │ │ └───┬───┘ │ │ │ │ │ │ │ ┌───┴───┐ │ │ │ │ 主存 │ │ │ │ └───────┘ │ │ │ │ │ ┌───┴───┐ ┌──────────┐ ┌──────────┐ │ │ │ CPU │←─────│ 系统总线 │←─────│ I/O桥 │ │ │ └───────┘ └──────────┘ └────┬─────┘ │ │ │ │ │ ┌───┴───┐ │ │ │ 主存 │ │ │ └───────┘ │ │ │ │ 读操作步骤 │ │ 1. CPU 将地址 A 放到系统总线上I/O 桥将信号传递到内存总线 │ │ 2. 主存从内存总线读地址从 DRAM 取出数据字将数据写到内存总线 │ │ 3. I/O 桥将内存总线信号翻译成系统总线信号沿系统总线传递 │ │ 4. CPU 从系统总线读数据复制到寄存器 %rax │ │ │ └─────────────────────────────────────────────────────────────────────┘二、局部性“程序倾向于引用邻近于其他最近引用过的数据项的数据项或者最近引用过的数据项本身。这种倾向被称为局部性原理。”局部性是程序运行的基本属性也是存储器层次结构能够生效的根本原因。如果程序没有局部性那么任何层次的缓存都会失效——因为每次访问的数据都不在缓存中。2.1 局部性的两种形式┌─────────────────────────────────────────────────────────────────────┐ │ 局部性原理示意图 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ 时间局部性Temporal Locality │ │ │ │ 被引用过一次的内存位置很可能在不远的将来再被多次引用 │ │ │ │ → 示例循环中的累加器变量、函数中的局部变量 │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ 空间局部性Spatial Locality │ │ │ │ 如果一个内存位置被引用了一次那么程序很可能在不远的将来 │ │ │ │ 引用附近的一个内存位置 │ │ │ │ → 示例顺序访问数组元素、遍历链表 │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ │ └─────────────────────────────────────────────────────────────────────┘2.2 数据引用的局部性分析// 示例数组求和intsum_array(inta[M][N]){inti,j,sum0;for(i0;iM;i){for(j0;jN;j){suma[i][j];// 按行遍历步长 1}}returnsum;}这个函数的局部性分析sum变量良好的时间局部性每次循环都被访问a[i][j]良好的空间局部性按行优先访问步长为 1i和j良好的时间局部性在循环中反复更新2.3 局部性小结重复引用相同变量的程序有良好的时间局部性步长 k 越小空间局部性越好取指令指令获取——循环有好的时间和空间局部性核心原则将注意力集中在内循环上因为大部分计算和存储器访问都集中在这里三、存储器层次结构3.1 核心思想存储器层次结构的基本思想是对于每个 k位于 k 层的更快更小的存储设备作为位于 k1 层的更大更慢的存储设备的缓存。┌─────────────────────────────────────────────────────────────────────┐ │ 存储器层次结构 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ L0: 寄存器 ←─── 管理编译器 │ │ ↑ │ │ L1: L1 高速缓存 ←─── 管理硬件 │ │ ↑ │ │ L2: L2 高速缓存 ←─── 管理硬件 │ │ ↑ │ │ L3: L3 高速缓存 ←─── 管理硬件 │ │ ↑ │ │ L4: 主存 ←─── 管理操作系统 │ │ ↑ │ │ L5: 本地磁盘 ←─── 管理操作系统 │ │ ↑ │ │ L6: 远程存储 ←─── 管理操作系统/网络 │ │ │ │ 层次结构的本质每一层都是下一层的缓存 │ │ → 从寄存器到磁盘越往下速度越慢、容量越大、成本越低 │ │ │ └─────────────────────────────────────────────────────────────────────┘3.2 缓存的基本概念从逻辑上看缓存是一个数组每个数组元素是一个缓存块。由于缓存的容量远小于下层存储需要将数据映射到缓存中缓存命中第 k 层缓存了需要的数据对象 d缓存不命中第 k 层没有缓存 d需要从第 k1 层取出替换/驱逐从缓存中覆盖一个现存块牺牲块被驱逐的块冷缓存空的缓存导致的缓存不命中称为强制性不命中或冷不命中冲突不命中由限制性放置策略引起容量不命中当活跃块集合工作集的大小比缓存大时发生3.3 缓存的管理者缓存类型缓存什么被缓存在何处管理方式寄存器4-8 字节字CPU 核心编译器TLB地址翻译处理器硬件L1/L2/L3 Cache64 字节块处理器硬件DRAM主存处理器硬件虚拟内存4KB 页主存操作系统磁盘文件磁盘操作系统四、高速缓存存储器4.1 通用组织结构一个高速缓存由 S 个组Set组成每组包含 E 个缓存行Line每个缓存行包含一个有效位、t 个标记位和一个大小为 B 字节的数据块┌─────────────────────────────────────────────────────────────────────┐ │ 高速缓存通用组织结构 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ C S × E × B │ │ │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ Cache │ │ │ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │ │ │ │ Set 0 │ │ Set 1 │ │ ... │ │ Set S-1 │ │ │ │ │ │ ┌─────┐ │ │ ┌─────┐ │ │ │ │ ┌─────┐ │ │ │ │ │ │ │Line0│ │ │ │Line0│ │ │ │ │ │Line0│ │ │ │ │ │ │ │ v│t│ 块 │ │ │ v│t│ 块 │ ... │ │ │ v│t│ 块 │ │ │ │ │ │ ├─────┤ │ │ ├─────┤ │ │ │ │ ├─────┤ │ │ │ │ │ │ │Line1│ │ │ │Line1│ │ │ │ │ │Line1│ │ │ │ │ │ │ └─────┘ │ │ └─────┘ │ │ │ │ └─────┘ │ │ │ │ │ └─────────┘ └─────────┘ └─────────┘ └─────────┘ │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ │ │ 其中 │ │ S 组数Set 数量 │ │ E 相联度每组行数 │ │ B 块大小Bytes per block │ │ C S × E × B 缓存总容量 │ │ │ └─────────────────────────────────────────────────────────────────────┘4.2 内存地址的划分在缓存访问中内存地址被划分为三个字段┌─────────────────────────────────────────────────────────────────────┐ │ 内存地址划分 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ 地址位 (t位) (s位) (b位) │ │ ┌────────┬─────────┬─────────┐ │ │ │ tag │ set idx │ block │ │ │ │ │ │ offset │ │ │ └────────┴─────────┴─────────┘ │ │ │ │ 各字段含义 │ │ • tag标记位唯一标识缓存行 │ │ • set idx组索引定位到具体组 │ │ • block offset块内偏移在块中定位具体字节 │ │ │ │ S 2^s │ │ B 2^b │ │ │ └─────────────────────────────────────────────────────────────────────┘4.3 三种映射方式① 直接映射高速缓存E 1最简单的情况每组只有 1 个缓存行。每次根据 set index 直接找到对应组比较 tag 是否匹配。┌─────────────────────────────────────────────────────────────────────┐ │ 直接映射缓存E1 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ 查找步骤 │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ 1. 组选择根据 set index 定位到对应的组 │ │ │ │ 2. 行匹配检查该组唯一的行的 tag 是否与地址的 tag 匹配 │ │ │ │ 3. 字抽取如果匹配且 valid1根据 block offset 取出数据 │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ │ │ ⚠️ 缺点如果两个地址的 set index 相同会交替访问对方 │ │ 导致冲突不命中抖动现象 │ │ │ └─────────────────────────────────────────────────────────────────────┘② 组相联高速缓存1 E C/B每组有 E 个缓存行。当组中有多个空行时可以放置多个块冲突不命中得到缓解。没有空行时需要选择一个牺牲行进行替换。替换策略策略全称规则LRULeast Recently Used替换最后一次访问时间最久远的一行LFULeast Frequently Used替换过去某个时间窗口内引用次数最少的一行随机Random随机选择一行替换③ 全相联高速缓存E C/B所有缓存行都在同一个组中。地址被划分为标记和块偏移没有组索引位。┌─────────────────────────────────────────────────────────────────────┐ │ 三种映射方式对比 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ ┌─────────────┬─────────────┬─────────────┬─────────────┐ │ │ │ 映射方式 │ 每组行数 │ 冲突情况 │ 实现难度 │ │ │ ├─────────────┼─────────────┼─────────────┼─────────────┤ │ │ │ 直接映射 │ E 1 │ 冲突严重 │ 简单 │ │ │ ├─────────────┼─────────────┼─────────────┼─────────────┤ │ │ │ 组相联 │ E 1 │ 明显缓解 │ 中等 │ │ │ ├─────────────┼─────────────┼─────────────┼─────────────┤ │ │ │ 全相联 │ E C/B │ 无冲突 │ 复杂 │ │ │ └─────────────┴─────────────┴─────────────┴─────────────┘ │ │ │ │ 真实系统中L1 Cache 常用 8 路组相联L2/L3 使用更高路数 │ │ │ └─────────────────────────────────────────────────────────────────────┘4.4 写策略写操作比读操作复杂因为写完缓存后主存里的副本也需要处理。写命中Write Hit策略策略规则优点缺点写直达写缓存的同时立即写下一级存储实现简单主存始终与缓存一致每次写都要访问主存产生大量总线流量写回只写缓存暂不写主存打上脏位驱逐时才写回主存大幅减少总线流量性能好每条缓存行需要额外的脏位逻辑更复杂场景对比连续对同一地址写 100 次写直达需要 100 次主存写写回只需 1 次主存写。写缺失Write Miss策略策略规则写分配先从下一级加载该块到缓存再在缓存中执行写操作非写分配绕过缓存直接写到下一级存储典型组合写回 写分配推荐利用空间局部性写直达 非写分配真实系统中低层更常用写回策略4.5 真实缓存层次结构现代处理器通常有多个独立的缓存i-cache只保存指令的高速缓存通常是只读的d-cache只保存数据的高速缓存统一缓存同时保存指令和数据4.6 缓存参数的性能影响参数影响命中时间从缓存向处理器发送一行的时间L1 约 4 周期L2 约 10 周期不命中惩罚由于不命中需要额外的时间主存约 50-200 周期不命中率内存引用在缓存中没找到的比例块大小块越大对空间局部性越好块越多对时间局部性命中率有损害相联度越高抖动越少但实现复杂度和访问速度受影响五、编写缓存友好的代码5.1 核心原则将注意力集中在内循环上因为大部分计算和存储器访问都集中在这里按照数据对象在存储器中存放的顺序以步长为 1来读取数据可使空间局部性最佳5.2 分块Blocking技术分块是将一个大矩阵划分为若干小块进行处理使每个小块可以完全放入缓存中从而减少缓存不命中。// 矩阵乘法的分块优化示例#defineBLOCK8// 块大小voidmatrix_multiply_block(intn,intA[n][n],intB[n][n],intC[n][n]){inti,j,k,i1,j1,k1;for(i0;in;iBLOCK){for(j0;jn;jBLOCK){for(k0;kn;kBLOCK){// 对 BLOCK × BLOCK 的块进行运算for(i1i;i1iBLOCK;i1){for(k1k;k1kBLOCK;k1){for(j1j;j1jBLOCK;j1){C[i1][j1]A[i1][k1]*B[k1][j1];}}}}}}}┌─────────────────────────────────────────────────────────────────────┐ │ 分块技术原理示意图 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ 矩阵 A 矩阵 B │ │ ┌─────────────────┐ ┌─────────────────┐ │ │ │ ██████│ │ │ ██████│ │ │ │ │ ██████│ │ │ ██████│ │ │ │ │ ──────┼─────────│ │ ──────┼─────────│ │ │ │ │ │ │ │ │ │ │ └─────────────────┘ └─────────────────┘ │ │ │ │ 分块策略 │ │ • 将大矩阵划分为 BLOCK × BLOCK 的小块 │ │ • 将一个小块加载到缓存中进行所有操作 │ │ • 保证缓存能同时容纳 A 块、B 块和 C 块的相关部分 │ │ • 大幅减少缓存未命中 │ │ │ └─────────────────────────────────────────────────────────────────────┘六、存储器山存储器山Memory Mountain是读吞吐量读带宽随工作集大小和访问步长变化的函数。┌─────────────────────────────────────────────────────────────────────┐ │ 存储器山概念图 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ 吞吐量 ▲ │ │ (MB/s) │ │ │ │ ╱────────────────╲ │ │ │ ╱ L1 峰值 ╲ │ │ │ ╱ (寄存器级) ╲ │ │ │ ╱ ╲ │ │ │ ╱ L2 缓存级 ╲ │ │ │ ╱ ╲ │ │ │ ╱ L3 缓存级 ╲ │ │ │ ╱ ╲ │ │ │╱ 主存级 ╲ │ │ └────────────────────────────────────→ 工作集大小 │ │ │ │ 存储器山揭示了 │ │ • 缓存在不同层级提供不同的带宽 │ │ • 步长越小、工作集越小吞吐量越高 │ │ • 是衡量程序局部性的直观工具 │ │ │ └─────────────────────────────────────────────────────────────────────┘七、配套实验Cache Lab第 6 章对应的经典实验是Cache Lab帮助我们了解缓存对 C 语言性能的影响。实验分为两个部分。7.1 Part A缓存模拟器在csim.c中编写一个缓存模拟器以 valgrind 内存跟踪为输入模拟缓存命中/未命中行为输出命中、未命中和逐出的总数。// 缓存行结构typedefstruct{unsignedlonglongtag;// 标记位intvalid;// 有效位inttimestamp;// LRU 时间戳// uint8_t *blocks; // 数据块模拟中不需要}Line;// 缓存组结构typedefstruct{size_tline_count;Line*lines;}Set;// 缓存结构typedefstruct{intset_num;// 组数intline_num;// 每组的行数Set*sets;}Sim_Cache;实验要点采用 LRU最近最少使用替换策略处理 L加载、S存储、M修改相当于 L S三种操作缓存大小、相联度、块大小通过命令行参数指定使用valgrind生成的 trace 文件作为测试输入7.2 Part B矩阵转置优化优化矩阵转置函数目标是最小化缓存未命中次数。测试场景矩阵大小满分要求缓存配置32 × 32misses 300s5, E1, b532 组每组 1 行块大小 32 字节64 × 64misses 1300同上61 × 67misses 2000同上核心限制最多 12 个局部变量不能用 malloc不能修改 A 矩阵只能修改 B 矩阵。// 32×32 矩阵的优化转置分块策略voidtranspose_32x32(intM,intN,intA[N][M],intB[M][N]){inti,j,i1,j1;constintBLOCK8;// 块大小一个块可以放 8 个 intfor(i0;iN;iBLOCK){for(j0;jM;jBLOCK){for(i1i;i1iBLOCK;i1){for(j1j;j1jBLOCK;j1){if(i1!j1){B[j1][i1]A[i1][j1];}else{// 对角线元素特殊处理避免冲突inttmpA[i1][j1];B[j1][i1]tmp;}}}}}}┌─────────────────────────────────────────────────────────────────────┐ │ Part B 分块策略分析 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ 缓存配置分析 │ │ • s5 → 32 个组 │ │ • E1 → 直接映射每组只有 1 行 │ │ • b5 → 块大小 32 字节 → 可存 8 个 int │ │ │ │ 为什么分块有效 │ │ • 转置时B 矩阵按列访问空间局部性差 │ │ • 大矩阵转置会导致严重冲突不命中 │ │ • 使用 8×8 分块每个块大小正好能利用缓存块特性 │ │ • 一次处理一个块块内数据可缓存在缓存中大幅减少 miss │ │ │ │ ⚠️ 难点64×64 矩阵需要更精细的策略 │ │ → 需要使用 4×4 分块与 8×8 分块结合或对角线元素特殊处理 │ │ │ └─────────────────────────────────────────────────────────────────────┘八、本章知识点思维导图第 6 章 存储器层次结构 │ ├── 1. 存储技术 │ ├── RAM │ │ ├── SRAM静态6 晶体管/位cache │ │ └── DRAM动态1 晶体管电容/位主存 │ ├── 非易失性存储器 │ │ ├── PROM/EPROM/EEPROM │ │ └── FlashSSD 基础 │ ├── 磁盘 │ │ ├── T_seek寻道3-9 ms │ │ ├── T_rotation旋转4-8 ms │ │ └── T_transfer传送~0.02 ms │ └── SSD闪存技术无机械部件 │ ├── 2. 局部性 │ ├── 时间局部性同一位置被多次引用 │ ├── 空间局部性附近位置被引用 │ └── 取指令的局部性循环 │ ├── 3. 存储器层次结构 │ ├── L0 寄存器编译器管理 │ ├── L1-L3 缓存硬件管理 │ ├── L4 主存OS 管理 │ ├── L5 本地磁盘OS 管理 │ └── L6 远程存储 │ ├── 4. 高速缓存 │ ├── 参数S组数、E相联度、B块大小 │ ├── 地址划分tag | set index | block offset │ ├── 映射方式 │ │ ├── 直接映射E1 │ │ ├── 组相联1 E C/B │ │ └── 全相联E C/B │ ├── 不命中类型 │ │ ├── 强制性/冷不命中 │ │ ├── 冲突不命中 │ │ └── 容量不命中 │ ├── 写策略 │ │ ├── 写命中写直达 vs 写回 │ │ └── 写缺失写分配 vs 非写分配 │ └── i-cache / d-cache / 统一缓存 │ ├── 5. 缓存友好代码 │ ├── 步长 1 访问 │ ├── 分块技术 │ └── 循环优化 │ ├── 6. 存储器山 │ ├── 读吞吐量 vs 工作集大小 │ └── 步长对带宽的影响 │ └── 7. Cache Lab ├── Part A缓存模拟器 │ ├── 解析 trace 文件 │ ├── LRU 替换策略 │ └── 输出 hit/miss/eviction └── Part B矩阵转置优化 ├── 32×328×8 分块 ├── 64×64更精细策略 └── 61×67分块优化九、本章小结第 6 章深入揭示了计算机系统中存储器层次结构的全貌✅存储技术理解了 SRAM 与 DRAM 的区别、非易失性存储器的种类以及磁盘和 SSD 的工作原理与性能特征✅局部性原理掌握了时间局部性和空间局部性的概念这是缓存工作的理论基石✅存储器层次结构理解了 L0~L6 各层之间的关系——每一层都是下一层的缓存✅缓存组织结构掌握了 S、E、B 三个参数的含义理解了直接映射、组相联、全相联三种映射方式的差异与适用场景✅写策略理解了写直达 vs 写回、写分配 vs 非写分配的权衡✅缓存友好编程学会了分块、循环展开等技术来编写缓存友好的代码✅Cache Lab 实验通过模拟缓存和优化矩阵转置将理论知识转化为实践能力本章最核心的三个洞察局部性是程序的基本属性——良好的程序设计应充分利用局部性原理使热数据始终留在缓存中分块是缓存友好的核心技术——当处理无法放入缓存的大数据结构时分块可以有效减少容量不命中直接映射缓存的冲突不命中是需要警惕的——当两个数据映射到同一组时会相互驱逐导致性能剧烈下降可以通过调整数据结构大小或使用更高相联度的缓存来缓解 下一篇预告下一章我们将进入第 7 章链接。这一章将深入探讨程序从目标文件到可执行文件的组装过程链接的基本概念静态链接 vs 动态链接目标文件的类型可重定位目标文件、可执行目标文件、共享目标文件符号解析全局符号、局部符号、强符号与弱符号的规则重定位如何将目标文件中的逻辑地址转换为最终的内存地址静态库使用ar命令创建和使用静态库动态链接共享库的加载时链接和运行时链接库打桩在程序执行过程中拦截和替换库函数调用的技术位置无关代码PIC共享库的内存布局与 GOT/PLT 机制第 7 章将帮助我们理解程序加载和链接的幕后机制这是编写大型程序和解决链接错误的关键知识。敬请期待本文为个人学习笔记仅用于知识分享。如有错误欢迎指正。 点赞 收藏 分享让更多开发者看到这篇深度解析❤️ 如果觉得有用请给个赞支持一下作者
《深入理解计算机系统》读书笔记07: 存储器层次结构
发布时间：2026/7/12 20:45:15
作者: andylin02学习章节: 第 6 章 存储器层次结构关键词 随机访问存储器(SRAM/DRAM)非易失性存储器(ROM/Flash)局部性原理存储器层次结构高速缓存直接映射组相联全相联写策略分块存储器山Cache Lab引言跨越存储墙“一个编写良好的程序倾向于展示出良好的局部性。”—— CSAPP 作者在计算机系统模型中CPU 执行指令而存储器系统为 CPU 存放指令和数据。如果你需要的数据在 CPU 寄存器中访问它只需要 0 个周期如果在高速缓存中需要 4~75 个周期如果在主存中需要上百个周期而如果存储在磁盘上则需要大约几千万个周期CPU 与存储器之间的这种速度差距被称为存储墙Memory Wall——处理器的性能每年都在提升而主存的访问速度提升却相对缓慢。存储器层次结构正是为了解决这一矛盾而设计的核心思想通过在不同速度、不同容量的存储设备之间建立层级关系用局部性原理来弥合 CPU 与存储器之间的速度鸿沟。本章结构速览6.1 存储技术SRAM、DRAM、ROM、Flash、磁盘、SSD6.2 局部性时间局部性与空间局部性6.3 存储器层次结构核心思想与工作原理6.4 高速缓存存储器组织结构、映射方式、写策略6.5 编写缓存友好的代码分块技术、循环优化6.6 存储器山量化程序性能Cache Lab 配套实验Part A 缓存模拟器 Part B 矩阵转置优化一、存储技术1.1 随机访问存储器RAMRAM 分为两类静态的和动态的。SRAM 比 DRAM 更快但也贵得多。SRAM 用作高速缓存存储器既可以在 CPU 芯片上也可以在片下。DRAM 用作主存以及图形系统的帧缓冲区。静态 RAMSRAMSRAM 将每个位存储在一个双稳态的存储器单元中每个单元通常由 6 个晶体管实现。双稳态意味着电路可以无限期地保持在两个不同的电压状态之一其他任何状态都是不稳定的。只要有电SRAM 就会永远保持它的值。即使受到干扰当干扰消除时电路也会恢复到稳定值。动态 RAMDRAMDRAM 将每个位存储为对一个电容的充电每个单元由一个电容和一个访问晶体管组成。由于电容会漏电DRAM 需要定期刷新通常每 64ms。DRAM 对干扰非常敏感——当电容的电压被扰乱后它永远不会恢复。SRAM vs DRAM 对比特性SRAMDRAM每位晶体管数61相对访问时间1×10×需要刷新否是干扰敏感否是相对花费1000×1×主要应用高速缓存主存、帧缓冲区核心洞察SRAM 用晶体管密度换取了速度DRAM 用速度和稳定性换取了容量——这是典型的工程权衡。┌─────────────────────────────────────────────────────────────────────┐ │ DRAM 芯片组织结构 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ DRAM 芯片划分为 d 个超单元每个超单元包含 w 个 DRAM 单元 │ │ w 一般为 8。超单元按 r 行 c 列组织rc d。 │ │ │ │ ┌─────────────────────────────────────────┐ │ │ │ 列地址 │ │ │ │ ↓ │ │ │ │ ┌────┬────┬────┬────┐ │ │ │ 行 │ │(0,0)│(0,1)│(0,2)│(0,3)│ ← 行 0 │ │ │ 地 │ ├────┼────┼────┼────┤ │ │ │ 址 │ │(1,0)│(1,1)│(1,2)│(1,3)│ ← 行 1 │ │ │ │ ├────┼────┼────┼────┤ │ │ │ → │ │(2,0)│(2,1)│(2,2)│(2,3)│ ← 行 2 │ │ │ │ ├────┼────┼────┼────┤ │ │ │ │ │(3,0)│(3,1)│(3,2)│(3,3)│ ← 行 3 │ │ │ │ └────┴────┴────┴────┘ │ │ │ └─────────────────────────────────────────┘ │ │ │ │ 读取超单元 (2,1) 的步骤 │ │ 1. 内存控制器发送行地址 i2DRAM 将整个第 2 行复制到内部行缓冲区 │ │ 2. 内存控制器发送列地址 j1DRAM 从行缓冲区中复制超单元 (2,1) │ │ 发送给内存控制器 │ │ │ └─────────────────────────────────────────────────────────────────────┘内存模块每个 DRAM 芯片被连接到内存控制器。多个 DRAM 芯片封装在内存模块中插到主板的扩展槽上。常用的是双列直插内存模块DIMM以 64 位为块与内存控制器交换数据。1.2 非易失性存储器ROMROM 设备断电后仍能保持数据。由于历史原因它们被统称为只读存储器但实际上有些 ROM 是可写的ROM 类型擦写方式擦写次数PROM一次可编程用高电流熔断1EPROM紫外线整块擦除~1000EEPROM电子信号擦除~10^5Flash基于 EEPROM以块为单位擦除104~106存储在 ROM 设备中的程序通常被称为固件Firmware包括 BIOS、磁盘控制器固件等。固态硬盘SSD基于闪存技术将闪存翻译层和多个闪存芯片封装在一起。1.3 机械磁盘从磁盘上读信息的时间为毫秒级比从 DRAM 读慢了 10 万倍比从 SRAM 读慢了 100 万倍。┌─────────────────────────────────────────────────────────────────────┐ │ 机械磁盘访问时间 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ T_access T_seek T_rotation T_transfer │ │ │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ T_seek寻道时间 ≈ 3-9 ms │ │ │ │ → 移动传送臂将读/写头定位到目标磁道 │ │ │ ├─────────────────────────────────────────────────────────────┤ │ │ │ T_rotation旋转时间 ≈ 4-8 ms │ │ │ │ → 等待磁盘旋转到目标扇区平均半圈 │ │ │ ├─────────────────────────────────────────────────────────────┤ │ │ │ T_transfer传送时间 ≈ 0.02 ms │ │ │ │ → 读取整个扇区内容到控制器缓冲区 │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ │ │ 磁盘访问时间主要由机械运动决定毫秒级比 CPU 操作慢了 │ │ 数百万倍这也是为什么使用内存可以极大加速程序运行的根本原因。 │ │ │ └─────────────────────────────────────────────────────────────────────┘1.4 固态硬盘SSDSSD 是一种基于闪存的存储技术。一个固态硬盘中封装了一个闪存翻译层和多个闪存芯片。闪存翻译层是一个硬件/固件设备负责处理来自 CPU 的请求并管理闪存芯片的读写。SSD 没有机械运动部件因此随机访问速度远快于机械硬盘但寿命有限闪存擦写次数限制。1.5 连接 CPU 与存储器的典型总线结构一条总线是由多条并排的电线组成的一束线传输地址、数据和控制信号多个设备共享多条总线。┌─────────────────────────────────────────────────────────────────────┐ │ CPU 到主存的访问流程 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ CPU 执行 movq A, %rax │ │ │ │ ┌──────┐ ┌──────────┐ ┌──────────┐ │ │ │ CPU │─────→│ 系统总线 │─────→│ I/O桥 │ │ │ └──────┘ └──────────┘ └────┬─────┘ │ │ │ ▲ │ │ │ │ │ │ │ │ │ │ ┌───┴───┐ │ │ │ └──────────│内存总线│ │ │ │ └───┬───┘ │ │ │ │ │ │ │ ┌───┴───┐ │ │ │ │ 主存 │ │ │ │ └───────┘ │ │ │ │ │ ┌───┴───┐ ┌──────────┐ ┌──────────┐ │ │ │ CPU │←─────│ 系统总线 │←─────│ I/O桥 │ │ │ └───────┘ └──────────┘ └────┬─────┘ │ │ │ │ │ ┌───┴───┐ │ │ │ 主存 │ │ │ └───────┘ │ │ │ │ 读操作步骤 │ │ 1. CPU 将地址 A 放到系统总线上I/O 桥将信号传递到内存总线 │ │ 2. 主存从内存总线读地址从 DRAM 取出数据字将数据写到内存总线 │ │ 3. I/O 桥将内存总线信号翻译成系统总线信号沿系统总线传递 │ │ 4. CPU 从系统总线读数据复制到寄存器 %rax │ │ │ └─────────────────────────────────────────────────────────────────────┘二、局部性“程序倾向于引用邻近于其他最近引用过的数据项的数据项或者最近引用过的数据项本身。这种倾向被称为局部性原理。”局部性是程序运行的基本属性也是存储器层次结构能够生效的根本原因。如果程序没有局部性那么任何层次的缓存都会失效——因为每次访问的数据都不在缓存中。2.1 局部性的两种形式┌─────────────────────────────────────────────────────────────────────┐ │ 局部性原理示意图 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ 时间局部性Temporal Locality │ │ │ │ 被引用过一次的内存位置很可能在不远的将来再被多次引用 │ │ │ │ → 示例循环中的累加器变量、函数中的局部变量 │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ 空间局部性Spatial Locality │ │ │ │ 如果一个内存位置被引用了一次那么程序很可能在不远的将来 │ │ │ │ 引用附近的一个内存位置 │ │ │ │ → 示例顺序访问数组元素、遍历链表 │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ │ └─────────────────────────────────────────────────────────────────────┘2.2 数据引用的局部性分析// 示例数组求和intsum_array(inta[M][N]){inti,j,sum0;for(i0;iM;i){for(j0;jN;j){suma[i][j];// 按行遍历步长 1}}returnsum;}这个函数的局部性分析sum变量良好的时间局部性每次循环都被访问a[i][j]良好的空间局部性按行优先访问步长为 1i和j良好的时间局部性在循环中反复更新2.3 局部性小结重复引用相同变量的程序有良好的时间局部性步长 k 越小空间局部性越好取指令指令获取——循环有好的时间和空间局部性核心原则将注意力集中在内循环上因为大部分计算和存储器访问都集中在这里三、存储器层次结构3.1 核心思想存储器层次结构的基本思想是对于每个 k位于 k 层的更快更小的存储设备作为位于 k1 层的更大更慢的存储设备的缓存。┌─────────────────────────────────────────────────────────────────────┐ │ 存储器层次结构 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ L0: 寄存器 ←─── 管理编译器 │ │ ↑ │ │ L1: L1 高速缓存 ←─── 管理硬件 │ │ ↑ │ │ L2: L2 高速缓存 ←─── 管理硬件 │ │ ↑ │ │ L3: L3 高速缓存 ←─── 管理硬件 │ │ ↑ │ │ L4: 主存 ←─── 管理操作系统 │ │ ↑ │ │ L5: 本地磁盘 ←─── 管理操作系统 │ │ ↑ │ │ L6: 远程存储 ←─── 管理操作系统/网络 │ │ │ │ 层次结构的本质每一层都是下一层的缓存 │ │ → 从寄存器到磁盘越往下速度越慢、容量越大、成本越低 │ │ │ └─────────────────────────────────────────────────────────────────────┘3.2 缓存的基本概念从逻辑上看缓存是一个数组每个数组元素是一个缓存块。由于缓存的容量远小于下层存储需要将数据映射到缓存中缓存命中第 k 层缓存了需要的数据对象 d缓存不命中第 k 层没有缓存 d需要从第 k1 层取出替换/驱逐从缓存中覆盖一个现存块牺牲块被驱逐的块冷缓存空的缓存导致的缓存不命中称为强制性不命中或冷不命中冲突不命中由限制性放置策略引起容量不命中当活跃块集合工作集的大小比缓存大时发生3.3 缓存的管理者缓存类型缓存什么被缓存在何处管理方式寄存器4-8 字节字CPU 核心编译器TLB地址翻译处理器硬件L1/L2/L3 Cache64 字节块处理器硬件DRAM主存处理器硬件虚拟内存4KB 页主存操作系统磁盘文件磁盘操作系统四、高速缓存存储器4.1 通用组织结构一个高速缓存由 S 个组Set组成每组包含 E 个缓存行Line每个缓存行包含一个有效位、t 个标记位和一个大小为 B 字节的数据块┌─────────────────────────────────────────────────────────────────────┐ │ 高速缓存通用组织结构 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ C S × E × B │ │ │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ Cache │ │ │ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │ │ │ │ Set 0 │ │ Set 1 │ │ ... │ │ Set S-1 │ │ │ │ │ │ ┌─────┐ │ │ ┌─────┐ │ │ │ │ ┌─────┐ │ │ │ │ │ │ │Line0│ │ │ │Line0│ │ │ │ │ │Line0│ │ │ │ │ │ │ │ v│t│ 块 │ │ │ v│t│ 块 │ ... │ │ │ v│t│ 块 │ │ │ │ │ │ ├─────┤ │ │ ├─────┤ │ │ │ │ ├─────┤ │ │ │ │ │ │ │Line1│ │ │ │Line1│ │ │ │ │ │Line1│ │ │ │ │ │ │ └─────┘ │ │ └─────┘ │ │ │ │ └─────┘ │ │ │ │ │ └─────────┘ └─────────┘ └─────────┘ └─────────┘ │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ │ │ 其中 │ │ S 组数Set 数量 │ │ E 相联度每组行数 │ │ B 块大小Bytes per block │ │ C S × E × B 缓存总容量 │ │ │ └─────────────────────────────────────────────────────────────────────┘4.2 内存地址的划分在缓存访问中内存地址被划分为三个字段┌─────────────────────────────────────────────────────────────────────┐ │ 内存地址划分 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ 地址位 (t位) (s位) (b位) │ │ ┌────────┬─────────┬─────────┐ │ │ │ tag │ set idx │ block │ │ │ │ │ │ offset │ │ │ └────────┴─────────┴─────────┘ │ │ │ │ 各字段含义 │ │ • tag标记位唯一标识缓存行 │ │ • set idx组索引定位到具体组 │ │ • block offset块内偏移在块中定位具体字节 │ │ │ │ S 2^s │ │ B 2^b │ │ │ └─────────────────────────────────────────────────────────────────────┘4.3 三种映射方式① 直接映射高速缓存E 1最简单的情况每组只有 1 个缓存行。每次根据 set index 直接找到对应组比较 tag 是否匹配。┌─────────────────────────────────────────────────────────────────────┐ │ 直接映射缓存E1 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ 查找步骤 │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ 1. 组选择根据 set index 定位到对应的组 │ │ │ │ 2. 行匹配检查该组唯一的行的 tag 是否与地址的 tag 匹配 │ │ │ │ 3. 字抽取如果匹配且 valid1根据 block offset 取出数据 │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ │ │ ⚠️ 缺点如果两个地址的 set index 相同会交替访问对方 │ │ 导致冲突不命中抖动现象 │ │ │ └─────────────────────────────────────────────────────────────────────┘② 组相联高速缓存1 E C/B每组有 E 个缓存行。当组中有多个空行时可以放置多个块冲突不命中得到缓解。没有空行时需要选择一个牺牲行进行替换。替换策略策略全称规则LRULeast Recently Used替换最后一次访问时间最久远的一行LFULeast Frequently Used替换过去某个时间窗口内引用次数最少的一行随机Random随机选择一行替换③ 全相联高速缓存E C/B所有缓存行都在同一个组中。地址被划分为标记和块偏移没有组索引位。┌─────────────────────────────────────────────────────────────────────┐ │ 三种映射方式对比 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ ┌─────────────┬─────────────┬─────────────┬─────────────┐ │ │ │ 映射方式 │ 每组行数 │ 冲突情况 │ 实现难度 │ │ │ ├─────────────┼─────────────┼─────────────┼─────────────┤ │ │ │ 直接映射 │ E 1 │ 冲突严重 │ 简单 │ │ │ ├─────────────┼─────────────┼─────────────┼─────────────┤ │ │ │ 组相联 │ E 1 │ 明显缓解 │ 中等 │ │ │ ├─────────────┼─────────────┼─────────────┼─────────────┤ │ │ │ 全相联 │ E C/B │ 无冲突 │ 复杂 │ │ │ └─────────────┴─────────────┴─────────────┴─────────────┘ │ │ │ │ 真实系统中L1 Cache 常用 8 路组相联L2/L3 使用更高路数 │ │ │ └─────────────────────────────────────────────────────────────────────┘4.4 写策略写操作比读操作复杂因为写完缓存后主存里的副本也需要处理。写命中Write Hit策略策略规则优点缺点写直达写缓存的同时立即写下一级存储实现简单主存始终与缓存一致每次写都要访问主存产生大量总线流量写回只写缓存暂不写主存打上脏位驱逐时才写回主存大幅减少总线流量性能好每条缓存行需要额外的脏位逻辑更复杂场景对比连续对同一地址写 100 次写直达需要 100 次主存写写回只需 1 次主存写。写缺失Write Miss策略策略规则写分配先从下一级加载该块到缓存再在缓存中执行写操作非写分配绕过缓存直接写到下一级存储典型组合写回 写分配推荐利用空间局部性写直达 非写分配真实系统中低层更常用写回策略4.5 真实缓存层次结构现代处理器通常有多个独立的缓存i-cache只保存指令的高速缓存通常是只读的d-cache只保存数据的高速缓存统一缓存同时保存指令和数据4.6 缓存参数的性能影响参数影响命中时间从缓存向处理器发送一行的时间L1 约 4 周期L2 约 10 周期不命中惩罚由于不命中需要额外的时间主存约 50-200 周期不命中率内存引用在缓存中没找到的比例块大小块越大对空间局部性越好块越多对时间局部性命中率有损害相联度越高抖动越少但实现复杂度和访问速度受影响五、编写缓存友好的代码5.1 核心原则将注意力集中在内循环上因为大部分计算和存储器访问都集中在这里按照数据对象在存储器中存放的顺序以步长为 1来读取数据可使空间局部性最佳5.2 分块Blocking技术分块是将一个大矩阵划分为若干小块进行处理使每个小块可以完全放入缓存中从而减少缓存不命中。// 矩阵乘法的分块优化示例#defineBLOCK8// 块大小voidmatrix_multiply_block(intn,intA[n][n],intB[n][n],intC[n][n]){inti,j,k,i1,j1,k1;for(i0;in;iBLOCK){for(j0;jn;jBLOCK){for(k0;kn;kBLOCK){// 对 BLOCK × BLOCK 的块进行运算for(i1i;i1iBLOCK;i1){for(k1k;k1kBLOCK;k1){for(j1j;j1jBLOCK;j1){C[i1][j1]A[i1][k1]*B[k1][j1];}}}}}}}┌─────────────────────────────────────────────────────────────────────┐ │ 分块技术原理示意图 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ 矩阵 A 矩阵 B │ │ ┌─────────────────┐ ┌─────────────────┐ │ │ │ ██████│ │ │ ██████│ │ │ │ │ ██████│ │ │ ██████│ │ │ │ │ ──────┼─────────│ │ ──────┼─────────│ │ │ │ │ │ │ │ │ │ │ └─────────────────┘ └─────────────────┘ │ │ │ │ 分块策略 │ │ • 将大矩阵划分为 BLOCK × BLOCK 的小块 │ │ • 将一个小块加载到缓存中进行所有操作 │ │ • 保证缓存能同时容纳 A 块、B 块和 C 块的相关部分 │ │ • 大幅减少缓存未命中 │ │ │ └─────────────────────────────────────────────────────────────────────┘六、存储器山存储器山Memory Mountain是读吞吐量读带宽随工作集大小和访问步长变化的函数。┌─────────────────────────────────────────────────────────────────────┐ │ 存储器山概念图 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ 吞吐量 ▲ │ │ (MB/s) │ │ │ │ ╱────────────────╲ │ │ │ ╱ L1 峰值 ╲ │ │ │ ╱ (寄存器级) ╲ │ │ │ ╱ ╲ │ │ │ ╱ L2 缓存级 ╲ │ │ │ ╱ ╲ │ │ │ ╱ L3 缓存级 ╲ │ │ │ ╱ ╲ │ │ │╱ 主存级 ╲ │ │ └────────────────────────────────────→ 工作集大小 │ │ │ │ 存储器山揭示了 │ │ • 缓存在不同层级提供不同的带宽 │ │ • 步长越小、工作集越小吞吐量越高 │ │ • 是衡量程序局部性的直观工具 │ │ │ └─────────────────────────────────────────────────────────────────────┘七、配套实验Cache Lab第 6 章对应的经典实验是Cache Lab帮助我们了解缓存对 C 语言性能的影响。实验分为两个部分。7.1 Part A缓存模拟器在csim.c中编写一个缓存模拟器以 valgrind 内存跟踪为输入模拟缓存命中/未命中行为输出命中、未命中和逐出的总数。// 缓存行结构typedefstruct{unsignedlonglongtag;// 标记位intvalid;// 有效位inttimestamp;// LRU 时间戳// uint8_t *blocks; // 数据块模拟中不需要}Line;// 缓存组结构typedefstruct{size_tline_count;Line*lines;}Set;// 缓存结构typedefstruct{intset_num;// 组数intline_num;// 每组的行数Set*sets;}Sim_Cache;实验要点采用 LRU最近最少使用替换策略处理 L加载、S存储、M修改相当于 L S三种操作缓存大小、相联度、块大小通过命令行参数指定使用valgrind生成的 trace 文件作为测试输入7.2 Part B矩阵转置优化优化矩阵转置函数目标是最小化缓存未命中次数。测试场景矩阵大小满分要求缓存配置32 × 32misses 300s5, E1, b532 组每组 1 行块大小 32 字节64 × 64misses 1300同上61 × 67misses 2000同上核心限制最多 12 个局部变量不能用 malloc不能修改 A 矩阵只能修改 B 矩阵。// 32×32 矩阵的优化转置分块策略voidtranspose_32x32(intM,intN,intA[N][M],intB[M][N]){inti,j,i1,j1;constintBLOCK8;// 块大小一个块可以放 8 个 intfor(i0;iN;iBLOCK){for(j0;jM;jBLOCK){for(i1i;i1iBLOCK;i1){for(j1j;j1jBLOCK;j1){if(i1!j1){B[j1][i1]A[i1][j1];}else{// 对角线元素特殊处理避免冲突inttmpA[i1][j1];B[j1][i1]tmp;}}}}}}┌─────────────────────────────────────────────────────────────────────┐ │ Part B 分块策略分析 │ ├─────────────────────────────────────────────────────────────────────┤ │ │ │ 缓存配置分析 │ │ • s5 → 32 个组 │ │ • E1 → 直接映射每组只有 1 行 │ │ • b5 → 块大小 32 字节 → 可存 8 个 int │ │ │ │ 为什么分块有效 │ │ • 转置时B 矩阵按列访问空间局部性差 │ │ • 大矩阵转置会导致严重冲突不命中 │ │ • 使用 8×8 分块每个块大小正好能利用缓存块特性 │ │ • 一次处理一个块块内数据可缓存在缓存中大幅减少 miss │ │ │ │ ⚠️ 难点64×64 矩阵需要更精细的策略 │ │ → 需要使用 4×4 分块与 8×8 分块结合或对角线元素特殊处理 │ │ │ └─────────────────────────────────────────────────────────────────────┘八、本章知识点思维导图第 6 章 存储器层次结构 │ ├── 1. 存储技术 │ ├── RAM │ │ ├── SRAM静态6 晶体管/位cache │ │ └── DRAM动态1 晶体管电容/位主存 │ ├── 非易失性存储器 │ │ ├── PROM/EPROM/EEPROM │ │ └── FlashSSD 基础 │ ├── 磁盘 │ │ ├── T_seek寻道3-9 ms │ │ ├── T_rotation旋转4-8 ms │ │ └── T_transfer传送~0.02 ms │ └── SSD闪存技术无机械部件 │ ├── 2. 局部性 │ ├── 时间局部性同一位置被多次引用 │ ├── 空间局部性附近位置被引用 │ └── 取指令的局部性循环 │ ├── 3. 存储器层次结构 │ ├── L0 寄存器编译器管理 │ ├── L1-L3 缓存硬件管理 │ ├── L4 主存OS 管理 │ ├── L5 本地磁盘OS 管理 │ └── L6 远程存储 │ ├── 4. 高速缓存 │ ├── 参数S组数、E相联度、B块大小 │ ├── 地址划分tag | set index | block offset │ ├── 映射方式 │ │ ├── 直接映射E1 │ │ ├── 组相联1 E C/B │ │ └── 全相联E C/B │ ├── 不命中类型 │ │ ├── 强制性/冷不命中 │ │ ├── 冲突不命中 │ │ └── 容量不命中 │ ├── 写策略 │ │ ├── 写命中写直达 vs 写回 │ │ └── 写缺失写分配 vs 非写分配 │ └── i-cache / d-cache / 统一缓存 │ ├── 5. 缓存友好代码 │ ├── 步长 1 访问 │ ├── 分块技术 │ └── 循环优化 │ ├── 6. 存储器山 │ ├── 读吞吐量 vs 工作集大小 │ └── 步长对带宽的影响 │ └── 7. Cache Lab ├── Part A缓存模拟器 │ ├── 解析 trace 文件 │ ├── LRU 替换策略 │ └── 输出 hit/miss/eviction └── Part B矩阵转置优化 ├── 32×328×8 分块 ├── 64×64更精细策略 └── 61×67分块优化九、本章小结第 6 章深入揭示了计算机系统中存储器层次结构的全貌✅存储技术理解了 SRAM 与 DRAM 的区别、非易失性存储器的种类以及磁盘和 SSD 的工作原理与性能特征✅局部性原理掌握了时间局部性和空间局部性的概念这是缓存工作的理论基石✅存储器层次结构理解了 L0~L6 各层之间的关系——每一层都是下一层的缓存✅缓存组织结构掌握了 S、E、B 三个参数的含义理解了直接映射、组相联、全相联三种映射方式的差异与适用场景✅写策略理解了写直达 vs 写回、写分配 vs 非写分配的权衡✅缓存友好编程学会了分块、循环展开等技术来编写缓存友好的代码✅Cache Lab 实验通过模拟缓存和优化矩阵转置将理论知识转化为实践能力本章最核心的三个洞察局部性是程序的基本属性——良好的程序设计应充分利用局部性原理使热数据始终留在缓存中分块是缓存友好的核心技术——当处理无法放入缓存的大数据结构时分块可以有效减少容量不命中直接映射缓存的冲突不命中是需要警惕的——当两个数据映射到同一组时会相互驱逐导致性能剧烈下降可以通过调整数据结构大小或使用更高相联度的缓存来缓解 下一篇预告下一章我们将进入第 7 章链接。这一章将深入探讨程序从目标文件到可执行文件的组装过程链接的基本概念静态链接 vs 动态链接目标文件的类型可重定位目标文件、可执行目标文件、共享目标文件符号解析全局符号、局部符号、强符号与弱符号的规则重定位如何将目标文件中的逻辑地址转换为最终的内存地址静态库使用ar命令创建和使用静态库动态链接共享库的加载时链接和运行时链接库打桩在程序执行过程中拦截和替换库函数调用的技术位置无关代码PIC共享库的内存布局与 GOT/PLT 机制第 7 章将帮助我们理解程序加载和链接的幕后机制这是编写大型程序和解决链接错误的关键知识。敬请期待本文为个人学习笔记仅用于知识分享。如有错误欢迎指正。 点赞 收藏 分享让更多开发者看到这篇深度解析❤️ 如果觉得有用请给个赞支持一下作者
![SortedMap与SortedSet：immutable中的有序集合完全教程 [特殊字符]](http://pic.xiahunao.cn/yaotu/SortedMap与SortedSet：immutable中的有序集合完全教程 [特殊字符])
