存储器层次结构

物理介质

存储技术

随机访问存储器

基本存储体系

1)输入设备将程序与数据写入主存; 2) CPU取指令; 3) CPU执行指令期间读数据; 4) CPU写回运算结果; 5) 输出设备输出结果;

主存速度慢的原因

主存容量不足的原因

存储体系的层次结构

2021927173034

存储器硬件介质单位成本(美元/MB)随机访问延时说明
L1 CacheSRAM71ns
L2 CacheSRAM74ns访问延时15x L1 Cache
MemoryDRAM0.015100ns访问延时15X SRAM,价格1/40 SRAM
DiskSSD(NAND)0.0004150μs访问延时1500X DRAM,价格1/40 DRAM
DiskHDD0.0000410ms访问延时70X SSD,价格1/10 SSD

局部性

时间局部性

空间局部性

主存中的数据组织

ISA设计时要考虑的两个问题

数据存储与边界

按边界对齐的数据存储:浪费一些空间

批注 2020-01-30 161009

未按边界对齐存放:虽节省了空间,但增加了访存次数

批注 2020-01-30 161136

需要在性能与容量间权衡

大端与小端存储

无论是大端还是小端,每个系统内部是一致的,但在系统间通信时可能会发生问题!因为顺序不同,需要进行顺序转换

存储技术

随机访问存储器

静态RAM(SRAM)

批注 2020-01-30 162459

工作原理

结构

批注 2020-01-15 092634

静态存储器的不足

动态RAM(DRAM)

202274213610

批注 2020-01-30 164801

DRAM与SRAM不同的是,需要靠不断地“刷新”,才能保持数据被存储起来

刷新

集中刷新

分散刷新

异步刷新

其它结构的DRAM存储单元

批注 2020-01-30 190355

传统DRAM

存储扩展

用16K X 8 的存储芯片构建16K X 32的存储器

用16K X 8 的存储芯片构建128k X 8的存储器

用16K X 8 的存储芯片构建128K X 32的存储器

批注 2020-01-30 190639

无论哪种类型的存储扩展都要完成CPU与主存间地址线、数据线、控制线的连接

磁盘存储

磁盘构造

构造

性能度量

访问优化

物理结构决定了磁盘更擅长顺序访问,为了优化随机读写的低效率,有一些手段:

磁盘容量度量

连接到磁盘

访问磁盘

内存映射:将磁盘文件映射到进程的虚拟地址空间中的技术,这样就可以像访问内存一样访问磁盘文件,从而方便了文件的读写操作

固态硬盘

raid

raid的数据拆分有两种:

比特级的粒度较细,所以读写效率相对较低能

批注 2020-02-08 204640

RAID级别说明可靠性读性能写性能最少硬盘数量硬盘利用率
RAID01100%
RAID121/N
RAID5较高3(N-1)/N
RAID6较高3(N-2)/N
RAID1E3M/N
RAID104M/N
RAID50较高6(N-M)/N
RAID60较高6(N - M * 2)/N

N为RAID组成员盘的个数,M为RAID组的子组数。

RAID0

批注 2020-02-08 204953

RAID1

批注 2020-02-08 205138

RAID2

在数据盘的基础上,增加了一个磁盘来存放ECC

RAID 3/4

批注 2020-02-08 205227

RAID5

批注 2020-02-08 205428

RAID6

为每4 位数据存储2 位的冗余信息,这样系统可容忍两张磁盘 发生故障

RAID10

批注 2020-02-08 205601

RAID01

批注 2020-02-08 205654

只能容忍一个磁盘故障,如0号盘损坏,左边RAID0失效,只能使用右边的RAID0,不能再有盘损坏,故冗余度为1

实现方式

在空闲时期,控制器会对每张磁盘的每一个厨区进行读取,如果发现某个扇区无法读取,会从其余磁盘中进行恢复

一些硬件RAID实现允许热交换:在不切断电濒的情况下梅出错磁盘用新的磁盘替换

比较

批注 2020-02-08 205826

选择考量

存储技术的趋势

对程序数据引用的局部性

取指令的局部性

多体交叉存储器

其基本思想是在不提高存储器速率、不扩展数据通路位数的前提下,通过存储芯片的交叉组织,提高CPU单位时间内访问的数据量,从而缓解快速的CPU与慢速的主存之间的速度差异。

高位多体交叉存储器

