技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 由原子操作引起的关于Cache的讨论

由原子操作引起的关于Cache的讨论

浏览:2905次  出处信息

最近MPI集群有用户抛出这样一个问题,当MLR算法或PLSA算法与PLDA同时运行在某个节点时,MLR的效率会降低二十倍,PLSA的效率也会下降非常厉害,而与其它的算法重合时,即使两个算法的程序都可以所有CPU吃满,效率也未必会下降如此厉害,用户怀疑是我的PLDA代码设计的问题,这个问题也引起了大家比较激烈的讨论。

   大家对于PLDA的质疑源自于我引入了原子操作共享了一个大矩阵,而用户理解的是PLDA的原子操作过于频繁,频繁地锁住内存总线导致运行在同一节点上的其它任务性能退化严重,这里面其实是存在一个误区的,首先看看我实现原子操作的方法:

#define atomic_incl(v) __asm__ __volatile__("lock incl %0;":"=m"(v))

   使用lock指令前缀,实现原子操作很常用的方法,而大家质疑的也正是这个lock前缀,我查过Intel的手册,在PentiumPro之前是的CPU使用lock前缀确实是需要对总线加锁的,这种情况对于性能的影响是非常大的,而新的CPU设计都采用了writeback的内存访问方式,使用lock前缀时,CPU的行为不再是去锁住内存总线,而是cache line级别的lock,我一直是这样理解的,在讨论的时候专用计算组的大牛长仁指出,锁cache的概念是不存在的,这和我理解的确实不一样,而且我查了Intel手册和相关的官方文档,里面对于lock前缀的介绍都用到了cache lock这样的说法,而lock前缀实现原子操作的原理也确实是通过类似对cache line加锁来实现的,后来我又和长仁请教了下,他告诉我其实cache上没有lock的功能,硬件实现上cache不能实现lock,其实是通过cache协议来实现的,声称为cache lock是方便软件开发人员理解。

   我们线上的CPU都是Nehalem微架构的,在这些CPU上绝大多数情况下lock prefix是不会尝试锁总线的,Intel手册里面也提到了有些特殊情况下会访问总线,一种情况是对一些不能被cache的内存访问,比如一些memory-map的IO设备,另外一种情况就是指令的操作跨越了两个cache line,这两种情况在我们的环境下都是不会发生的。

   关于CPU的cache要补充的是物理CPU之间不会共享任何级别的cache,而CPU的每个Core都有自己的L1 Cache,它们之间共享更高级别的Cache,每个Core的不同线程之间是共享L1 Cache的,但不同的线程有自己独立的寄存器,从这个角度上来说同一个节点上让两个任务干扰最小的办法就是通过cgroup把不同的任务绑定到不同的物理CPU上,这样相互之间的干扰最小,这样相互之间就没有共享的Cache了。

   说到lock prefix就接着说下CPU的Cache一致性协议吧,经典的Cache一致性协议叫MESI,对应于Cache的四个状态: Modified, Exclusive, Shared, Invalid,后来基于MESI还演化出一些新的协议,比如AMD的MOESI,AMD我没了解过,就不瞎说了,Intel Core i7演化出MESIF,F代表Forward,F的引入应该是出于性能的考虑,它是基于S基础之上的,当某Cache的状态是F的时候,其它人再读取这块数据F就可以直接把数据传给他,然后这个新的Cache变成F,旧的F变成S,我的理解是这个事情就是由QPI来做的,了解不多,不敢再多说了哈。

   在标准的MESI中,当数据读到Cache中来时,并且只有一个Cache持有这份数据而且数据与内存中一致,这时Cache的状态是Exclusive,另一个Cache也请求这份数据时,Cache由Exclusive变为Shared,这时两份Cache和内存中仍然一致,当其中一份Cache被修改时,就会有一个RFO(Request For Ownership)广播把其它的Cache标记为Invalid,而对于处于Modified状态和Exclusive状态的Cache而言当前的Core对其都是可写的,因为这个Core拥有这个Cache的Ownership,当Cache处于Modified状态时,它会监听其它Core的读操作,如有发生,那就会把Cache回写然后再置为Shared状态,同样,Exclusive状态的Cache也会监听其它Core的读操作,如有发生则直接转为Shared状态。

   加lock prefix的操作都是Read for ownership transaction,也就是带有写意图的读操作,这时候便会触发RFO,导致其它Core上的Cache失效。

   再回过头来说PLDA,最初为了防止对共享内存的加锁,所有线程都维护一块独立的大内存,这个开销是非常大的,以至于由于机器内存大小的限制,导致只能启动很少的线程,大部分CPU都处在空闲状态,引入原子操作后将这块内存共享起来,内存占用量下来后可以启动更多的线程把所有的CPU跑满,虽然频繁地使用原子锁也有相当大的开销,但比起能同时利用所有的CPU这个开销就微不足道了。

   乱七八糟说了一通,不知道有没有说错的地方,希望路过的专家不吝指正。

建议继续学习:

  1. Linus:为何对象引用计数必须是原子的    (阅读:11448)
  2. Buffer和cache的区别是什么?    (阅读:6823)
  3. 谈冷热数据    (阅读:5732)
  4. 前端要给力之:原子,与原子联结的友类、友函数    (阅读:5312)
  5. Linux操作系统中内存buffer和cache的区别    (阅读:5305)
  6. 学习:一个并发的Cache    (阅读:4968)
  7. 关于Linux的文件系统cache    (阅读:4773)
  8. Twitter架构图(cache篇)    (阅读:4719)
  9. 详解MyISAM Key Cache(前篇)    (阅读:4064)
  10. 7个示例科普CPU Cache    (阅读:4112)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1