首页  思维导图  详情

与程序员相关的CPU缓存知识

2020-07-09 10:27:57   1  举报





AI智能生成

CPU缓存相关信息

CPU缓存

学习总结

软件开发

读书笔记

作者其他创作

大纲/内容

基础知识

多级缓存

老的CPU有两级缓存、新的CPU有三级缓存

L1分为两种

一种是指令缓存

另一种是数据缓存

L2、L3不分指令和数据

L1和L2缓存在每个CPU核上，L3是所有CPU共享的内存

图例

一般L1、L2大小是KB级别，L3会是MB级别

与内存速度对比

L1的存取速度：4个CPU时钟周期

L2的存取速度：11个CPU时钟周期

L3的存取速度：39个CPU时钟周期

RAM内存的存取速度：107个CPU时钟周期

设计多级缓存的原因

1. 物理速度；容量大就需要更多晶体管，而更多晶体管就会使信号路径变长，使速度变慢

2. 多个CPU需要同步缓存信息，Cache与RAM的速度差距大，多级不同尺寸的缓存，有利于提高整体性能

多级缓存存在的问题

1. 缓存命中率问题

2. 缓存更新的一致性问题

缓存命中

Cache Line

主流的CPU的Cache Line大小是64 Bytes；64B是16个32位整型，是CPU读取内存中数据的最小单位

有的CPU的Cache Line是32B 或 128B

怎么查看Cache Line大小

在Linux中，查看/sys/devices/system/cpu/cpu0/cache/index1/coherency_line_size即为cache line大小

内存地址映射缓存的方法

一种方式是任何一个内存地址的数据都可以被缓存到任何一个Cache Line中

有点：最灵活

缺点：当需要确定内存是否存在于Cache中时，需要进行O(n)复杂度的Cache遍历，效率很低

另一种方式，为了降低缓存搜索算法，使用类似Hash Table这样的数据结构，但是使用Hash Table就有可能存在hash冲突的问题

为了避免上述两种方案的缺点，采用了N-Way关联方式

1. 就是把联系的N个Cache Line绑定成一组

2. 然后找到相关的组

3. 然后再在这个组内找到相关的Cache Line

4. 将内存地址映射成Tag、Index、Offset来映射Cache中的地址

对于L2/L3 同样采用 N-Way的方法

缓存淘汰算法有两种

1. 随机

2. LRU，一般都是LRU算法（通过新增一个访问计数器来实现）

Prefetching 技术

当有数据没有命中缓存的时候，CPU就会以最小为Cache Line的单元向内存更新数据。当然，CPU并不一定只是更新64Bytes，因为访问主存实在是太慢了，所以，一般都会多更新一些。好的CPU会有一些预测的技术，如果找到一种pattern的话，就会预先加载更多的内存，包括指令也可以预加载

缓存一致性

缓存策略

1. Write Back 写操作只在Cache 上，然后再flush到内存上

2. Write Through，写操作同时写到cache和内存上

主流的CPU采用的Write Back方式，因为写内存太慢了

问题引入：如果有一个数据x在cpu的第0个核上被更新了，那么其他cpu核上对于这个数据x的值也需要被更新，这就是缓存一致性问题

从CPU硬件层面，有两种解决方法

1. Directory 协议

这种方法的典型实现是要设计一个集中式的控制器，他是主存储器控制器的一部分。其中一个目录存在再主存中，其中包含了有关各种本地缓存内容的全局状态信息。当单个CPU Cache发出读写请求时，这个集中式控制器会检查并发出必要的命令，以在主存和CPU Cache或CPU Cache质检进行数据同步和传输

2. Snoopy协议

这种协议更像是一种数据通知的总线型技术。CPU Cache通过这个协议可以识别其它Cache上的数据状态。如果有数据共享的话，可以通过广播机制将共享数据的状态通知给其它CPU Cache。这个协议要求每个CPU Cache 都可以“窥探”数据事件的通知并做出相应的反应。如图所示，有一个Snoopy Bus的总线。

