与程序员相关的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算法(通过新增一个访问计数器来实现)
这个叫做Set Associativity
举例说明
Intel处理器,L1 Cache有32KB,8-Way组相连,Cache Line是64 Bytes
分组
32KB 的Cache可以分成 32KB / 64 = 512 条 Cache Line
8-Way 的,于是每个Way有 512 / 8 = 64 条 Cache Line
每个Way 就有 64条 * 64B = 4096 Bytes的内存
索引内存地址
Tag: 每条Cache Line 前都有一个独立分配的24bits 来存的tag,其就是内存地址的前24bits
Index:内存地址后续的6个bits,是在这一Way的是Cache Line索引,2^6 = 64 刚好可以索引64条Cache Line
Offset:再往后的6 bits 用于表示在Cache Line里的偏移量
查找
1. 拿到一个内存地址,先拿出中间的6 bits 作为Index,对应每个Way的Cache Line索引
2. 再用Tag,变量每个Way,进行O(n) n=8 次遍历,找到在哪个组中
若2中查找到,则表示命中,否则cache miss
查找命中
说明:
L1 Cahce 可映射36 bits 的内存地址,一共2 ^ 36 = 64GB的内存
当CPU要访问一个内存的时候,通过这个内存中间的6bits 定位是哪个set,通过前24bits定位相应的Cache Line
就想一个Hash Table 的数据结构一样,先是O(1) 的索引,然后进行冲突搜索
因为中间的6bits 决定了同一个set 所以,对于一段连续的内存来说,每隔4096的内存会被存放到同一个组内,导致缓存冲突
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协议
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 来访问一个连续的数组
示例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 个线程上跑一下,得出的结果画一张图如下所示(横轴是线程数,纵轴是完成统的时间,单位是微秒)
延伸阅读
Wikipedia : CPU Cache
经典文章:Gallery of Processor Cache Effects (这篇文章中的测试已经有点过时了,但是这篇文章中所说的那些东西还是非常适用的)
Effective C++作者 Scott Meyers 的演讲 CPU Caches and Why You Care (Youtube,PPT)
美国私立大学Swarthmore的教材 Cache Architecture and Design
经典文章:What Every Programmer Should Know About Memory (这篇文章非常经典,但是开篇太晦涩了,居然告诉你晶体管内的构造,第三章和第六章是重点)
Nonblocking Algorithms and Scalable Multicore Programming
英文版
中文版
Github上的一个代码库 hardware-effects 里面有受CPU影响的程序的演示
Optimizing for instruction caches (Part 1,Part 2, Part 3)
P1
P2
P3
经典数据:Latency Numbers Every Programmer Should Know
关于Java的可以看一下这篇Optimizing Memory Access With CPU Cache 或是 Writing cache-friendly code
Optimizing Memory Access With CPU Cache
Writing cache-friendly code
0 条评论
回复 删除
下一页