跳转至

Chapter 6 存储器的层次结构

1）引入

1. 存储器系统(memory system)：

  1. 存储器系统是一个具有不同容量/成本/访问时间的存储设备的层次结构
  2. CPU寄存器内保存着最常用的数据
  3. 靠近CPU的小的/快速的高速缓存存储器(cache memory) 是一个缓冲区，缓存的是存储在相对慢速的主存储器(main memory) 中数据和指令的一部分
  4. 主存缓存存储在容量较大、慢速磁盘上的数据，而这些磁盘常常有作为存储在通过网络连接的其他机器的磁盘或磁带上的数据的缓冲区域
  5. 该系统的整体效果：一个大型的存储器池

2. 程序的局部性(locality)：

  1. 局部性是计算机的基本属性
  2. 具有==良好局部性==的程序倾向于一次又一次地访问===相同==的数据项集合，或是访问==相邻==的数据项集合

  3. 具有良好局部性的程序更多地倾向于从存储器层次结构中的较高层次处访问数据项，因此会运行地更快

  4. 如果程序所需要的数据是存储在CPU寄存器中，那么在指令的执行期间，在0个周期内就可以访问到它们

  5. 如果存储在高速缓存中，需要4～75个周期
  6. 如果存储在主存中，需要上百个周期
  7. 如果存储在磁盘上，需要几千万个周期
  8. 我们编写应用程序的窍门就在于：使得数据项存储在层次结构较高的位置，在那里CPU可更快地访问到它们

2）存储技术

【1】随机访问存储器(RAM,Random-Access Memory)

RAM分为两类：静态RAM(SRAM) 与 动态RAM(DRAM) 1. SRAM用来作为高速缓存存储器，可以在CPU芯片中，也可以在片外 2. DRAM用来作为主存以及图形的帧缓冲区

计算机系统中，SRAM（Static Random Access Memory）和DRAM（Dynamic Random Access Memory）通常都存在于主存储器（主存）中，而不是直接集成到CPU中。主存是计算机系统中用于存储程序和数据的主要存储设备，它与CPU通过内存总线相连! SRAM和DRAM在主存中扮演不同的角色： [1] SRAM（静态RAM）： 它是一种静态存储器，保持数据的状态不变，只要电源保持稳定。SRAM通常用于构建高速缓存，这是位于CPU和主存之间的快速存储器层。高速缓存用于暂时存储CPU频繁访问的数据和指令，以提高访问速度。 [2] DRAM（动态RAM）： 它是一种动态存储器，需要定期刷新以保持存储的数据。DRAM用于构建主存，因为它相对较便宜且能够提供大容量的存储。主存中的数据可以被CPU直接读取或写入，但相对于高速缓存而言，DRAM的访问速度较慢。

静态RAM：
  • SRAM将每个位存储在一个双稳态(bistable)的存储器单元中
  • 它可以无限期保持在两个不同的电压配置或状态之一
  • 类比“倒置的钟摆”
  • 由于SRAM的双稳态特性，只要有电，就可以永远保持它的值。即使有干扰(eg电子噪音)，当干扰消除时，电路就会恢复到稳定值 ![[Pasted image 20231118183626.png]]
动态RAM：
  • DRAM将每个位存储为一个电容的充电，其存储器单元对干扰十分敏感，当电容的电压被扰乱后，它就永远不会恢复了
  • DRAM芯片封装在内存模块(memory module)中，它插到主板的 ![[Pasted image 20231118183646.png]]
非易失性存储器(nonvolatile memory)：
  • 显而易见，如果断电，则DRAM与SRAM就会丢失它们的信息，从这个意义上来说，它们是“易失”的
  • 非易失性存储器(nonvolatile memory)即使是在断电后，依然能保存它们的信息
  • 虽然 ROM(只读存储器) 中有的类型既可以读也可以写，但是我们依旧喊它 ROM(Read-Only Memory)
  • 闪存(flash memory)：是一类非易失性存储器，为大型电子设备提供快速而持久的非易失性存储 「后面会介绍一种基于闪存的磁盘驱动器，called：固态硬盘[SSD]」
  • PROM：可编程ROM，只能使用一次
  • EPROM：可擦写可编程ROM，可以使用近\(10^5\)次
