做淘客网站需要多大空间,app制作免费平台,深圳微信网站建设报价,初中网站建设存储体系结构
速度快的存储硬件成本高、容量小#xff0c;速度慢的成本低、容量大。为了权衡成本和速度#xff0c;计算机存储分了很多层次#xff0c;有寄存器、L1 cache、L2 cache、L3 cache、主存#xff08;内存#xff09;和硬盘等。
根据程序的空间局部性和时间局…存储体系结构
速度快的存储硬件成本高、容量小速度慢的成本低、容量大。为了权衡成本和速度计算机存储分了很多层次有寄存器、L1 cache、L2 cache、L3 cache、主存内存和硬盘等。
根据程序的空间局部性和时间局部性原理缓存命中率可以达到 7090% 。因此增加缓存可以让整个存储系统的性能接近寄存器并且每字节的成本都接近内存所以缓存是存储体系结构的灵魂。
缓存原理
缓存的工作原理
cache line缓存行是缓存进行管理的最小存储单元也叫缓存块每个 cache line 包含 Flag、Tag 和 Data 通常 Data 大小是 64 字节但不同型号 CPU 的 Flag 和 Tag 可能不相同。从内存向缓存加载数据是按整个缓存行加载的一个缓存行和一个相同大小的内存块对应。 缓存是按照矩阵方式排列(M × N)横向是组(Set)纵向是路(Way)。每一个元素是缓存行(cache line)。
那么给定一个虚拟地址 addr 如何在缓存中定位它呢首先把它所在的组号找到即
//右移6位是因为 Block Offset 占 addr 的低 6 位Data 为 64 字节
Set Index (addr 6) % M;然后遍历该组所有的路找到 cache line 中的 Tag 与 addr 中 Tag 相等为止所有路都没有匹配成功那么缓存未命中。整个缓存容量 组数 × 路数 × 缓存行大小。
缓存行替换策略
目前最常用的缓存替换策略是最近最少使用算法Least Recently Used LRU或者是类似 LRU 的算法。
LRU 算法比较简单如图3缓存有 4 路并且访问的地址都哈希到了同一组访问顺序是 D1、D2、D3、D4 和 D5那么 D1 会被 D5 替换掉。算法的实现方式有很多种最简单的实现方式是位矩阵。
首先定义一个行、列都与缓存路数相同的矩阵。当访问某个路对应的缓存行时先将该路对应的所有行置为 1然后再将该路对应的所有列置为 0。
最近最少使用的缓存行所对应的矩阵行中 1 的个数最少最先被替换出去。 缓存缺失
缓存缺失就是缓存未命中需要把内存中数据加载到缓存所以运行速度会变慢。
拿电脑来测试L1d 的缓存大小是 32KB32768B8路缓存行大小 64B缓存组数 32 × 1024 ÷ 8 ÷ 64 64
运行下面代码
char *a new char(64 * 64 * 8); //32768B 对应64行 一行64组
for(int i 0; i 20000000; i) for(int j 0; j 32768; j 4096) a[j];循环 160000000 次耗时 301 ms。除了第一次未命中缓存后面每次读写数据都能命中缓存。调整上面的代码并运行
char *a new char(64 * 64 * 8 * 2); //65536B
for(int i 0; i 10000000; i)for(int j 0; j 65536; j 4096)a[j];本次耗时 959 ms。每一次读写数据都没有命中缓存所以耗时增加了 2 倍。
程序局部性
程序局部性就是读写内存数据时读写连续的内存空间目的是让缓存可以命中减少缓存缺失导致替换的开销。
int M 10000, N 10000;
char (*a)[N] (char(*)[N])calloc(M * N, sizeof(char));
for(int i 0; i M; i)for(int j 0; j N; j)a[i][j];耗时 314 ms。利用了程序局部性原理缓存命中率高。以下代码耗时 1187 ms。没有利用程序局部性原理缓存命中率低所以耗时增加了 2 倍。
int M 10000, N 10000;
char (*a)[N] (char(*)[N])calloc(M * N, sizeof(char));
for(int j 0; j N; j)for(int i 0; i M; i)a[i][j];伪共享
当两个线程同时各自修改两个相邻的变量由于缓存是按缓存行来整体组织的当一个线程对缓存行中数据执行写操作时必须通知其他线程该缓存行失效导致另一个线程从缓存中读取其想修改的数据失败必须从内存重新加载导致性能下降。
struct S {long long a;long long b;
} s;
std::thread t1([]() {for(int i 0; i 100000000; i)s.a;
});
std::thread t2([]() {for(int i 0; i 100000000; i)s.b;
});耗时 512 ms是两个线程互相影响使对方的缓存行失效导致直接从内存读取数据。解决办法是对上面代码做修改通过 long long noop[8] 把两个数据a 和 b划分到两个不同的缓存行中不再互相使对方的缓存失效所以速度变快了。修改后耗时181ms。
struct S {long long a;long long noop[8];long long b;
} s;缓存一致性协议
缓存写策略
从缓存和内存的更新关系来看分为
写回write-back 对缓存的修改不会立刻传播到内存只有当缓存行被替换时这些被修改的缓存行才会写回并覆盖内存中过时的数据。
写直达write through 缓存中任何一个字节的修改都会立刻穿透缓存直接传播到内存这种比较耗时。
从写缓存时 CPU 之间的更新策略来看分为
写更新Write Update 每次缓存写入新的值该核心必须发起一次总线请求通知其他核心更新他们缓存中对应的值。 坏处写更新会占用很多总线带宽 好处其他核心能立刻获得最新的值。
写无效Write Invalidate 每次缓存写入新的值都将其他核心缓存中对应的缓存行置为无效。 坏处当其他核心再次访问该缓存时发现缓存行已经失效必须从内存中重新载入最新的数据 好处多次写操作只需发一次总线事件第一次写已经将其他核心缓存行置为无效之后的写不必再更新状态这样可以有效地节省核心间总线带宽。
从写缓存时数据是否被加载来看分为
写分配Write Allocate 在写入数据前将数据读入缓存。当缓存块中的数据在未来读写概率较高也就是程序空间局部性较好时写分配的效率较好。 写不分配Not Write Allocate 在写入数据时直接将数据写入内存并不先将数据块读入缓存。当数据块中的数据在未来使用的概率较低时写不分配性能较好。
MESI 协议
MESI协议是基于失效的缓存一致性协议是支持写回缓存的最常用协议。为了解决多个核心之间的数据传播问题提出了总线嗅探Bus Snooping策略。本质上就是把所有的读写请求都通过总线Bus广播给所有的核心然后让各个核心去嗅探这些请求再根据本地的状态进行响应。
它的名字来自四种状态修改Modified专有Exclusive共享Shared和无效Invalid。
修改Modified缓存行被某个处理器独占修改过并且与主存中的数据不同步。只有该处理器可以访问这个缓存行其他处理器都不能访问。
专有Exclusive缓存行被某个处理器独占但没有被修改过与主存中的数据是一致的。只有该处理器可以访问这个缓存行但如果其他处理器想要访问可以直接读取主存中的数据。
共享Shared缓存行可以被多个处理器同时读取但没有被修改过与主存中的数据是一致的。多个处理器都可以同时访问这个缓存行。
无效Invalid缓存行的数据是无效的不能被使用。如果某个处理器需要使用这个数据它必须从主存中重新读取。
当一个处理器要读取或写入一个数据时MESI 协议会检查这个数据在缓存中的状态并根据情况进行以下操作
读取操作
如果数据在缓存中是无效的处理器会从主存中读取数据并将状态设置为共享或专有。如果数据在缓存中是共享或专有的处理器可以直接读取缓存中的数据。
写入操作
如果数据在缓存中是无效或共享的处理器会将数据从主存中读取并进行修改将状态设置为修改。如果数据在缓存中是专有的处理器可以直接修改缓存中的数据并将状态改为修改。
内存屏障
基本概念
编译器和处理器都必须遵守重排序规则。在单处理器的情况下不需要任何额外的操作便能保持正确的顺序。但是对于多处理器来说保证一致性通常需要增加内存屏障指令。即使编译器可以优化掉字段的访问例如因为未使用加载到的值编译器仍然需要生成内存屏障就好像字段访问仍然存在一样可以单独将内存屏障优化掉。
内存屏障只与内存模型中的高级概念例如 acquire 和 release间接相关。内存屏障指令只直接控制 CPU 与其缓存的交互以及它的写缓冲区持有等待刷新到内存的数据的存储和它的用于等待加载或推测执行指令的缓冲。这些影响可能导致缓存、主内存和其他处理器之间的进一步交互。
几乎所有的处理器都至少支持一个粗粒度的屏障指令通常称为 Fence也叫全屏障它保证了严格的有序性在 Fence 之前的所有读操作load和写操作store先于在 Fence 之后的所有读操作load和写操作store执行完。对于任何的处理器来说这通常都是最耗时的指令之一它的开销通常接近甚至超过原子操作指令。大多数处理器还支持更细粒度的屏障指令。
写缓冲与写屏障
严格按照MESI协议核心0 在修改本地缓存之前需要向其他核心发送 Invalid 消息其他核心收到消息后使他们本地对应的缓存行失效并返回 Invalid acknowledgement 消息核心0 收到后修改缓存行。这里核心0 等待其他核心返回确认消息的时间对核心来说是漫长的。 为了解决这个问题引入了 Store Buffer 当核心想修改缓存时直接写入 Store Buffer 无需等待继续处理其他事情由 Store Buffer 完成后续工作。 这样一来写的速度加快了但是引来了新问题下面代码的 bar 函数中的断言可能会失败。
int a 0, b 0;
// CPU0
void foo() {a 1;b 1;
}
// CPU1
void bar() {while (b 0) continue;assert(a 1);
}第一种情况CPU 为了提升运行效率和提高缓存命中率采用了乱序执行
第二种情况Store Buffer 在写入时b 所对应的缓存行是 专有Exclusive状态a 所对应的缓存行是 共享Shared 状态因为对 b 的修改不需要核心间同步但是修改 a 则需要也就是 b 会先写入缓存。与之对应 CPU1 中 a 是 共享Shared 状态b 是 无效Invalid状态由于 b 所对应的缓存区域是无效Invalid状态它就会向总线发出 BusRd 请求那么 CPU1 就会先把 b 的最新值读到本地完成变量 b 值的更新但是从缓存直接读取 a 值是 0 。
举一个更极端的例子
// CPU0
void foo() {a 1;b a;
}第一种情况不会发生了原因是代码有依赖不会乱序执行。但由于 Store Buffer 的存在第二种情况仍然可能发生原因同上。
为了解决上面问题引入了内存屏障屏障的作用是前边的读写操作未完成的情况下后面的读写操作不能发生。这就是 Arm 上 dmb 指令的由来它是数据内存屏障Data Memory Barrier的缩写。
int a 0, b 0;
// CPU0
void foo() {a 1;smp_mb(); //内存屏障各CPU平台实现不一样b 1;
}
// CPU1
void bar() {while (b 0) continue;assert(a 1);
}加上内存屏障后保证了 a 和 b 的写入缓存顺序。
总的来说Store Buffer 提升了写性能但放弃了缓存的顺序一致性这种现象称为弱缓存一致性。通常情况下多个 CPU 一起操作同一个变量的情况是比较少的所以 Store Buffer 可以大幅提升程序的性能。但在需要核间同步的情况下还是需要通过手动添加内存屏障来保证缓存一致性。
上面解决了核间同步的写问题但是核间同步还有一个瓶颈那就是读。
失效队列与读屏障
前面引入 Store Buffer 提升了写入速度那么 invalid 消息确认速度相比起来就慢了带来了速度不匹配很容易导致 Store Buffer 的内容还没及时写到缓存里自己就满了从而失去了加速的作用。
为了解决这个问题又引入了 Invalid Queue。收到 Invalid 消息的核心立刻返回 Invalid acknowledgement 消息然后把 Invalid 消息加入 Invalid Queue 等到空闲的时候再去处理 Invalid 消息。 运行上面增加内存屏障的代码断言可能还是失败。
核心0 中 a 所对应的缓存行是 S 状态b 所对应的缓存行是 E 状态核心1中 a 所对应的缓存行是 S 状态b 所对应的缓存行是 I 状态
因为有内存屏障在a 和 b的写入缓存的顺序不会乱。a 先向其他核心发送 Invalid 消息并且等待 Invalid 确认消息Invalid 消息先入 核心1 对应的 Invalid Queue 并立刻返回确认消息等待 核心1 处理核心0 收到确认消息后把 a 写入缓存继续处理 b 的写入由于 b 是 E 状态直接写入缓存核心1 发送 BusRd 消息读取到新的 b 值然后获取 aS 状态值是0因为使其无效的消息还在 Invalid Queue 中断言失败。引入 Invalid Queue 后对核心1 来说看到的 a 和 b 的写入又出现乱序了。
解决办法是继续加内存屏障核心1 想越过屏障必须清空 Invalid Queue及时处理了对 a 的无效然后读取到新的 a 值如下代码
int a 0, b 0;
// CPU0
void foo() {a 1;smp_mb();b 1;
}
// CPU1
void bar() {while (b 0) continue;smp_mb(); //继续加内存屏障assert(a 1);
}这里使用的内存屏障是全屏障包括读写屏障过于严格了会导致性能下降所以有了细粒度的读屏障和写屏障。
读写屏障分离
分离的写屏障和读屏障的出现是为了更加精细地控制 Store Buffer 和 Invalid Queue 的顺序。
读屏障不允许其前后的读操作越过屏障 写屏障不允许其前后的写操作越过屏障
int a 0, b 0;
// CPU0
void foo() {a 1;smp_wmb(); //写屏障b 1;
}
// CPU1
void bar() {while (b 0) continue;smp_rmb(); //读屏障assert(a 1);
}单向屏障
单向屏障 (half-way barrier) 也是一种内存屏障但它不是以读写来区分的而是像单行道一样只允许单向通行例如 ARM 中的 stlr 和 ldar 指令就是这样。
stlr 的全称是 store release register包括 StoreStore barrier 和 LoadStore barrier场景少通常使用 release 语义将寄存器的值写入内存ldar 的全称是 load acquire register包括 LoadLoad barrier 和 LoadStore barrier通常使用 acquire 语义从内存中将值加载入寄存器
release 语义的内存屏障只不允许其前面的读写向后越过屏障挡前不挡后 acquire 语义的内存屏障只不允许其后面的读写向前越过屏障挡后不挡前
x86-TSO
x86-TSO 有下面几个特点
Store Buffer 被实现为 FIFO 队列CPU 务必优先读取本地 Store Buffer 中的值如果有的话否则去缓存或内存里读取因为 Store Buffer 是 FIFO所以写写不会重排也就不需要 StoreStore barrierMFENCE 指令用于清空本地 Store Buffer并将数据刷到缓存和内存某 CPU 执行 lock 前缀的指令时会去争抢全局锁拿到锁后其他线程的读取操作会被阻塞在释放锁之前会清空该线程的本地的 Store Buffer这里和 MFENCE 执行逻辑类似Store Buffer 被写入变量后除了被其他线程持有锁以外的情况在任何时刻均有可能写回内存。 因为没有引入 Invalid Queue所以不需要 LoadLoad barrierLoadStore barrier 仅在乱序(out-of-order)处理器上有效因为等待写指令可以绕过读指令而 x86-TSO 相对其他平台缓存一致性是最严格的读操作不会延后不会使读写重排那么最后只有 StoreLoad barrier 是有效的其他屏障都是no-op。
C 内存模型
C11 原子操作的很多函数都有个 std::memory_order 参数这个参数就是这里所说的内存模型对应缓存一致性模型其作用是对同一时间的读写操作进行排序一共定义了 6 种类型如下
memory_order_relaxed松散内存序只用来保证对原子对象的操作是原子的在不需要保证顺序时使用
memory_order_release释放操作在写入某原子对象时当前线程的任何前面的读写操作都不允许重排到这个操作的后面去并且当前线程的所有内存写入都在对同一个原子对象进行获取的其他线程可见通常与memory_order_acquire 或 memory_order_consume 配对使用
memory_order_acquire获得操作在读取某原子对象时当前线程的任何后面的读写操作都不允许重排到这个操作的前面去并且其他线程在对同一个原子对象释放之前的所有内存写入都在当前线程可见
memory_order_consume同 memory_order_acquire 类似区别是它仅对依赖于该原子变量操作涉及的对象比如这个操作发生在原子变量 a 上而 s a b那 s 依赖于 a但 b 不依赖于 a当然这里也有循环依赖的问题例如t s 1因为 s 依赖于 a那 t 其实也是依赖于 a 的在大多数平台上这只会影响编译器的优化不建议使用
memory_order_acq_rel获得释放操作一个读‐修改‐写操作同时具有获得语义和释放语义即它前后的任何读写操作都不允许重排并且其他线程在对同一个原子对象释放之前的所有内存写入都在当前线程可见当前线程的所有内存写入都在对同一个原子对象进行获取的其他线程可见
memory_order_seq_cst顺序一致性语义对于读操作相当于获得对于写操作相当于释放对于读‐修改‐写操作相当于获得释放是所有原子操作的默认内存序并且会对所有使用此模型的原子操作建立一个全局顺序保证了多个原子变量的操作在所有线程里观察到的操作顺序相同当然它是最慢的同步模型。
在不同的 CPU 架构上这些模型的具体实现方式可能不同但是 C11 帮你屏蔽了内部细节不用考虑内存屏障只要符合上面的使用规则就能得到想要的效果。可能有时使用的模型粒度比较大会损耗性能当然还是使用各平台底层的内存屏障粒度更准确效率也会更高。
