多核CPU的系统架构和原理说明及编程注意事项详细说明
好久没有写一些微观方面的文章了，今天写一篇关于cpu cache相关的文章，这篇文章会讲述一些多核 cpu 的系统架构以及其原理，包括对程序性能上的影响，以及在进行并发编程的时候需要注意到的一些问题。这篇文章我会尽量地写简单和通俗易懂一些，主要是讲清楚相关的原理和问题，而对于一些细节和延伸阅读我会在文章最好给出相关的资源。
本文比较长，主要分成这么几个部分：基础知识、缓存的命中、缓存的一致性、相关的代码示例和延伸阅读。
因为无论你写什么样的代码都会交给cpu来执行，所以，如果你想写出性能比较高的代码，这篇文章中的技术还是应该认真学习的。
基础知识
首先，我们都知道现在的cpu多核技术，都会有几级缓存，老的cpu会有两级内存（l1和l2），新的cpu会有三级内存（l1，l2，l3 ），如下图所示：
其中：
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（数据和指令各32kb），l2 是 256k，l3有12mb（我的苹果电脑是 intel core i9-8950hk ，和core i7-8700k的cache大小一样）。
于是我们的数据就从内存向上，先到l3，再到l2，再到l1，最后到寄存器进行cpu计算。为什么会设计成三层？这里有下面几个方面的考虑：
一个方面是物理速度，如果你要更在的容量就需要更多的晶体管，除了芯片的体积会变大，更重要的是大量的晶体管会导致速度下降，因为访问速度和要访问的晶体管的位置成反比，也就是当信号路径变长时，通信速度会变慢。这部分是物理问题。
另外一个问题是，多核技术中，数据的状态需要在多个cpu中进行同步，并且，我们可以看到，cache和ram的速度差距太大，所以，多级不同尺寸的缓存有利于提高整体的性能。
这个世界永远是平衡的，一面变得有多光鲜，另一面也会变得有多黑暗。建立这么多级的缓存，一定就会引入其它的问题，这里有两个比较重要的问题，
一个是比较简单的缓存的命中率的问题。
另一个是比较复杂的缓存更新的一致性问题。
尤其是第二个问题，在多核技术下，这就很像分布式的系统了，要对多个地方进行更新。
缓存的命中
在说明这两个问题之前。我们需要要解一个术语 cache line。缓存基本上来说就是把后面的数据加载到离自己进的地方，对于cpu来说，它是不会一个字节一个字节的加载的，因为这非常没有效率，一般来说都是要一块一块的加载的，在cpu的缓存技术中，这个术语叫“cache line”（有的中文编译成“缓存线”），一般来说，一个主流的cpu的cache line 是 64 bytes（也有的cpu用32bytes和128bytes），也就是16个32位的整型。也就是说，cpu从内存中捞数据上来的最小数据单位。
比如：cache line是最小单位（64bytes），所以先把cache分布多个cache line，比如：l1有32kb，那么，32kb/64b = 500 个 cache line。
一方面，缓存需要把内存里的数据放到放进来，英文叫 cpu associativity。cache的数据放置的策略决定了内存中的数据块会拷贝到cpu cache中的哪个位置，因为cache的大小远远小于内存，所以，需要有一种地址关联的算法，能够让内存中的数据可以被映射到cache中来。这个有点像内存管理的方法。
基本上来说，我们会有如下的一些方法。
一种方法是，任何一个内存地址的数据可以被缓存在任何一个cache line里，这种方法是最灵活的，但是，如果我们要知道一个内存是否存在于cache中，我们就需要进行o（n）复杂度的cache遍历，这是很没有效率的。
另一种方法，为了降低缓存搜索算法，我们需要使用像hash table这样的数据结构，最简单的hash table就是做“求模运算”，比如：我们的l1 cache有500个cache line，那么，公式：`（内存地址 mod 500）x 64` 就可以直接找到所在的cache地址的偏移了。但是，这样的方式需要我们的程序对内存地址的访问要非常地平均，这成了一种非常理想的情况了。
为了避免上述的两种方案的问题，于是就要容忍一定的hash冲突，也就出现了 n-way 关联。也就是把连续的n个cache line绑成一组，然后，先把找到相关的组，然后再在这个组内找到相关的cache line。
那么，cache的命中率会成为程序运行性能非常关键的事，所以，了解上面的这些东西，会有利于我们知道在什么情况下有可以导致缓存的失效。
对于 n-way 关联我们取个例子，并多说一些细节（因为后面会用到），intel 大多数处理器的l1 cache都是32kb，8-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 》）
（图片来自《 cache： a place for concealment and safekeeping 》）
这意味着：
l1 cache 可映射 36bits 的内存地址，一共 2^36 = 64gb的内存
因为只要头24bits相同就会被映射到同一个way中，所以，每4096个地址会放在一way中。
当cpu要访问一个内存的时候，通过这个内存的前24bits 和中间的6bits可以直接定位相应的cache line。
此外，当有数据没有命中缓存的时候，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 都可以 “窥探” 数据事件的通知并做出相应的反应。
因为directory协议是一个中心式的，会有性能瓶颈，而且会增加整体设计的复杂度。而snoopy协议更像是微服务+消息通讯，所以，现在基本都是使用snoopy的总线的设计。
这里，我想多写一些细节，因为这种微观的东西，不自然就就会更分布式系统相关联，在分布式系统中我们一般用paxos/raft这样的分布式一致性的算法。而在cpu的微观世界里，则不必使用这样的算法，原因是因为cpu的多个核的硬件不必考虑网络会断会延迟的问题。所以，cpu的多核心缓存间的同步的核心就是要管理好数据的状态就好了。
这里介绍几个状态协议，先从最简单的开始，mesi协议，这个协议跟那个著名的足球运动员梅西没什么关系，其主要表示缓存数据有四个状态：modified（已修改）， exclusive（独占的），shared（共享的），invalid（无效的）。
这些状态的状态机如下所示：
下面是个示例（如果你想看一下动画演示的话，这里有一个网页（ mesi interactive animations ），你可以进行交互操作，这个动画演示中使用的write through算法）：
当前操作cpu0cpu1memory说明1） cpu0 read（x）x=1 （e）x=1只有一个cpu有 x 变量，
所以，状态是 exclusive2） cpu1 read（x）x=1 （s）x=1（s）x=1有两个cpu都读取 x 变量，
所以状态变成 shared3） cpu0 write（x，9）x= 9 （m）x=1（i）x=1变量改变，在cpu0中状态
变成 modified，在cpu1中
状态变成 invalid4） 变量 x 写回内存x=9 （m）x=1（i）x=9目前的状态不变5） cpu1 read（x）x=9 （s）x=9（s）x=9变量同步到所有的cache中，
状态回到shared
mesi 这种协议在数据更新后，会标记其它共享的cpu缓存的数据拷贝为invalid状态，然后当其它cpu再次read的时候，就会出现 cache misses 的问题，此时再从内存中更新数据。可见，从内存中更新数据意味着20倍速度的降低。我们能不直接从我隔壁的cpu缓存中更新？是的，这就可以增加很多速度了，但是状态控制也就变麻烦了。还需要多来一个状态：owner（宿主），用于标记，我是更新数据的源。于是，现了 moesi 协议
moesi协议的状态机和演示我就不贴了，我们只需要理解moesi协议允许 cpu cache 间同步数据，于是也降低了对内存的操作，性能是非常大的提升，但是控制逻辑也非常复杂。
顺便说一下，与 moesi 协议类似的一个协议是 mesif ，其中的 f 是 forward，同样是把更新过的数据转发给别的 cpu cache 但是，moesi 中的 owner 状态 和mesif 中的 forward 状态有一个非常大的不一样—— owner状态下的数据是dirty的，还没有写回内存，forward状态下的数据是clean的，可以丢弃而不用另行通知。
需要说明的是，amd用moesi，intel用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 |
我们可以看到，从［9，1024］ 以后，时间显注上升。包括［17，512］ 和 ［18，512］ 也显注上升。这是因为，我机器的 l1 cache 是 32kb， 8 way 的，前面说过，8 way的一个组有64个cache line，也就是4096个字节，而1024个整型正好是 4096 bytes，所以，一旦过了这个界，每个步长都无法命中 l1 cache，每次都是 cache miss，所以，导致访问时间一下子就上升了。而 ［16， 512］也是一样的，其中的几步开始导致l1 cache开始失效。
示例三
接下来，我们再来看个示例。下面是一个二维数组的两种遍历方式，一个逐行遍历，一个是逐列遍历，这两种方式在理论上来说，寻址和计算量都是一样的，执行时间应该也是一样的。
const int row = 1024;const int col = 512int matrix［row］［col］;//逐行遍历int sum_row=0;for（int r=0; r《row; r++） { for（int c=0; c《col; c++）{ sum_row += matrix［r］; }}//逐列遍历int sum_col=0;for（int c=0; c《col; c++） { for（int r=0; r《row; r++）{ sum_col += matrix［r］; }}
然而，并不是，在我的机器上，得到下面的结果。
逐行遍历：0.081ms
逐列遍历：1.069ms
执行时间有十几倍的差距。其中的原因，就是逐列遍历对于cpu cache 的运作方式并不友好，所以，付出巨大的代价。
示例四
接下来，我们来看一下多核下的性能问题，参看如下的代码。两个线程在操作一个数组的两个不同的元素（无需加锁），线程循环1000万次，做加法操作。在下面的代码中，我高亮了一行，就是 p2 指针，要么是 p［1］ ，或是 p［18］ ，理论上来说，无论访问哪两个数组元素，都应该是一样的执行时间。
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 友好的。
疯狂比特币背后究竟有什么风险?
fireflyFace-RK3399主板Android入门
OPPO R11首发的骁龙660怎么样？能否超越去年的骁龙821？
IC设计产业成投资重点 九成半导体基金欲注资
如何实现网络型电能质量监测装置的人机交互设计
多核CPU的系统架构和原理说明及编程注意事项详细说明
2023国际量子光子学大会圆满闭幕
农行5G智慧银行的正式运营开启了5G+金融建设的新实践
强力巨彩：LED大显示普及的宏伟使命
浅析推动生命科学发展的光泵半导体激光（OPSL）技术（三）
2012最热门新产品：力科12位高精度示波器榜上有名
Win10 20H1终于修复显示器卡顿问题 问题已被用户提及快1年
C++内置基本数据类型
赛扬G4900T值不值得买 很适合做第二套低功耗平台
智慧城市3.0到底应该是怎么样的
智能型器件Astro II简介
CAN总线负载率怎么估算？
用人工神经网络控制真实大脑，MIT的科学家做到了
顶尖无人驾驶汽车团队那么多，不用总盯着谷歌
多种气体传感器在电池储能电站安全预警中的应用
本文比较长，主要分成这么几个部分：基础知识、缓存的命中、缓存的一致性、相关的代码示例和延伸阅读。
因为无论你写什么样的代码都会交给cpu来执行，所以，如果你想写出性能比较高的代码，这篇文章中的技术还是应该认真学习的。
基础知识
首先，我们都知道现在的cpu多核技术，都会有几级缓存，老的cpu会有两级内存（l1和l2），新的cpu会有三级内存（l1，l2，l3 ），如下图所示：
其中：
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（数据和指令各32kb），l2 是 256k，l3有12mb（我的苹果电脑是 intel core i9-8950hk ，和core i7-8700k的cache大小一样）。
于是我们的数据就从内存向上，先到l3，再到l2，再到l1，最后到寄存器进行cpu计算。为什么会设计成三层？这里有下面几个方面的考虑：
一个方面是物理速度，如果你要更在的容量就需要更多的晶体管，除了芯片的体积会变大，更重要的是大量的晶体管会导致速度下降，因为访问速度和要访问的晶体管的位置成反比，也就是当信号路径变长时，通信速度会变慢。这部分是物理问题。
另外一个问题是，多核技术中，数据的状态需要在多个cpu中进行同步，并且，我们可以看到，cache和ram的速度差距太大，所以，多级不同尺寸的缓存有利于提高整体的性能。
这个世界永远是平衡的，一面变得有多光鲜，另一面也会变得有多黑暗。建立这么多级的缓存，一定就会引入其它的问题，这里有两个比较重要的问题，
一个是比较简单的缓存的命中率的问题。
另一个是比较复杂的缓存更新的一致性问题。
尤其是第二个问题，在多核技术下，这就很像分布式的系统了，要对多个地方进行更新。
缓存的命中
在说明这两个问题之前。我们需要要解一个术语 cache line。缓存基本上来说就是把后面的数据加载到离自己进的地方，对于cpu来说，它是不会一个字节一个字节的加载的，因为这非常没有效率，一般来说都是要一块一块的加载的，在cpu的缓存技术中，这个术语叫“cache line”（有的中文编译成“缓存线”），一般来说，一个主流的cpu的cache line 是 64 bytes（也有的cpu用32bytes和128bytes），也就是16个32位的整型。也就是说，cpu从内存中捞数据上来的最小数据单位。
比如：cache line是最小单位（64bytes），所以先把cache分布多个cache line，比如：l1有32kb，那么，32kb/64b = 500 个 cache line。
一方面，缓存需要把内存里的数据放到放进来，英文叫 cpu associativity。cache的数据放置的策略决定了内存中的数据块会拷贝到cpu cache中的哪个位置，因为cache的大小远远小于内存，所以，需要有一种地址关联的算法，能够让内存中的数据可以被映射到cache中来。这个有点像内存管理的方法。
基本上来说，我们会有如下的一些方法。
一种方法是，任何一个内存地址的数据可以被缓存在任何一个cache line里，这种方法是最灵活的，但是，如果我们要知道一个内存是否存在于cache中，我们就需要进行o（n）复杂度的cache遍历，这是很没有效率的。
另一种方法，为了降低缓存搜索算法，我们需要使用像hash table这样的数据结构，最简单的hash table就是做“求模运算”，比如：我们的l1 cache有500个cache line，那么，公式：`（内存地址 mod 500）x 64` 就可以直接找到所在的cache地址的偏移了。但是，这样的方式需要我们的程序对内存地址的访问要非常地平均，这成了一种非常理想的情况了。
为了避免上述的两种方案的问题，于是就要容忍一定的hash冲突，也就出现了 n-way 关联。也就是把连续的n个cache line绑成一组，然后，先把找到相关的组，然后再在这个组内找到相关的cache line。
那么，cache的命中率会成为程序运行性能非常关键的事，所以，了解上面的这些东西，会有利于我们知道在什么情况下有可以导致缓存的失效。
对于 n-way 关联我们取个例子，并多说一些细节（因为后面会用到），intel 大多数处理器的l1 cache都是32kb，8-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 》）
（图片来自《 cache： a place for concealment and safekeeping 》）
这意味着：
l1 cache 可映射 36bits 的内存地址，一共 2^36 = 64gb的内存
因为只要头24bits相同就会被映射到同一个way中，所以，每4096个地址会放在一way中。
当cpu要访问一个内存的时候，通过这个内存的前24bits 和中间的6bits可以直接定位相应的cache line。
此外，当有数据没有命中缓存的时候，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 都可以 “窥探” 数据事件的通知并做出相应的反应。
因为directory协议是一个中心式的，会有性能瓶颈，而且会增加整体设计的复杂度。而snoopy协议更像是微服务+消息通讯，所以，现在基本都是使用snoopy的总线的设计。
这里，我想多写一些细节，因为这种微观的东西，不自然就就会更分布式系统相关联，在分布式系统中我们一般用paxos/raft这样的分布式一致性的算法。而在cpu的微观世界里，则不必使用这样的算法，原因是因为cpu的多个核的硬件不必考虑网络会断会延迟的问题。所以，cpu的多核心缓存间的同步的核心就是要管理好数据的状态就好了。
这里介绍几个状态协议，先从最简单的开始，mesi协议，这个协议跟那个著名的足球运动员梅西没什么关系，其主要表示缓存数据有四个状态：modified（已修改）， exclusive（独占的），shared（共享的），invalid（无效的）。
这些状态的状态机如下所示：
下面是个示例（如果你想看一下动画演示的话，这里有一个网页（ mesi interactive animations ），你可以进行交互操作，这个动画演示中使用的write through算法）：
当前操作cpu0cpu1memory说明1） cpu0 read（x）x=1 （e）x=1只有一个cpu有 x 变量，
所以，状态是 exclusive2） cpu1 read（x）x=1 （s）x=1（s）x=1有两个cpu都读取 x 变量，
所以状态变成 shared3） cpu0 write（x，9）x= 9 （m）x=1（i）x=1变量改变，在cpu0中状态
变成 modified，在cpu1中
状态变成 invalid4） 变量 x 写回内存x=9 （m）x=1（i）x=9目前的状态不变5） cpu1 read（x）x=9 （s）x=9（s）x=9变量同步到所有的cache中，
状态回到shared
mesi 这种协议在数据更新后，会标记其它共享的cpu缓存的数据拷贝为invalid状态，然后当其它cpu再次read的时候，就会出现 cache misses 的问题，此时再从内存中更新数据。可见，从内存中更新数据意味着20倍速度的降低。我们能不直接从我隔壁的cpu缓存中更新？是的，这就可以增加很多速度了，但是状态控制也就变麻烦了。还需要多来一个状态：owner（宿主），用于标记，我是更新数据的源。于是，现了 moesi 协议
moesi协议的状态机和演示我就不贴了，我们只需要理解moesi协议允许 cpu cache 间同步数据，于是也降低了对内存的操作，性能是非常大的提升，但是控制逻辑也非常复杂。
顺便说一下，与 moesi 协议类似的一个协议是 mesif ，其中的 f 是 forward，同样是把更新过的数据转发给别的 cpu cache 但是，moesi 中的 owner 状态 和mesif 中的 forward 状态有一个非常大的不一样—— owner状态下的数据是dirty的，还没有写回内存，forward状态下的数据是clean的，可以丢弃而不用另行通知。
需要说明的是，amd用moesi，intel用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 |
我们可以看到，从［9，1024］ 以后，时间显注上升。包括［17，512］ 和 ［18，512］ 也显注上升。这是因为，我机器的 l1 cache 是 32kb， 8 way 的，前面说过，8 way的一个组有64个cache line，也就是4096个字节，而1024个整型正好是 4096 bytes，所以，一旦过了这个界，每个步长都无法命中 l1 cache，每次都是 cache miss，所以，导致访问时间一下子就上升了。而 ［16， 512］也是一样的，其中的几步开始导致l1 cache开始失效。
示例三
接下来，我们再来看个示例。下面是一个二维数组的两种遍历方式，一个逐行遍历，一个是逐列遍历，这两种方式在理论上来说，寻址和计算量都是一样的，执行时间应该也是一样的。
const int row = 1024;const int col = 512int matrix［row］［col］;//逐行遍历int sum_row=0;for（int r=0; r《row; r++） { for（int c=0; c《col; c++）{ sum_row += matrix［r］; }}//逐列遍历int sum_col=0;for（int c=0; c《col; c++） { for（int r=0; r《row; r++）{ sum_col += matrix［r］; }}
然而，并不是，在我的机器上，得到下面的结果。
逐行遍历：0.081ms
逐列遍历：1.069ms
执行时间有十几倍的差距。其中的原因，就是逐列遍历对于cpu cache 的运作方式并不友好，所以，付出巨大的代价。
示例四
接下来，我们来看一下多核下的性能问题，参看如下的代码。两个线程在操作一个数组的两个不同的元素（无需加锁），线程循环1000万次，做加法操作。在下面的代码中，我高亮了一行，就是 p2 指针，要么是 p［1］ ，或是 p［18］ ，理论上来说，无论访问哪两个数组元素，都应该是一样的执行时间。
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 友好的。
疯狂比特币背后究竟有什么风险?
fireflyFace-RK3399主板Android入门
OPPO R11首发的骁龙660怎么样？能否超越去年的骁龙821？
IC设计产业成投资重点 九成半导体基金欲注资
如何实现网络型电能质量监测装置的人机交互设计
多核CPU的系统架构和原理说明及编程注意事项详细说明
2023国际量子光子学大会圆满闭幕
农行5G智慧银行的正式运营开启了5G+金融建设的新实践
强力巨彩：LED大显示普及的宏伟使命
浅析推动生命科学发展的光泵半导体激光（OPSL）技术（三）
2012最热门新产品：力科12位高精度示波器榜上有名
Win10 20H1终于修复显示器卡顿问题 问题已被用户提及快1年
C++内置基本数据类型
赛扬G4900T值不值得买 很适合做第二套低功耗平台
智慧城市3.0到底应该是怎么样的
智能型器件Astro II简介
CAN总线负载率怎么估算？
用人工神经网络控制真实大脑，MIT的科学家做到了
顶尖无人驾驶汽车团队那么多，不用总盯着谷歌
多种气体传感器在电池储能电站安全预警中的应用