访问主存：

[1] 数据流通过总线(bus)的共享电子电路在处理器和DRAM主存之间来回交互，这些步骤叫做：总线事务 [2] 读事务：从主存传送数据到CPU [3] 写事务：从CPU传送数据到主存

1. 主要部件：
  • CPU芯片
  • I/O桥：将系统主线的电子信号 转换为 内存总线的电子信号
  • 主存
  • 系统主线(system bus)：连接的是CPU 与 I/O桥接器
  • 内存总线(memory bus)：连接的是 I/O桥接器 与 主存 ![[Pasted image 20231118190305.png]]
2. 考虑两个小过程：

Text Only
1
movq A , %rax
coding含义：将地址A的内容加载到寄存器%rax中

CPU芯片上：总线接口(bus interface)的电路在总线上发起读事务 1. CPU将地址A放到系统总线上，I/O桥将信号传递到内存总线 2. 主存感知到内存总线上的地址信号，从内存主线读地址 3. 主存从DRAM中拉取对应的数据字，并将数据写到内存总线 4. I/O桥将内存主线的信号翻译成系统主线信号，然后沿着系统主线传递 5. CPU感知到系统主线上的数据，从主线读数据，并将数据复制到寄存器%rax中 ![[Pasted image 20231118190945.png]] ![[Pasted image 20231118191003.png]] ![[Pasted image 20231118191042.png]]

Text Only
1
movq %rax , A
coding含义：将寄存器%rax中的内容写到到地址A

CPU发起写事务 1. CPU将地址放到系统主线上 2. 内存从内存主线读出地址，并等待数据到达 3. CPU将%rax寄存器汇总的数据字复制到系统总线 4. 主存从内存总线读出数据字，并将这些位存储到DRAM中

【2】磁盘存储

（1）磁盘构造：

整个装置被称为磁盘驱动器(disk drive)，我们通常简称为磁盘(disk)

（2）磁盘容量：
  • 记录密度(recording density)：磁道一英寸段中可以放入的位数
  • 磁道密度(track density)：从盘片中心出发半径上一英寸的段内可以有的磁道数
  • 面密度(areal density)：记录密度 x 磁道密度

提升磁盘容量的方法： 1. 提高面密度（old） 2. 多区记录（now）

磁道容量的计算公式： \(磁盘容量 = 字节数/扇区 * 平均扇区数/磁道 * 磁道数/表面 * 表面数/盘片 * 盘片数/磁盘\)

（3）磁盘操作：
  • 寻道时间：移动机械臂将读写头 定位到目标扇区的磁道上，这一部分时间called寻道时间
  • 旋转时间：读写头到了期望的磁道后，驱动器等待目标扇区的第一个位 旋转到读写头 正下方，这一部分时间called旋转时间
  • 传送时间：当目标扇区的第一个位 旋转到读写头 正下方时，驱动器就可以开始读/写该扇区的内容，直至将内容全部处理完毕，这一部分时间called传送时间
（4）逻辑磁盘块：
（5）连接I/O设备：

例如：图形卡、监视器、鼠标、键盘等输入/输出设备(I/O devices)，都是通过I/O总线连接到CPU与主存的 系统主线与内存主线是与CPU相关的，与上述不同 这些I/O主线比系统主线和内存主线慢，但是它可以容纳更多种类的第三方I/O设备

有三种不同类型的设备连接到主线： 1. 通用串行主线(Universal Serial Bus , USB)：最通用！ 2. 图形卡(or适配器)：包含硬件与软件逻辑，它们负责代表CPU在显示器上画像素 3. 主机总线适配器：可以将一个/多个磁盘连接到I/O总线，使用的是一个特别的 主机总线接口 定义的通信协议 - 常见的主机总线适配器有两种： - SCSI控制器：可以支持多个磁盘驱动器 - SATA控制器：仅支持一个磁盘驱动器

其他的设备，比如网络适配器 ，可以通过将适配器插入到主板上空的扩展槽 中，从而连接到I/O总线，这些插槽提供了到总线的直接电路连接 ![[Pasted image 20231118200318.png]]

