ui做套网站多少钱,网站开发ios,网站开发建设类合同,杭州 网站建设 哪家强转自这篇 CPU Cache#xff0c;估计也没人看
基础知识
首先#xff0c;我们都知道现在的 CPU 多核技术#xff0c;都会有几级缓存#xff0c;老的 CPU 会有两级内存#xff08;L1 和 L2#xff09;#xff0c;新的CPU会有三级内存#xff08;L1#xff0c;L2#x…转自这篇 CPU Cache估计也没人看
基础知识
首先我们都知道现在的 CPU 多核技术都会有几级缓存老的 CPU 会有两级内存L1 和 L2新的CPU会有三级内存L1L2L3 如下图所示 其中 L1 缓存分成两种一种是指令缓存一种是数据缓存。L2 缓存和 L3 缓存不分指令和数据。 L1 和 L2 缓存在每一个 CPU 核中L3 则是所有 CPU 核心共享的内存。 L1、L2、L3 的越离CPU近就越小速度也越快越离 CPU 远速度也越慢。
再往后面就是内存内存的后面就是硬盘。我们来看一些他们的速度 L1 的存取速度4 个CPU时钟周期 L2 的存取速度 11 个CPU时钟周期 L3 的存取速度39 个CPU时钟周期 RAM内存的存取速度 107 个CPU时钟周期
我们可以看到L1 的速度是 RAM 的 27 倍但是 L1/L2 的大小基本上也就是 KB 级别的L3 会是 MB 级别的。例如Intel Core i7-8700K 是一个 6 核的 CPU每核上的 L1 是 64KB数据和指令各 32KBL2 是 256KL3 有 2MB我的苹果电脑是 Intel Core i9-8950HK和Core i7-8700K 的Cache大小一样。
我们的数据就从内存向上先到 L3再到 L2再到 L1最后到寄存器进行 CPU 计算。为什么会设计成三层这里有下面几个方面的考虑 一个方面是物理速度如果要更大的容量就需要更多的晶体管除了芯片的体积会变大更重要的是大量的晶体管会导致速度下降因为访问速度和要访问的晶体管所在的位置成反比也就是当信号路径变长时通信速度会变慢。这部分是物理问题。 另外一个问题是多核技术中数据的状态需要在多个CPU中进行同步并且我们可以看到cache 和RAM 的速度差距太大所以多级不同尺寸的缓存有利于提高整体的性能。
这个世界永远是平衡的一面变得有多光鲜另一面也会变得有多黑暗。建立这么多级的缓存一定就会引入其它的问题这里有两个比较重要的问题 一个是比较简单的缓存的命中率的问题。 另一个是比较复杂的缓存更新的一致性问题。
尤其是第二个问题在多核技术下这就很像分布式的系统了要对多个地方进行更新。
缓存的命中
在说明这两个问题之前。我们需要要解一个术语 Cache Line。缓存基本上来说就是把后面的数据加载到离自己近的地方对于 CPU 来说它是不会一个字节一个字节的加载的因为这非常没有效率一般来说都是要一块一块的加载的对于这样的一块一块的数据单位术语叫 Cache Line一般来说一个主流的 CPU 的 Cache Line 是 64 Bytes也有的CPU用32Bytes和128Bytes64 Bytes也就是 16 个 32 位的整型这就是 CPU 从内存中捞数据上来的最小数据单位。
比如Cache Line是最小单位64Bytes所以先把 Cache 分布多个 Cache Line比如L1 有 32KB那么32KB/64B 512 个 Cache Line。
一方面缓存需要把内存里的数据放到放进来英文叫 CPU Associativity。Cache 的数据放置的策略决定了内存中的数据块会拷贝到 CPU Cache 中的哪个位置上因为 Cache 的大小远远小于内存所以需要有一种地址关联的算法能够让内存中的数据可以被映射到 Cache 中来。这个有点像内存地址从逻辑地址向物理地址映射的方法但不完全一样。
基本上来说我们会有如下的一些方法。 一种方法是任何一个内存地址的数据可以被缓存在任何一个 Cache Line 里这种方法是最灵活的但是如果我们要知道一个内存是否存在于 Cache 中我们就需要进行 O(n) 复杂度的 Cache 遍历这是很没有效率的。 另一种方法为了降低缓存搜索算法我们需要使用像Hash Table这样的数据结构最简单的hash table就是做求模运算比如我们的 L1 Cache 有 512 个 Cache Line那么公式内存地址 mod 512* 64 就可以直接找到所在的Cache地址的偏移了。但是这样的方式需要我们的程序对内存地址的访问要非常地平均不然冲突就会非常严重。这成了一种非常理想的情况了。 为了避免上述的两种方案的问题于是就要容忍一定的hash冲突也就出现了 N-Way 关联。也就是把连续的N 个 Cache Line 绑成一组然后先把找到相关的组然后再在这个组内找到相关的 Cache Line。这叫 Set Associativity。如下图所示。 对于 N-Way 组关联可能有点不好理解这里个例子并多说一些细节不然后面的代码你会不能理解Intel 大多数处理器的 L1 Cache 都是 32KB8-Way 组相联Cache Line 是 64 Bytes。这意味着 32KB的可以分成32KB / 64 512 条 Cache Line。 因为有8 Way于是会每一Way 有 512 / 8 64 条 Cache Line。 于是每一路就有 64 x 64 4096 Byts 的内存。
为了方便索引内存地址 Tag每条 Cache Line 前都会有一个独立分配的 24 bits来存的 tag其就是内存地址的前24bits Index内存地址后续的 6 个 bits 则是在这一 Way 的是Cache Line 索引2^6 64 刚好可以索引64条Cache Line Offset再往后的 6bits 用于表示在 Cache Line 里的偏移量
如下图所示图片来自《Cache: a place for concealment and safekeeping》
当拿到一个内存地址的时候先拿出中间的 6bits 来找到是哪组。 然后在这一个 8 组的 cache line 中再进行 O(n) n8 的遍历主是要匹配前 24bits 的 tag。如果匹配中了就算命中如果没有匹配到那就是 cache miss如果是读操作就需要进向后面的缓存进行访问了。L2/L3 同样是这样的算法。而淘汰算法有两种一种是随机一种是 LRU。现在一般都是以 LRU 的算法通过增加一个访问计数器来实现 这也意味着 L1 Cache 可映射 36bits 的内存地址一共 2^36 64GB 的内存 当 CPU 要访问一个内存的时候通过这个内存中间的 6bits 定位是哪个 set通过前 24bits 定位相应的Cache Line。 就像一个 hash Table 的数据结构一样先是 O(1)的索引然后进入冲突搜索。 因为中间的 6bits 决定了一个同一个 set所以对于一段连续的内存来说每隔 4096 的内存会被放在同一个组内导致缓存冲突。
此外当有数据没有命中缓存的时候CPU 就会以最小为 Cache Line 的单元向内存更新数据。当然CPU 并不一定只是更新 64Bytes因为访问主存实在是太慢了所以一般都会多更新一些。好的 CPU 会有一些预测的技术如果找到一种 pattern 的话就会预先加载更多的内存包括指令也可以预加载。这叫 Prefetching 技术 参看Wikipedia 的 Cache Prefetching 和 纽约州立大学的 Memory Prefetching。比如你在for-loop访问一个连续的数组你的步长是一个固定的数内存就可以做到prefetching。注指令也是以预加载的方式执行参看本站的《代码执行的效率》中的第三个示例
了解这些细节会有利于我们知道在什么情况下有可以导致缓存的失效。
缓存的一致性
对于主流的 CPU 来说缓存的写操作基本上是两种策略参看本站《缓存更新的套路》 一种是 Write Back写操作只要在 cache 上然后再 flush 到内存上。 一种是 Write Through写操作同时写到 cache 和内存上。
为了提高写的性能一般来说主流的 CPU如Intel Core i7/i9采用的是 Write Back 的策略因为直接写内存实在是太慢了。
好了现在问题来了如果有一个数据 x 在 CPU 第 0 核的缓存上被更新了那么其它 CPU 核上对于这个数据 x 的值也要被更新这就是缓存一致性的问题。当然对于我们上层的程序我们不用关心 CPU 多个核的缓存是怎么同步的这对上层的代码来说都是透明的
一般来说在 CPU 硬件上会有两种方法来解决这个问题。 Directory 协议。这种方法的典型实现是要设计一个集中式控制器它是主存储器控制器的一部分。其中有一个目录存储在主存储器中其中包含有关各种本地缓存内容的全局状态信息。当单个 CPU Cache 发出读写请求时这个集中式控制器会检查并发出必要的命令以在主存和 CPU Cache之间或在 CPU Cache自身之间进行数据同步和传输。 Snoopy 协议。这种协议更像是一种数据通知的总线型的技术。CPU Cache 通过这个协议可以识别其它Cache上的数据状态。如果有数据共享的话可以通过广播机制将共享数据的状态通知给其它 CPU Cache。这个协议要求每个 CPU Cache 都可以窥探数据事件的通知并做出相应的反应。如下图所示有一个 Snoopy Bus 的总线。 因为 Directory 协议是一个中心式的会有性能瓶颈而且会增加整体设计的复杂度。而 Snoopy 协议更像是微服务消息通讯所以现在基本都是使用 Snoopy 的总线的设计。
这里我想多写一些细节因为这种微观的东西让人不自然地就会跟分布式系统关联起来在分布式系统中我们一般用 Paxos/Raft 这样的分布式一致性的算法。而在 CPU 的微观世界里则不必使用这样的算法原因是因为 CPU 的多个核的硬件不必考虑网络会断会延迟的问题。所以CPU 的多核心缓存间的同步的核心就是要管理好数据的状态就好了。
这里介绍几个状态协议先从最简单的开始MESI 协议这个协议跟那个著名的足球运动员梅西没什么关系其主要表示缓存数据有四个状态Modified已修改, Exclusive独占的,Shared共享的Invalid无效的。
这些状态的状态机如下所示有点复杂你可以先不看这个图就是想告诉你状态控制有多复杂 下面是个示例如果你想看一下动画演示的话这里有一个网页MESI Interactive Animations你可以进行交互操作这个动画演示中使用的 Write Through 算法
当前操作CPU0CPU1Memory说明1) CPU0 read(x)x1 (E)x1只有一个CPU有 x 变量 所以状态是 Exclusive2) CPU1 read(x)x1 (S)x1(S)x1有两个CPU都读取 x 变量 所以状态变成 Shared3) CPU0 write(x,9)x9 (M)x1(I)x1变量改变在CPU0中状态 变成 Modified在CPU1中 状态变成 Invalid4) 变量 x 写回内存x9 (M)X1(I)x9目前的状态不变5) CPU1 read(x)x9 (S)x9(S)x9变量同步到所有的Cache中 状态回到Shared
MESI 这种协议在数据更新后会标记其它共享的 CPU 缓存的数据拷贝为 Invalid 状态然后当其它 CPU 再次read 的时候就会出现 cache miss 的问题此时再从内存中更新数据。从内存中更新数据意味着 20 倍速度的降低。我们能不能直接从我隔壁的 CPU 缓存中更新是的这就可以增加很多速度了但是状态控制也就变麻烦了。还需要多来一个状态Owner(宿主)用于标记我是更新数据的源。于是出现了 MOESI 协议
MOESI 协议的状态机和演示示例我就不贴了有兴趣可以上Berkeley上看看相关的课件我们只需要理解MOESI协议允许 CPU Cache 间同步数据于是也降低了对内存的操作性能是非常大的提升但是控制逻辑也非常复杂。
顺便说一下与 MOESI 协议类似的一个协议是 MESIF其中的 F 是 Forward同样是把更新过的数据转发给别的 CPU Cache 但是MOESI 中的 Owner 状态 和MESIF 中的 Forward 状态有一个非常大的不一样—— Owner 状态下的数据是 dirty 的还没有写回内存Forward 状态下的数据是 clean的可以丢弃而不用另行通知。
需要说明的是AMD 用 MOESIIntel 用 MESIF。所以F 状态主要是针对 CPU L3 Cache 设计的前面我们说过L3 是所有 CPU 核心共享的。相关的比较可以参看StackOverlow上这个问题的答案
程序性能
了解了我们上面的这些东西后我们来看一下对于程序的影响。
示例一
首先假设我们有一个64M长的数组设想一下下面的两个循环 const int LEN 64*1024*1024;int *arr new int[LEN];for (int i 0; i LEN; i 2) arr[i] * i;for (int i 0; i LEN; i 8) arr[i] * i;
按我们的想法来看第二个循环要比第一个循环少4倍的计算量其应该也是要快4倍的。但实际跑下来并不是在我的机器上第一个循环需要 127 毫秒第二个循环则需要 121 毫秒相差无几。这里最主要的原因就是 Cache Line因为 CPU 会以一个 Cache Line 64Bytes 最小时单位加载也就是 16 个 32bits 的整型所以无论你步长是 2 还是 8都差不多。而后面的乘法其实是不耗 CPU 时间的。
示例二
我们再来看一个与缓存命中率有关的代码我们以一定的步长increment 来访问一个连续的数组。 for (int i 0; i 10000000; i) {for (int j 0; j size; j increment) {memory[j] j;}}
我们测试一下在下表中 表头是步长也就是每次跳多少个整数而纵向是这个数组可以跳几次你可以理解为要几条 Cache Line于是表中的任何一项代表了这个数组有多少而且步长是多少。比如横轴是 512纵轴是4意思是这个数组有 4*512 2048 个长度访问时按512步长访问也就是访问其中的这几项[0, 512, 1024, 1536] 这四项。
表中同的项是是循环 1000 万次的时间单位是“微秒”除以1000后是毫秒 | count | 1 | 16 | 512 | 1024 |------------------------------------------| 1 | 17539 | 16726 | 15143 | 14477 || 2 | 15420 | 14648 | 13552 | 13343 || 3 | 14716 | 14463 | 15086 | 17509 || 4 | 18976 | 18829 | 18961 | 21645 || 5 | 23693 | 23436 | 74349 | 29796 || 6 | 23264 | 23707 | 27005 | 44103 || 7 | 28574 | 28979 | 33169 | 58759 || 8 | 33155 | 34405 | 39339 | 65182 || 9 | 37088 | 37788 | 49863 |156745 || 10 | 41543 | 42103 | 58533 |215278 || 11 | 47638 | 50329 | 66620 |335603 || 12 | 49759 | 51228 | 75087 |305075 || 13 | 53938 | 53924 | 77790 |366879 || 14 | 58422 | 59565 | 90501 |466368 || 15 | 62161 | 64129 | 90814 |525780 || 16 | 67061 | 66663 | 98734 |440558 || 17 | 71132 | 69753 |171203 |506631 || 18 | 74102 | 73130 |293947 |550920 |我们可以看到从 [91024] 以后时间显著上升。包括 [17512] 和 [18,512] 也显著上升。这是因为我机器的 L1 Cache 是 32KB, 8 Way 的前面说过8 Way 的有 64 组每组 8 个 Cache Line当 for-loop步长超过 1024 个整型也就是正好 4096 Bytes 时也就是导致内存地址的变化是变化在高位的 24bits 上而低位的1 2bits 变化不大尤其是中间6bits没有变化导致全部命中同一组 set导致大量的 cache 冲突导致性能下降时间上升。而 [16, 512]也是一样的其中的几步开始导致L1 Cache开始冲突失效。
示例三
接下来我们再来看个示例。下面是一个二维数组的两种遍历方式一个逐行遍历一个是逐列遍历这两种方式在理论上来说寻址和计算量都是一样的执行时间应该也是一样的。 const int row 1024;const int col 512int matrix[row][col];//逐行遍历int sum_row0;for(int _r0; _rrow; _r) {for(int _c0; _ccol; _c){sum_row matrix[_r][_c];}}//逐列遍历int sum_col0;for(int _c0; _ccol; _c) {for(int _r0; _rrow; _r){sum_col matrix[_r][_c];}}
然而并不是在我的机器上得到下面的结果。 逐行遍历0.081ms 逐列遍历1.069ms
执行时间有十几倍的差距。其中的原因就是逐列遍历对于 CPU Cache 的运作方式并不友好所以付出巨大的代价。
示例四
接下来我们来看一下多核下的性能问题参看如下的代码。两个线程在操作一个数组的两个不同的元素无需加锁线程循环1000万次做加法操作。在下面的代码中我高亮了一行就是p2指针要么是p[1]或是 p[30]理论上来说无论访问哪两个数组元素都应该是一样的执行时间。 void fn (int* data) {for(int i 0; i 10*1024*1024; i)*data rand();}int p[32];int *p1 p[0];int *p2 p[1]; // int *p2 p[30];thread t1(fn, p1);thread t2(fn, p2);
然而并不是在我的机器上执行下来的结果是 对于 p[0] 和 p[1] 560ms 对于 p[0] 和 p[30]104ms
这是因为 p[0] 和 p[1] 在同一条 Cache Line 上而 p[0] 和 p[30] 则不可能在同一条Cache Line 上 CPU 的缓存最小的更新单位是 Cache Line所以这导致虽然两个线程在写不同的数据但是因为这两个数据在同一条 Cache Line 上就会导致缓存需要不断进在两个 CPU 的 L1/L2 中进行同步从而导致了 5 倍的时间差异。
示例五
接下来我们再来看一下另外一段代码我们想统计一下一个数组中的奇数个数但是这个数组太大了我们希望可以用多线程来完成这个统计。下面的代码中我们为每一个线程传入一个 id 然后通过这个 id 来完成对应数组段的统计任务。这样可以加快整个处理速度。 int total_size 16 * 1024 * 1024; //数组长度int* test_data new test_data[total_size]; //数组int nthread 6; //线程数因为我的机器是6核的int result[nthread]; //收集结果的数组void thread_func (int id) {result[id] 0;int chunk_size total_size / nthread 1;int start id * chunk_size;int end min(start chunk_size, total_size);for ( int i start; i end; i ) {if (test_data[i] % 2 ! 0 ) result[id];}}
然而在执行过程中你会发现6 个线程居然跑不过 1 个线程。因为根据上面的例子你知道 result[] 这个数组中的数据在一个 Cache Line 中所以所有的线程都会对这个 Cache Line 进行写操作导致所有的线程都在不断地重新同步 result[] 所在的 Cache Line所以导致 6 个线程还跑不过一个线程的结果。这叫 False Sharing。
优化也很简单使用一个线程内的变量。 void thread_func (int id) {result[id] 0;int chunk_size total_size / nthread 1;int start id * chunk_size;int end min(start chunk_size, total_size);int c 0; //使用临时变量没有cache line的同步了for ( int i start; i end; i ) {if (test_data[i] % 2 ! 0 ) c;}result[id] c;}
我们把两个程序分别在 1 到 32 个线程上跑一下得出的结果画一张图如下所示横轴是线程数纵轴是完成统的时间单位是微秒 上图中我们可以看到灰色的曲线就是第一种方法橙色的就是第二种用局部变量的方法。当只有一个线程的时候两个方法相当基本没有什么差别但是在线程数增加的时候的时候你会发现第二种方法的性能提高的非常快。直到到达 6 个线程的时候开始变得稳定前面说过我的 CPU 是6核的。而第一种方法无论加多少线程也没有办法超过第二种方法。因为第一种方法不是 CPU Cache 友好的。也就是说第二种方法只要我的 CPU 核数足够多就可以做到线性的性能扩展让每一个 CPU 核都跑起来而第一种则不能。