批注 2020-01-16 113946

低位多体交叉存储器

批注 2020-01-16 113919

批注 2020-02-08 161132

高速缓存存储器

现代的多核处理器大都采用混合式的方式将缓存集成到芯片上,一般情况下,L3 是所有处理器核共享的,L1 和 L2 是每个处理器核特有的

内存中的指令、数据,会被加载到 L1-L3 Cache 中,而不是直接由 CPU 访问内存去拿

CPU 从内存中读取数据到 CPU Cache 的过程中,是一小块 Cache Line 来读取数据的,而不是按照单个数组元素来读取数据的,大部分 Cache Line的大小通常是64个字节,Disruptor 利用了这点

cache的工作过程

sequenceDiagram  alt 命中    CPU ->> Cache: 读取数据    Cache ->> CPU: 返回数据  end  alt 缺失    CPU ->> Cache: 读取数据    Cache ->> 内存: 读取数据    内存 ->> Cache: 返回数据    Cache ->> CPU: 返回数据  end

缓存写策略

修改什么时候传播到主存:

当某个 CPU 的缓存发生变化,其他 CPU 缓存所保有该数据副本的更新策略:

当前要写入的数据不在缓存中时,根据是否要先将数据加载到缓存:

cache地址映射机制

对于一个地址,可以通过地址得到其应该在哪个组,确定在哪个组后,再将内存地址与组中的每一路缓存块 tag 进行匹配,如果相等,就说明该内存块已经载入到缓存中;如果没有匹配的 tag,就说明缓存缺失,需要将内存块放到该组的一个空闲缓存块上;如果所有路的缓存块都正在被使用,那么需要选择一个缓存块,将其移出缓存,把新的内存块载入

批注 2020-02-08 162555

内存地址到 Cache Line

cache的结构

缓存块的组织形式

批注 2020-02-08 162726

有效位V脏位M是否有tag匹配缓存操作说明状态转换
0读/写缓存缺失,将内存数据载入缓存tag设置成地址高21位,有效位V置1
10缓存命中状态不变
1读/写同组缓存块已满,选择一个缓存块替换被替换的缓存块有效位置位V置0,回到第一行状态
10缓存命中脏位M置1
11缓存命中,但缓存和内存数据不一致缓存状态保持不变
11缓存命中,继续写缓存状态保持不变

相联存储器

缓存缺失

Cache地址映射与变换方法

全相联映射

缓存只有一个组,所有的内存块都放在这一个组的不同路上

批注 2020-02-08 164919

特点

所以应用在小容量cache

直接映射

缓存只有一个路,一个内存块只能放置在特定的组上

批注 2020-02-08 165705

特点

应用在大容量cache

组相联映射

缓存同时有多个组和多个路

批注 2020-02-08 185829

淘汰策略

程序运行一段时间后,Cache存储空间被占满,当再有新数据要调入时,就需要通过某种机制决定替换的数据

先进先出法FIFO

批注 2020-02-08 191721

最不经常使用法LFU

批注 2020-02-08 191910

近期最少使用法LRU

批注 2020-02-08 192722

替换算法的抖动

伪共享false sharing

当两个线程同时各自修改两个相邻的变量,由于缓存是按缓存块来组织的,当一个线程对一个缓存块执行写操作时,必须使其他线程含有对应数据的缓存块无效。这样两个线程都会同时使对方的缓存块无效,导致性能下降

经常会看到为了解决伪共享而进行的数据填充

VI协议

当前 CPU 发起的操作:

stateDiagram-v2  V --> V: PrRd/PrWr/BusWr  I --> I: PrWr/BusWr  I --> V: PrRd/BusRd

总线发起的请求:

stateDiagram-v2  V --> V: 除BusRd  I --> I: 除BusRd与BusWr  V --> I: 除BusWr

MESI

是一种写失效协议:只有一个 CPU 核心负责写入数据,在这个 CPU 核心写入 Cache 之后,它会去广播一个“失效”请求告诉所有其他的 CPU 核心。其他的 CPU 核心,只是去判断自己是否也有一个“失效”版本的 Cache Block,然后把这个也标记成失效

相对应的就是写广播协议:一个写入请求广播到所有的 CPU 核心,同时更新各个核心里的 Cache,写广播还需要把对应的数据传输给其他 CPU 核心