（6）访问磁盘：
  • 访问磁盘是什么意思：用户操作CPU对于disk内的文件等数据进行访问与读取
  • CPU使用一种称为内存映射I/O(memory-mapped I/O) 的方法，来向I/O设备发送命令
  • 在使用内存映射I/O的系统中，地址空间汇总有一块地址是为与I/O设备通信保留的，每一个这样的地址called：I/O端口
  • 当一个设备连接到总线时，它与一/多个端口相关联

举例分析： 假设一个磁盘控制器（外接的I/O设备）映射到端口0xa0 step1：CPU会通过执行三个对地址0xa0对存储指令，发起磁盘读

message1： 发出一个命令字，告诉磁盘发起一个读，同时还传送了其他参数(eg:读完成后，是否中断CPU...) message2：指明应该读取的逻辑块号(block num) message3：指明应该将数据存储在磁盘扇区内容的主存地址

step2(CPU)：当CPU发出命令请求后，磁盘开始执行读操作，此时CPU通常会做别的工作，把磁盘“晾在一边”

这么做的原因是：读磁盘的时间太长，如果这段时间CPU一直等着它，就会错失很多其他信息，性价比太低！

step2(disk)：磁盘控制收到来自CPU的读命令后： 1. 它把逻辑块号翻译成一个扇区地址，读取该扇区的内容 2. 然后将这些内容直接传送到主存，不需要CPU进行干涉！ 3. 在DMA传送完成后，磁盘扇区内容被安全地存储在主存中

step3：DMA传送完成后，磁盘扇区内容会被安全地存储在主存中 1. 磁盘控制器通过给CPU发送一个中断信号来通知CPU，“我的数据已经全部传到主存中了，你可以进行访问了！” 2. 此时：CPU收到这个中断信号，会暂停手边的工作，跳转到一个操作系统例程，它会记录下I/O已完成，然后将控制返回到刚刚CPU被中断的位置 ![[Pasted image 20231118202827.png]] ![[Pasted image 20231118202838.png]] ![[Pasted image 20231118202849.png]]

【3】固态硬盘（Solid State Disk，SSD）

  • SSD是一种基于闪存的存储技术
  • SSD封装插到I/O总线上标准硬盘插槽(通常是USB/SATA)，行为就像其他硬盘一样，处理来自CPU的读写逻辑磁盘块的请求

SSD的工作原理： ![[Pasted image 20231118203820.png]] 1. 一个闪存由B个块(block)的序列组成 2. 每个块(block)由P页(page)组成 3. 数据的写入是以“页”为单位的，只有在一页所属的块整个被擦除后，才能写这一页 4. 一旦一个块被擦除，块中每一页都可以不需要再进行擦除就写一次

事实上，读SSD比写要快得多 随机写很慢mainly because： 1. 擦除块需要相对较长的时间 2. 如果写操作试图修改一个已经包含数据的页p，那么这个block中所有的带有用数据的页都必须被复制到一个新(newly 擦除)的块，然后才能对页p进行写操作

3）局部性

  • 一个编写良好的程序常常具备很好的局部性(locality)
  • 意味着它们倾向于一次又一次地访问===相同==的数据项集合，或是访问==相邻==的数据项集合
  • 这种倾向性called“局部性原理“(principle of locality)

形式： 1. 时间局部性：被引用过一次的内存位置很可能在不远的将来再被多次引用 2. 空间局部性：如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用它附近的一个内存位置

计算机体系结构的很多地方都利用到了局部性原理： 1. 硬件层：引入“高速缓存存储器”来保存最近被引用的指令与数据项，从而提高对主存的访问速度 2. 操作系统级：系统使用主存作为虚拟地址空间最近被引用块的高速缓存

4）存储器层次结构

![[Pasted image 20231118205825.png]]