因为Directory协议是一个中心式的，会有性能瓶颈，而且会增加整体设计的复杂度。而Snoopy协议更像是微服务+消息通讯，所以，现在基本都是使用Snoopy的总线的设计

延伸

因为这种微观的东西，不自然就就会更分布式系统相关联，在分布式系统中我们一般用Paxos/Raft这样的分布式一致性的算法。而在CPU的微观世界里，则不必使用这样的算法，原因是因为CPU的多个核的硬件不必考虑网络会断会延迟的问题。所以，CPU的多核心缓存间的同步的核心就是要管理好数据的状态就好了

MESI协议

主要表示缓存数据有四个状态：Modified（已修改）, Exclusive（独占的）,Shared（共享的），Invalid（无效的）

MOESI协议

由于当缓存被更新为I状态时，需要重新从内存中读取，而内存读取太慢了

优化方案是从隔壁的CPU缓存中读取，这样可以增加很多的速度

这种对于MESI的改进，就叫做MOESI

https://en.wikipedia.org/wiki/MOESI_protocol

这里O是Owner(宿主)的意思

MESIF协议

与MOESI解决相同的问题

这里的F是Forward，同样是把更新过的数据转发给别的CPU Cache

MOESI中的Owner状态和MESIF中的Forward状态有一个非常大的不同：Owner状态下的数据是dirty的，还没有写会内存；Forward状态下的数据是clean的。可以丢弃而不用另行通知

AMD采用MOESI，Intel采用MESIF

代码示例

示例1

假设我们有一个64M长的数组，设想一下下面的两个循环

按我们的想法来看，第二个循环要比第一个循环少4倍的计算量，其应该也是要快4倍的。但实际跑下来并不是，在我的机器上，第一个循环需要127毫秒，第二个循环则需要121毫秒，相差无几。这里最主要的原因就是 Cache Line，因为CPU会以一个Cache Line 64Bytes最小时单位加载，也就是16个32bits的整型，所以，无论你步长是2还是8，都差不多。而后面的乘法其实是不耗CPU时间的。

示例2

我们以一定的步长increment 来访问一个连续的数组

我们测试一下，在下表中，表头是步长，也就是每次跳多少个整数，而纵向是这个数组可以跳几次（你可以理解为要几条Cache Line），于是表中的任何一项代表了这个数组有多少，而且步长是多少。比如：横轴是 512，纵轴是4，意思是，这个数组有 4*512 = 2048 个长度，访问时按512步长访问，也就是访问其中的这几项：[0, 512, 1024, 1536] 这四项。

示例3

下面是一个二维数组的两种遍历方式，一个逐行遍历，一个是逐列遍历，这两种方式在理论上来说，寻址和计算量都是一样的，执行时间应该也是一样的

示例4

接下来，我们来看一下多核下的性能问题，参看如下的代码。两个线程在操作一个数组的两个不同的元素（无需加锁），线程循环1000万次，做加法操作。在下面的代码中，我高亮了一行，就是p2指针，要么是p[1]，或是 p[30]，理论上来说，无论访问哪两个数组元素，都应该是一样的执行时间

示例5

我们想统计一下一个数组中的奇数个数，但是这个数组太大了，我们希望可以用多线程来完成这个统计。下面的代码中，我们为每一个线程传入一个 id ，然后通过这个 id 来完成对应数组段的统计任务。这样可以加快整个处理速度。

然而，在执行过程中，你会发现，6个线程居然跑不过1个线程。因为根据上面的例子你知道 result[] 这个数组中的数据在一个Cache Line中，所以，所有的线程都会对这个 Cache Line 进行写操作，导致所有的线程都在不断地重新同步 result[] 所在的 Cache Line，所以，导致 6 个线程还跑不过一个线程的结果。这叫 False Sharing

我们把两个程序分别在 1 到 32 个线程上跑一下，得出的结果画一张图如下所示（横轴是线程数，纵轴是完成统的时间，单位是微秒）