stateDiagram-v2  M --> M: 本地读/写  M --> S: 总线读/发出写回信号  M --> I: 总线写/发出写回信号  E --> M: 本地写  E --> E: 本地读  E --> S: 总线读  E --> I: 总线写/发出写回信号  S --> S: 本地写/发出总线写信号  S --> S: 本地读  S --> I: 总线写/发出写回信号  I --> S: 本地读/发出总线读信号  I --> E: 本地读/发出总线读信号  I --> M: 本地写/发出总线写信号

内存屏障

严格遵守 MESI 协议会导致某个核对缓存的占用比较长,从而影响性能。为此通过放宽 MESI 限制,引入 store buffer、invalid queue 的方式,提升了写缓存核间同步的速度

store buffer 是硬件实现的缓冲区,它的读写速度比缓存的速度更快,所有面向缓存的写操作都会先经过 store buffer,即先收集一些写操作,再批量写到缓存中,但它并不能保证变量写入缓存和主存的顺序

当一个 CPU 向同伴发出 Invalid 消息的时候,它的同伴要先把自己的缓存置为 Invalid,然后再发出 acknowledgement。这个过程是比较慢的,所以引入了 invalid queue ,收到 Invalid 消息的 CPU,立刻回传确认消息,再把这个失效的消息放到一个队列中,等到空闲的时候再去处理失效消息,将缓存设置为 invalid

这两个优化都可能导致变量没有写到缓存前,被其他核给读到过期值

所以引入了内存屏障,屏障的作用是前边的读写操作未完成的情况下,后面的读写操作不能发生

// CPU0void foo() {    a = 1;    smp_wmb(); // 写屏障    b = 1;}// CPU1void bar() {    while (b == 0) continue;    smp_rmb(); // 读屏障    assert(a == 1);}

除了使用读写对内存屏障进行分类外(alpha 结构),另外一种叫做单向屏障的不是以读写来区分的,而是像单行道一样,只允许单向通行:

单向内存屏障有两个重要的语义:

TSO 模型

处理器对于 store 操作(写操作)的行为有如下规定:

  1. Store Buffering(写缓冲):每个处理器都拥有自己的写缓冲区,store 操作首先被存放在这个缓冲区中,而不是立即写入主存。
  2. Write Combining(写合并):在写缓冲中,如果发现多个 store 操作针对同一个内存地址,那么这些操作可能会被合并成一个较大的写操作。
  3. Store Atomicity(写原子性):store 操作对于其它处理器来说是原子的,即要么全部执行,要么全部不执行。但是,不同的 store 操作之间的顺序可能会被打乱。
  4. Store Ordering(写顺序):每个处理器的 store 操作按照程序中的顺序执行,并且对于其它处理器来说,每个处理器所执行的 store 操作都是有序的

写原子性跟写顺序性就解决了上述内存模型中的一致性问题

NUMA

内存在物理上被分为了多个节点 node,CPU 可以访问所有节点,但是为了提升访问效率,CPU 可以有选择地优先访问离自己近的内存节点

stateDiagram-v2  state node1 {    cpu1 --> 内存1  }  cpu1 --> cpu2: cpu通信  cpu2 --> cpu1: cpu通信  cpu1 --> 内存2: 远程访问  cpu2 --> 内存1: 远程访问  state node2 {    cpu2 --> 内存2  }
内存策略描述
MPOL_BIND只在特定节点分配,如果空间不足则进行swap
MPOL_INTERLEAVE本地和远程节点均可分配
MPOL_PREFERRED指定节点分配,当内存不足时,优先选择离指定节点近的节点分配
MPOL_LOCAL优先在本地节点分配,当内存不足时,在其他节点分配

虚拟存储器

概述

必须解决的问题

批注 2020-02-08 200857

地址划分

虚拟地址 = 虚页号+页偏移量

逻辑地址与物理地址的转换

TLB (Translation Lookaside Buffer)

虚实地址转换过程中存在的问题

批注 2020-02-08 202837

工作原理

TLB类似页表,也是PTE的集合。为实现对TLB的快速访问,类似于Cache中的映射方法,对来自于CPU的虚页号进行逻辑划分,得到相应的标记和索引字段

批注 2020-02-08 204051

缓存写

高速缓存参数的性能影响

存储器层次结构中的缓存

缓解快速CPU与慢速的主存之间的速度差异

工作工程

编写高速缓存友好的代码

高速缓存对程序性能的影响