这里着重介绍：存储器结构中的缓存！
（1）基础知识：
  1. 存储器层次结构的中心思想：对于每个k，位于k层的更快更小的存储设备作为位于k+1层的更大更慢的存储设备的缓存。（换言之：层次结构的每一层都缓存来自较低一层的数据对象）
  2. 第k+1层的存储器被划分成连续的数据对象组块(chunk)，称为“块”(block)
  3. 每个block有唯一的地址/名字，使之区分于其他的块；块的大小可以是固定大小的，也可以是可变大小的
  4. 第k层的缓存包含第k+1层的一个子集的副本
  5. 数据总是以块大小为传输单元(transfer unit)在layer(k)与layer(k+1)之间来回复制的
  6. 一般而言：层次结构中离CPU较远的设备访问时间较长 ![[Pasted image 20231118211553.png]]
（2）缓存映射关系：
当程序需要layer(k+1)中的某个数据对象d时，它首先在当前存储在layer(k)的一个块中查找d，

  1. 缓存命中：

    如果d刚好缓存在layer(k)中，那么程序直接从layer(k)中读取d，显然这种情况要比“从layer(k+1)读取d”快！这就叫“缓存命中”

  2. 缓存不命中：

    [1] 如果d并没有缓存在layer(k)中，那么程序需要从layer(k+1)缓存中取出包含d的那个block；如果第k层缓存已经满了，可能就会覆盖现存的一个块 [2] 覆盖现存的一个块called“替换(replacing)”或“驱逐(evicting)”这个块，被驱逐的那个block叫做“牺牲块(victim block)” [3] 决定who is ‘victim block’ 的策略called：缓存的替换策略，通常采用的是LRU策略('最近最少被使用strategy') [4] 在layer(k)缓存从layer(k+1)取出那个块后，程序就可以像前面那样从layer(k)读取d了【将东西覆盖进上级缓存即可，它会一直呆在那里，等待稍后的访问】

（3）缓存不明中的分类：
  1. 强制性不命中/冷不命中：第k层的缓存是空的

    这种情况通常都是初期的短暂性事件，不会在程序warmed up后的稳定状态中发生

  2. 冲突不命中：对象始终映射到同一个缓存块，会导致缓存一直未命中

    上述“放置策略”实质上是限制性策略，虽然缓存足够大，能保存被引用的数据对象；但是因为这些对象始终映射到同一个缓存块，会导致缓存一直未命中（比如策略是layer(k+1)->layer(k): i mod4）

  3. 容量不命中：工作集的大小超过缓存的大小时，缓存装不下

5）高速缓存存储器

（1）引入：
  • 随着CPU与主存逐渐增大的差距，系统设计者被迫在CPU寄存器文件与主存之间插入一个小的SRAM高速缓存存储器 称为 L1高速缓存（一级缓存），L1高速缓存的访问速度几乎和寄存器一样快
  • 由于设计需要，设计者又在L1与主存之间插入了一个更大的高速缓存，称作：L2高速缓存
  • 部分现在系统中，L2与主存之间插入了一个更大的高速缓存，称作：L3高速缓存
  • 后续的介绍中，我们假设CPU与主存之间只有L1高速缓存

（2）通用高速缓存存储器组织结构：

![[Pasted image 20231119100525.png]] - 每个存储器地址有m位，形成M = \(2^m\) 个不同的地址 - 这个机器的高速缓存被组织成S = \(2^s\) 个高速缓存组(cache set)的数组 - 每个组包含E个高速缓存行(cache line) - 每个行是由一个B = \(2^b\) 字节的数据块(block)组成的 - 一个有效位(valid bit)：指明这个行是否包含有意义的信息 - t = m - (b+s) 个标记位(它是当前block的内存地址的位的一个子集)，它们唯一地标识存储在这个高速缓存行中的块

  1. 一般而言：高速缓存的结构可以用元组(S,E,B,m)表示
  2. 高速缓存的大小(or 容量)：所有块的大小之和(不包含标记位与有效位)，C = S x E x B
  3. 操作步骤：

    当一条加载指令指示CPU从主存地址A中读取一个字时，它把地址A发送给高速缓存，如果高速缓存正保存着地址A处那个字的副本，它就立马将那个字发回CPU

