第 6 章 存储器层次结构
# 第 6 章 存储器层次结构
前言
- 在简单模型中,存储器系统(memory system)是一个线性的字节数组,而 CPU 能在一个常数时间内访问每个存储器位置
- 但实际上,存储器系统是一个具有不同容量、成本和访问时间的存储设备层次结构
# 6.1 储存技术
# 6.1.1 随机访问存储器
随机访问存储器 (Random-Access Memory RAM) 分为两类:静态 (SRAM) 的和动态 (DRAM) 的
- 只要有供电, SRAM 就会保持不变,但是 DRAM 需要不断的刷新
- SRAM 的抗干扰能力更强
- 如光和电噪声
- 但 SRAM 需要更多的晶体管
- 因而密集度低,价格贵,功耗大
传统的 DRAM
- DRAM 芯片中的单元(位)被分为
个超单元 - 每个超单元由
个 DRAM 单元组成 - 一个
的 DRAM 总共储存了 位信息
- 每个超单元由
DRAM 芯片的的高级视图
- 为了读出超单元
的内容 - 内存控制器先将行地址
发送到 DRAM - 称为 RAS(Row Access Strobe 行访问选通脉冲)
- 再将列地址
发送到 DRAM - 称为 CAS(Column Access Strobe 列访问选通脉冲)
- RAS 和 CAS 共享相同的 DRAM 地址引脚
- 内存控制器先将行地址
- 为了读出超单元
读一个 DRAM 超单元的内容
- 先发 RAS,读出整行的内容到缓存区,然后再发 CAS,从缓存区中选取所需要的列
二维阵列可以减小芯片上地址引脚的数量,但是必须分两次发送地址,会增加访问时间
内存模块
- DRAM 芯片封装在内存模块中,Core i7 以 64 位为块与内存控制器进行数据交换
读一个内存模块的内容
- 每个超单元含有 8 个位
- 将 8 个 DRAM 芯片组合在一起,然后内存模块再将地址信号广播到 8 个芯片,依次从中取出 1 个字节(8 位),组成一个 8 字节(64 位的块) 的块
增强的 DRAM
- 快页模式 DRAM(Fast Page Mode DRAM, FPM DRAM)
- 当从一行中连续的读取超单元时,只用发送一个 RAS 信号,后面跟着多个 CAS 信号
- 扩展数据输出 DRAM (Extended Data Out DRAM EDO DRAM)
- FPM DRAM 的增强模式,允许各个 CAS 信号在时间上更紧密一些
- 同步 DRAM (Synchronous DRAM, SDRAM)
- 用与驱动内存控制器相同的外部时钟信号的上升沿作为控制信号
- 可以提升传输速度
- 双倍数据速度同步 DRAM (Double Data-Rate Synchronous DRAM,DDR SDRAM)
- SDRAM 的一种增强,其使用两个时钟沿作为控制信号,从而使得速度翻倍
- 根据预缓冲区的大小可以划分为:DDR(2 位),DDR2(4位) 和 DDR3 (8位)
- 预缓冲区可用于提高有效带宽
- 视频 RAM(Video RAM,VRAM)
- 用于图形系统的帧缓冲区中
- 基本内容与 FPM DRAM 类似,主要区别是
- 其输出是通过依次对内部缓冲区进行移位得到的
- VRAM 允许对内存并行地读和写
非易失性的储存器
- 即使在断电后,仍然能保存信息
- 只读储存器(ROM,Read-Only Memory),即是一种非易失性存储器
- ROM 中有的类型即可以读,也可以写
- 闪存 (flash memory) 也是一种非易失性的储存器,其基于 EEPROM
- 固态硬盘 (Solid State Disk, SSD) 是一种新型的基于闪存的磁盘驱动器
- 存储在 ROM 中的程序通常被称为 固件(firmware)
访问主存
- 总线 (bus) 是一组并行的导线,能携带地址、数据和控制信号
- 数据流通过总线在 CPU 和 DRAM 主存之间来来回回
总线示意图
# 6.1.2 磁盘储存
磁盘是广为应用的保存大量数据的储存设置
- 从磁盘上读信息的时间为毫秒级,比从 DRAM 读慢了 10 万倍
磁盘构造
- 磁盘由盘片构成
- 每个盘片有两个表面 (surface)
- 每个表面由一组称为磁道 (tracker) 的同心圆组成
- 每个磁道被划分为一组扇区 (sector)
- 每个扇区保含相等数量的数据位,通常为 512 字节
- 扇区之间由一些间隙 (gap) 分开
- 间隙存储用来标识扇区的格式化位
- 柱面 (cylinder) 是所有盘片表面上到主轴中心的距离相等的磁道的集合
磁盘构造示意图
磁盘容量
- 1 GB =
字节,1 TB = 字节
磁盘操作
- 磁盘针对每个盘面都有一个独立的读写头
磁盘动态特性示意图
- 磁盘以扇区大小的块来读写数据,其访问时间大约是 10 ms
- 对扇区的访问时间有三个主要的部分
- 寻道时间
- 一般为 3 ~ 9 ms
- 与传动臂的机械伺服运行相关,很难进一步的提升
- 旋转时间
- 读/写头到达期望的磁道后,需要等待目标扇区的第一个位旋转到读/写头下
- 与磁盘的旋转速度相关,与寻道时间大致相同
- 传送时间
- 一个扇区转过读/写头的时间
- 一般较短
- 寻道时间
逻辑磁盘块
- 现代磁盘将它们的构造呈现为一个 B 个扇区大小的逻辑块序列
- 编号为
- 编号为
- 磁盘封装中有一个小的硬件/固件设备,称为磁盘控制器
- 其维护着逻辑块号和实际磁盘扇区之间的映射关系
连接 I/O 设备
- 磁盘通过 I/O 总线连接到 CPU 和主存
- Intel 的外围设备互连 (Peripheral Component Interconnect, PCI) 总线即为 I/O 总线
- 两个最常用的磁盘接口是 SCSI 和 SATA
- SCSI 更快且能支持多个磁盘驱动器,但是更贵
- SATA 只支持一个磁盘驱动器
磁盘连接示意图
访问磁盘
访问磁盘过程的示意图
- 直接内存访问 (Direct Memory Access, DMA)
- 设备可以直接执行读或写总线事务而不需要 CPU 干涉的过程,称为直接内存访问
# 6.1.3 固态硬盘
固态硬盘的特点
- 固态硬盘是一种基于闪存的储存技术
示意图
- 页的大小是 512 字节 ~ 4 KB
- 块由 32 ~ 128 页组成
- 读 SSD 要比写 SSD 要快
- 因为数据是以页为单位读写的
- 只有在一页所属的块整个被擦除后,才能写这一页
- 被擦除通常是指该块中的所有位均被设置为 1
- 一旦一个块被擦除后, 块中的每个页都可以不需要再进行擦除就写一次
- 大约进行 100 000 次重复写之后,块就会磨损坏
比起旋转磁盘,SSD 没有移动的部件,因此其随机访问时间比旋转磁盘要快,能耗更低同时也更结实
- 但是其价格比旋转磁盘要贵
# 6.1.4 存储技术趋势
存储技术
- 不同的储存技术有着不同的价格和性能折中
- 不同储存技术的价格和性能属性以截然不同的速率变化
- 对于内存和磁盘技术来说:增加密度比降低访问时间容易得多
- DRAM 和磁盘的性能滞后于 CPU 的性能
各种储存器的访问时间
- CPU 的周期时间在 2003 年附近的突变是由于多核处理器的出现
- 因为处理器的功耗正比于
- 其中
为时钟频率, 是电容(大致正比于面积), 是电压
- 其中
- 一味的提高时钟频率,会使得处理器的功耗不断增加,从而撞上了所谓的 “能量墙 (power wall)”
- 功耗不断增加,处理器的散热也会成为比较严重的问题
- 因此,在保持
不变的情况下,通过增加处理器的核数,来继续的提升性能 - 因为只要所有核的总面积不变,多核造成的能耗就能保持不变
- 只要特征尺寸继续按照摩尔定律指数性的下降,每个处理器中的核数以及每个处理器的有效性能,都会继续增加
- 简单的理解就是单个核不能做得更快,就将任务分给多个核同时来做
- 因为处理器的功耗正比于
- CPU 的周期时间在 2003 年附近的突变是由于多核处理器的出现
- 随着多核的出现,多个处理器核并发地向 DRAM 和磁盘发请求, DRAM 和磁盘的吞吐量也变得越来越重要
现代计算机较多使用基于 SRAM 的高速缓存来弥补处理器-内存之间的差距
这种方法行之有效是因为应用程序的一个称为 局部性 (locality) 的基本属性
# 6.2 局部性
局部性
- 一个编写良好的的计算机程序常具有良好的局部性 (locality)
- 它倾向于引用邻近于其它最近被引用过的数据项的数据项,或者最近引用过的数据项本身
时间局部性 (temporal locality) 和空间局部性 (spatial locality)
- 在具有良好时间局部性的程序中
- 被引用过一次的内存位置很可能在不远的将来再被多次引用
- 在具有良好的空间局部性的程序中
- 如果一个内存位置被引用了一次
- 那么程序很可能在不远的将来引用其附近的一个内存位置
局部性原理的应用
- 在硬件层,计算机设计者通过引入称为 高速缓存存储器 的小而快的存储器来保存最近引用的指令和数据项
- 在操作系统层面,局部性原则允许系统将主存用作虚拟地址空间中最近引用的块的缓存
- 操作系统用主存来缓存磁盘文件系统中最近被使用的磁盘块
# 6.2.1 对程序数据引用的局部性
引用模式
- 步长为 1 的引用模式 (stride-1 reference pattern) 称为顺序引用模式
- 相对于元素的大小
- 在一个连续的向量中,每隔
个元素进行访问,就称为步长为 的引用模式 - 一般而言,随着步长的增加,空间局部性下降
# 6.2.2 取指令的局部性
CPU 只会从内存中读出它的指令,其很少会重写或修改这些指令
# 6.2.3 局部性小结
局部性小结
- 重复引用相同变量的程序具有良好的时间局部性
- 对于具有步长为
的引用模式的程序,步长越小,空间局部性越好 - 对于取指令来说,循环具有良好的时间和空间局部性
- 循环体越小,循环执行的次数越多,局部性越好
# 6.3 存储器层次结构
存储技术和计算机软件的一些基本和持久的属性
- 存储技术
- 不同存储技术的访问时间差异很大
- 速度较快的技术每字节的成本要比速度慢的技术高,而且容量较小
- CPU 和主存之间的速度差距在增大
- 计算机软件
- 一个编写良好的程序倾向于展现出良好的局部性
硬件和软件的基本属性互相补充的很完美,借助这种性质,可以采用一种组织存储器系统的方法
- 称为存储器的层次结构 (memory hierarchy)
存储器层次结构
- 示意图
- 从高层往低层走,储存设备变得更慢、更便宜和更大
- 有时磁带也是存储器结构层次中的一层,其位于本地磁盘层的下面
- 固态硬盘在存储器层次结构中,能连接起 DRAM 和旋转磁盘之间的鸿沟
# 6.3.1 存储层次结构中的缓存
高速缓存
- 存储器层次结构的中心思想是
- 对于每个
- 位于
层的更小更快的存储设备作为位于 层更大更慢的储存设备的缓存
- 对于每个
- 数据总是以块大小为传送单元 (transfer unit) 在第
层和第 层之间来回复制 - 一般而言,层次结构中较低层的设备访问时间较长,为了补偿这些较长的访问时间,倾向于使用较大的块
缓存原理示意图
缓存命中
- 当程序需要第
层的某个数据对象 时 - 其首先在当前存储在第
层的一个块中查找 - 如果
刚好缓存在第 层,则称为缓存命中 (cache hit)
缓存不命中
- 如果第
层中没有缓存数据对象 ,则称为缓存不命中 (cache miss) - 当发生缓存不命中时,第
层的缓存从第 层取出包含 的那个块 - 如果此时第
层的缓存已满,则可能覆盖现存的一个块
- 如果此时第
- 覆盖一个现存块的过程称为 替换 (replacing) 或 驱逐(evicting)
- 被驱逐的这个块有时也称为 牺牲块 (victim block)
- 决定该替换哪个块是由缓存的 替换策略 (replacement policy) 来控制的
- 随机替换策略 的缓存会随机选择一个牺牲块
- LRU 替换策略的缓存会选择那个最后被访问的时间距现在最远的块
缓存不命中的种类
- 强制不命中 (compulsory miss) 或 冷不命中(cold miss)
- 一个空的缓存对任何数据对象的访问都会不命中
- 此时称为强制不命中 (compulsory miss) 或 冷不命中 (cold miss)
- 一个空的缓存也被称为 冷缓存 (cold cache)
- 通常是短暂事件,不会在反复访问存储器使得缓存 暖身 (warmed up) 之后的稳定状态中出现
- 一个空的缓存对任何数据对象的访问都会不命中
- 冲突不命中 (conflict miss)
- 放置策略 (placement policy)
- 只要发生了不命中,第
层的缓存就要执行某个放置策略,确定把它从第 层取出的块放在哪里 - 最灵活的替换策略是允许来自
层的任何块放在第 层的任何块中 - 对于储存层次结构中高层的缓存 (靠近 CPU),其是用硬件来实现的,而且速度非常重要
- 如果随机的放置块,则实现起来通常很昂贵,而且定位起来的时间代价很高
- 对于储存层次结构中高层的缓存 (靠近 CPU),其是用硬件来实现的,而且速度非常重要
硬件缓存通常使用更严格的放置策略,由此可能会导致冲突不命中
- 只要发生了不命中,第
- 放置策略 (placement policy)
- 容量不命中 (capacity miss)
- 当工作集的大小超过缓存的大小时,缓存会经历容量不命中
- 强制不命中 (compulsory miss) 或 冷不命中(cold miss)
管理缓存的逻辑可以是硬件、软件,或者是两者的结合
- 大多数情况下,缓存都是自动运行的,不需要程序采取特殊或显式的行动
# 6.3.2 存储器层次结构概念小结
基于缓存的存储器层次结构行之有效的原因
现代计算机系统中的缓存
# 6.4 高速缓存存储器
# 6.4.1 通用的高速缓存存储器组织结构
高速缓存的通用组织
查找类似于极其简单的哈希函数的哈希表
- 首先根据地址中的
位的组索引找到分组 - 再根据
位标记位确定行 - 如果找不到标记位相匹配的行,则发生了缓冲不命中
- 如果找到了行 ,则根据
位块偏移确定块的位置
- 首先根据地址中的
- 高速缓存的容量
- 容量不包括有效位和标记位
将地址的高位用做标记位,从而可以将较大的储存空间映射到较小的储存空间
- 因为不同的地址,其组索引和块偏移可能相同
- 此时它们会被映射到同一个组中
- 这时可以通过标记位对它们进行区分
- 因为不同的地址,其组索引和块偏移可能相同
# 6.4.2 直接映射高速缓存
每个组只有一行的高速缓存称为直接映射高速缓存 (direct-mapped cache)
- 由于每组只有一行,极易导致冲突不命中,也就是“抖动”
- 即高速缓存反复地加载和驱逐相同的高速缓存块的组
- 参照 P431 页的示例
# 6.4.3 组相联高速缓存
组相联高速缓存 (set associative cache) 每个组都保存有多于一个的高速缓存行
组相联高速缓存中不命中时的行替换
LRU 翻译为最近最少使用有歧义
# 6.4.4 全相联高速缓存
全相联高速缓存 (fully associative cache) 是由一个包含所有高速缓存行的组组成的
# 6.4.5 有关写的问题
写命中的处理方法(write hit)
- 分为直写 (write-through) 和写回 (write-back)
写不命中的处理方法
- 分为写分配 (write-allocate) 和非写分配 (not-write-allocate)
写回和写分配的高速缓存的模型更加符合当前的发展趋势
# 6.4.6 一个真实的高速缓存层次结构的解剖
Intel Core i7 的高速缓存层次结构
- 示意图
i-cache
* 只保存指令的高速缓存d-cache
- 只保存数据的高速缓存
- 统一的高速缓存 (unified cache)
- 即保存指令又保存数据的高速缓存
- i7 中有两个独立的高速缓存
i-cache
和d-cache
- 目的是让处理器能同时读一个指令字和一个数据字
Intel Core i7 各级高速缓存的特性
# 6.4.7 高速缓存参数的性能影响
衡量高速缓存性能的指标
高速缓存参数对性能的影响
# 6.5 编写高速缓存友好的代码
应把注意力集中在核心函数里的循环上,而忽略其他部分
两个编写高速缓存友好的代码的要点
- 对局部变量的反复引用是好的
- 因为编译器能将它们缓存在寄存器文件中
- 利用了时间局部性
- 步长为 1 的引用模式是好的
- 因为储存器层次结构中所有层次的缓存都是将数据储存为连续的块
- 利用了空间局部性
# 6.6 综合:高速缓存对程序性能的影响
# 6.6.1 存储器山
一个程序从储存系统中读数据的速率称为 读吞吐量 (read throughput)
存储器山 (memory mountain)
- MB/s 为
字节/秒
时间局部性的山脊
- 垂直于工作集大小轴有四条山脊 (ridges)
- 分别对应工作集完全位于 L1,L2,L3 和主存内的时间局部性区域
- 工作集过大,无法全部装入高速缓存时,其时间局部性会变差
- 因为加载进高速缓存中的变量,没有被多次使用,就会被新加载进来的量给覆盖掉
空间局部性的山坡
- 在 L2,L3 和主存的山脊上,随着步长的增加,有一个与空间局部性相关的山坡(slope)
- 从图中可以看出,即使工作集过大,以至于其不能装入任何一个高速缓存时
- 主存山脊的最高点也比它的最低点高 8 倍
- 说明即使当程序的时间局部性很差时,空间局部性仍然能补救
#
硬件预取 (prefetching) 机制
- 步长为 1 时,有一条垂直于步长轴的平坦的山脊线,此时吞吐量保持在 12 GB/s
- 即使此时的工作集超出了 L1 和 L2 的大小
- 这主要归功于 Core i7 的硬件预取机制
- 其能自动的识别顺序的,步长为 1 的引用模式,从而在一些块被访问之前,将它们取到高速缓存中
# 6.6.2 重新排列循环以提升空间局部性
矩阵的乘法
- 矩阵的乘法需要 3 层循环,通过调整循环的排列,可以提升最内层循环的空间局部性,从而提升程序性能
- 分析具体的空间局部性时,只针对最内层的循环进行分析即可
- 所以,最终 6 种可能可以简化为书中的 3 种类型
-
- 注意,程序中局部变量的使用,可以减少加载次数以及未命中次数
- 核心思想是消除循环中矩阵列方向上的步长增长
- 对于
的矩阵 ,可按下式求解矩阵的乘法 - 从公式可以看出,按照
的顺序组织循环,能够得到最好的空间局部性 - 与
的调用顺序相比,其不能使用一个局部变量来储存 的值 - 因为内层循环多了对
的读写
- 因为内层循环多了对
- 但是由于良好的空间局部性以及硬件预取机制,采用此种排列的性能仍然有很大的提升
- 与
- 矩阵乘法内循环的分析
- 注意块大小为 32 个字节,数组类型为
double
,占据 8 个字节,所以一个块只能存放 4 个数组元素
- 注意块大小为 32 个字节,数组类型为
- 矩阵乘法性能
利用分块 (blocking) 来提升程序性能
- 核心思想是将一个程序中的数据结构组织成大的片 (chunk)
- 使得能够将一个片加载到 L1 高速缓存中,并在这个片中尽可能多的进行所需的读和写
- 然后丢掉这个片,加载下一个片,依此类推
- 使得能够将一个片加载到 L1 高速缓存中,并在这个片中尽可能多的进行所需的读和写
分块主要是可以提高内循环的时间局部性
- 但是分块使得代码更难阅读和理解
# 6.6.3 在程序中利用局部性
要点
- 将注意力集中在内循环上,因为大部分计算和内存访问都发生在这里
- 通过按照数据对象储存在内存中的顺序、以步长为 1 来读数据,可以使得程序中的空间局部性最大
- 一旦从储存器中读入了一个对象,就尽可能多的使用它,从而使得程序中的时间局部性最大