高速缓存如何知道它是否包含addr.A包含的那个字的副本？——使用简单的哈希表 1）A中s个组索引位(set index)是一个到S个组的数组的索引，它告诉我们这个字必须被存储在哪个组中 2）当我们知道这个字必须放在哪个组中，A中的t个标记位就告诉我们这个组的哪一行包含这个字(如有的话) ，iff：设置了有效位 & 该行的标记位与addr.A中的标记位相匹配 3）当我们知道这个字所处的行后，由于b个偏移位给出了在B个字节的数据块中的字偏移，我们就可以轻松定位到“目标地点”了

（3）直接映射高速缓存

[1] 引入：
  1. 根据每个组的高速缓存行数E，高速缓存被分为不同的类。E=1的高速缓存被称为直接映射高速缓存(direct-mapped cache)
  2. 过程：当CPU执行一条读内存字w的指令，它向L1请求这个字；L1如有此副本，就是缓存命中，高速缓存回很快抽取出w，并将它返回给CPU；否则就是缓存不命中，此时L1向主存请求包含w的块的一个副本，CPUwaiting。当被请求的块最终从内存到达时，L1将这个块存放在它的一个高速缓存行中，从被存储的块中抽取出字w，然后将它返回给CPU
[2] 具体过程：

![[Pasted image 20231119105532.png]]

1. 直接映射高速缓存中的组选择
  • 高速缓存从w的地址中间取出s个组索引位
  • 组索引位转换成的十进制数字就是对应数组下标的索引

    例如: 上述 addr.13，对应的s=2(它对应的十进制数字范围0～3）,这里它的index bit = (10)\(_2\)，，还原成十进制数是2，即：对应组2 即：被解释为选择组2的整数索引

2. 直接映射高速缓存中的行匹配
  • 在上一步中我们已经选择完毕“该去哪个组”，接下来的一步就是确定是否有字w的一个副本存储在组i的一个高速缓存行内了
  • 这对于“直接映射高速缓存”是个good news，因为它每组只有一行
  • 这个行的有效位设置了，则说明此行的标记和块中的位是有意义的
  • 此行的标记位和地址中的标记位相匹配，则说明我们要的w的副本确实在这一行中 ![[Pasted image 20231119110532.png]]
3. 直接映射高速缓存中的字选择
  • 现在我们已经知道w在这个块的具体位置了，现在需要确定字w在块中是从哪里开始的
  • 块偏移位提供了所需要的字的第一个字节的偏移

    例如上图中的Block offset是\((100)_2\) 它表明w的副本是从块中的字节4开始的

4. 直接映射高速缓存中不命中时的行替换
  • 如果cache不命中，那么需要从存储器层次结构的下一层中取出被请求的块，然后将新的块存储在组索引位指示的组中的一个高速缓存行中
  • 对于直接映射高速缓存来说，每个组只包含有一行，那么“替换策略”很简单：用新取出的行代替当前行
5. 具体示例：

![[Pasted image 20231119105532.png]] - 标记位和索引位连起来唯一地标识了内存中的每个块

块0是由地址0和1组成的；块2是由地址4和5组成的 - 映射到同一个高速缓存组的块由标记位唯一地标识 块0和块4都是0mod4，回溯射到的是同一个表示块，但是块0的标记位是0，块4的标记位是1，形成区分！ - 存在“冲突不命中”的问题

【1】初始时，高速缓存是empty的，每个有效位都是0 ![[Pasted image 20231119112401.png]] 【2】读取addr.0的字： 1. 查表addr=0：对应的index=\((00)_2\)，得到十进制数0，说明它映射到“小数组”下标index=0 2. “小数组”组0的有效位现在是0，很显然：本次缓存不命中 3. 查表addr=0:对应的==block_num = 0==，故：高速缓存从内存(or lower1 layer)中取出==块0==，并将这个块存储在组0中 4. 随后，高速缓存返回新取出的高速缓存行的块[0]的m[0]（内存位置0的内容），并将有效位改为1！ ![[Pasted image 20231119113856.png]] 【3】读取addr.1的字： 1. 查表addr=1：对应的index=\((00)_2\)，得到十进制数0，说明它映射到“小数组”下标index=0 2. 此时组0的有效位已经是1；现考察Tag是否匹配 3. 因为addr.1的Tag=0；而此时组0的Tag=0，匹配！本次高速缓存命中！ 4. 查表addr=1：对应的==block_num = 0==，故高速缓存立刻从高速缓存行的块1中返回m[1] 5. 高速缓存的状态没有发生变化 【4】读取addr.13的字： 1. 查表addr=13：对应的index=\((10)_2\)，得到十进制数2，说明它映射到“小数组”下标index=2 2. “小数组”组2的有效位现在是0，很显然：本次缓存不命中 3. 查表addr=13：对应的==block_num = 6==，故高速缓存从内存(or lower1 layer)中取出==块6==，并将这个块存储在组2中 4. 随后，高速缓存返回新取出的高速缓存行的块[1]的m[13]（内存位置13的内容），并将有效位改为1！ ![[Pasted image 20231119113920.png]] 【5】读取addr.8的字： 1. 查表addr=8：对应的index=\((00)_2\)，得到十进制数0，说明它映射到“小数组”下标index=0 2. 虽然看似命中，但是实际上并没有！ 3. 因为addr.8的Tag=1；而此时组0的Tag=0，并不匹配！ 4. 查表addr=8：对应的==block_num = 4==，故高速缓存从内存(or lower1 layer)中取出==块4==，并将这个块存储在组0中 5. 然后从新的高速缓存行的块[0]中返回m[8] ![[Pasted image 20231119114525.png]] - 考察步骤： 1. 查表：得到元素对应的组index 2. 如果valid bit 是0 ，直接未命中，高速缓存从内存中取出... 3. 如果valid bit 是1，现在考察Tag是否匹配： 4. 如果Tag匹配，说明本次高速缓存命中！立刻从高速缓存行的块1中直接返回... 5. 如果Tag不匹配，说明本次高速缓存未命中！高速缓存从内存中取出...

（4）组相联高速缓存

  • 很显然上述直接映射高速缓存冲突不命中的原因是：每个组只有一行(E=1)
  • 组相联高速缓存(set associative cache)放松了此限制
  • 一个1<E<(C/B)的高速缓存常称为：E路相联高速缓存
1. 组相联高速缓存：

它的组选择跟“直接”的一样，用组索引位标识组

2. 组相联高速缓存中的行匹配与字选择：

（1）它必须检查一个组内的多个行的标记位与有效位； （2）相联存储器是一个(key , value)键值对数组，输入key，就会返回value （3）可以把组相联高速缓存中的每个组都视作一个小的相联存储器，key是标记和有效位，value就是块的内容

![[Pasted image 20231119123915.png]] - key：组中的任何一行都可以包含任何映射到这个组的内存块，所以高速缓存必须仔细搜查组中的每一行 - 寻找一个有效的行，其标记与地址中的标记相匹配！ - 如果找到，那么就called命中，随后块偏移从这个块中选择一个字，跟之前一样 ![[Pasted image 20231119124232.png]] ##### 3. 组相联高速缓存中不命中时的行替换： - 当CPU请求的字不在组的任何一行中，那么就是缓存不命中，高速缓存必须从内存中取出包含这个字的块 - 一旦取出，就要考虑该替换哪个行！ 1. 如果有一个空行，那它就是best choice 2. 如果没有，那么我们必须从中选择一个非空行，希望CPU不会很快引用这个被替换的行(victim rank) 3. 上述的选择策略：

[1] LFU: 最不常使用，Least-Frequently-Used （过去某个时间窗口内引用次数最少的那一行） [2] LRU: 最近最少使用, Least-Recently-Used（最后一次访问时间最久远的那一行）

（5）全相联高速缓存

E=C/B：即在全相联高速缓存中，一个组包含所有的行

（6）有关写的问题

太难，此处跳过

（7）小结：区分块/高速缓存行/组

  • 块：是一个固定大小的信息包，在高速缓存和主存(or layer_next)之间来回传送
  • 行：是高速缓存中的一个容器。存储块和其他信息(eg: 有效位/标记位)
  • 组：是一个or多个行的集合，很显然“直接映射高速缓存”的组跟行等价，其他的高速缓存是：一“组”包含很多“行”