浅谈高端CPU Cache Page-Coloring（2）

作者 | 2011-04-17 11:12 | 类型 专题分析 | 44条用户评论 »

Sina WeiboBaiduLinkedInQQGoogle+RedditEvernote分享




系列目录 高端CPU Cache Page Coloring

  1. 浅谈高端CPU Cache Page-Coloring（1）
  2. 浅谈高端CPU Cache Page-Coloring（2）
  3. 浅谈高端CPU Cache Page-Coloring（3）
  4. 浅谈高端CPU Cache Page-Coloring（4）
  5. 浅谈高端CPU Cache Page-Coloring（5）
  6. 浅谈高端CPU Cache Page-Coloring（6）

为了理解Page Coloring，需要把握或者记住下面几点：
× OS的内存管理的基本分配粒度是Page，例如经典的4K大小；
×CPU的Cache管理的基本上分配粒度是基于Way-SET的Cache Line。例如，32bytes。
×大Cache，例如，L2，L3，很大，很大。

在上述３个前提下，如果理解Page　Coloring？

思考了好几天，如何用大白话来说，而非玩学术。玩胶片。

我的理解大概是这样的：

理解一：大宋姐妹一盘棋
如果北京八大胡同的姐妹们和东莞的姐妹们都是我大宋服务业的一盘棋，我们就要一盘棋来考虑，要拉通【注：某司的专门术语。好像意味着互通有无，或者有一个良好的通信Channel】。 因此，不要都往北京的天上人间或者地下人间跑，我们可以定一个政策，南方人就去东莞折腾；北方人就在北京。再整一个成都，西北人都去成都耍。Page Coloring其实就是这个意思。南方人，北方人，西北人就是所谓的识别着色（Coloring）。这样的好处是啥涅？不会导致大家都往成都跑【我的YY呀。没去过。成都的应该好点吧。北京的姐妹们的一口东北口音让人基本上无言以对，情何以堪呀】。

亮点： 相对均匀的分配落脚点的好处是都整体经济拉通有好处。

理解二：不要输在起跑线上
现在凡是都要计划。据说小朋友还没有出身，妈妈们就要开始琢磨上什么亲子班和各种攻略。为了就是让孩子们有个好的落脚点。可怜天下父母心。出身论在我大宋是根深蒂固的。红N代估计从来就看不起贫M代。富K代估计从来都忘了自己的贫K-j的祖先。如果不输在起跑线上？ 就是planning，把自己的孩子往中关村幼儿园整；往深圳的实验小学整。如何整？ Coloring！ 户口，买房子的地点等等。。。。

亮点：人为调整住房和户口【含假离婚（据说最后都变成真离婚）】信息，映射到最好，或者次好的校区。

Coloring的目的就是把一个东西的落脚点，有目的地，设置好，从而获得最大利益。这个设置就是通过在可控的范围内（OS），把物理Page的Page Frame信息调配好，从而最大程度上的利用大Cache。

现在我们来看看CPU的Page和Cache是如何协同工作的。

现在考虑一个L2 Cache，参数如下：
–大小： 2M
–SET/Way： 4 Way SET
–Line: 32 Bytes

这个2M的L2 Cache有多少SET（集合或者组）？

2M/（32 × 4） = (2 ×２^20)/ (2^5 * 2^2)=2^14=16K=16*1024
=10240+6144=16384

这个2M的cache是分成了16384个SET。每个SET里含有和管理4个Cache Line。这个管理算法可以是P-LRU，当然，也可以是王大师的WLRU算法。这个SET里面的替换算法在此不讨论。基本上类似于贵族幼儿园内部的潜规则。例如，送礼多的，老师就照顾多点。或者不送礼的，下个学期突然就让你的孩子out了，被另外一个小replace你们家小孩的名额了。

我们现在来看一个OS层面的Page，4K大小。是如何落在这16384个SET里的。

不失一般性，我们假设这个Physical Page是0×0. 最低端的4K内存。
其地址范围是：０－（４K－１）。

我们来考察其在这个2M Cache中的分布情况。

问题一：　一个Page有多少Cache　Line？
４K／３２＝　２＾７＝１２８。
也就是说每个OS层面分出来的物理页面会占据１２８个CPU层面的Cache　Line。

现在假设我们对这个４K的区域做一个ｍｅｍｓｅｔ（０ｘ０，０，　４＊１０２４）．

显然，在２M　Cache的CPU下，这个４K的内存一定都会被带到Cache中来。

但是如何分布的？

是散落在这１６３８４个SET中的某一个连续的１２８个SET中的。这里的某一个，其实就是第一个１２８个SET。

上述的这段话要绝对的理解清楚。否则下面的图都无法看，和对Page Coloring无法理解。

一个4K大小的物理内存的东西被按照每32字节大小放在了128个不同的SET中

reduced to：

4千个贪官，来自不同的机关单位。每个单位是32个人，排队去天上人间（北方干部），或者去东莞（南方干部），或者去成都（西部干部）。

妈咪是这样处理的：


× 来自同一个机关的干部们（32人一组）都在一个包厢（SET）里。

【妈咪注：每一个包厢其实可以容纳4组（32×4）贪官。但另外3组席位那是为另外贪官队伍准备的。目前，就只放一组进来】

×不同单位的干部们都在相邻的前后左右包厢里。

×4千个贪官整了128个包厢


那么物理页面１是如何在Cache中分布的？

以此类推，第3，4，5个物理页面也都会被分配和跟在后面的Cache SET 中，而不会与前面的物理页面占据的Cache位置相冲突。

Until 第（16386/128=2^14/2^7=2^7=128）个物理页面被分配之后。

换言之，如果我们连续对128个物理页面做memset清0，就会把这个2M的L2 Cache的每个SET中放上一个Cache Line。而且没有任何冲突。

问题就是出在128个物理页面之后的事情。 事情要绕回去，从头来了。

为什么？

系列前一篇 系列下一篇
(12个打分， 平均：4.67 / 5)

工具箱
本文链接 | | 打印此页 | 44条用户评论 »

雁过留声

“浅谈高端CPU Cache Page-Coloring（2）”有44个回复

  1. Will Chie 于 2011-04-17 1:04 下午

    当年辛辛苦苦学的一点知识被首席给大众化了，郁闷，

    不过从首席的文中所学得更深入了，远比之前的粗浅理解深入，之前掌握的太皮毛了，基本只是给memory slab的每个page加了个偏移。

  2. 陈怀临 于 2011-04-17 2:31 下午

    写这种文章，如果没有道义精神支持，倒贴我钱，我也不干。。。伤神。我就要把体系结构，操作系统，这种计算机科学的皇冠上的明珠阐述的大傻们都能明白。。。：-）

    写完这个，我准备再写一个cache prefetch的专题。

    我行走江湖NM年，就没见过除了我，还（敢）用prefetch cache调商用系统的。。。非常subtle。属于春药系列，不能乱用。

  3. hanx 于 2011-04-17 6:38 下午

    嗯，我想问的也是cache prefetch的问题，特别想了解首席实现了prefetch后得到了什么样的性能回报。

    intel sse中扩充了prefetch的指令，之前有team做过一些简单的研究，但感觉大部分时候调测的复杂度太高，代码维护成本太大。

    考虑到现在的cpu cache这么大，有没有可能实现一个叫通用的方案，锁死一部分cache供使用，从而实现一个简化的编程接口。

    另外一条路子是程序在典型场景里面跑出profile后，然后反过来根据profile做优化，甚至实现动态的prefetch，不过目前看到的都是研究小组的成果，商用系统中目前有没有必要引入或目前引入的时机成熟不成熟？

  4. 沙加 于 2011-04-17 7:36 下午

    期待prefetch系列文章

  5. Will Chie 于 2011-04-17 7:38 下午

    首席威武，翘首期待，:D

  6. 陈怀临 于 2011-04-17 8:56 下午

    商用系统用prefetch做调优的条件不成熟。基本上是属于没有办法之后的办法。通常系统可以调的地方很多，还不至于需要玩prefetch。

  7. kevin 于 2011-04-17 9:25 下午

    用了prefetch，这段代码就不能动了
    多用几个prefetch，以后公司想开除你都得掂量掂量了

  8. 理客 于 2011-04-17 9:29 下午

    kevin这话有意思，所以小公司老板经常要自己牢牢掌握know how

  9. julang3 于 2011-04-17 10:04 下午

    期待首席的prefetch,刚在学习体系结构，最近也在折腾这个

  10. francis 于 2011-04-17 11:00 下午

    首席这春秋笔法，微言大义，很强。

  11. 天外有天 于 2011-04-17 11:43 下午

    感觉明白一点了。用自己的语言表达一下：

    有1G的内存，1M的cache。先简化为1way的情况。
    这1G内存不能存在cache的任意位置，
    实际上，是有个映射关系的。
    每个物理的内存单元固定映射在一个cache 单元上（单元就是cache line）.总共有1000个内存单元映射在这个cache 单元上。

    问题来了：
    如果程序申请的内存正好是这1000个内存单元中的两个，然后交错访问，cache等于失效了。

    N-way可以缓解这种事件，但是不能完全解决。

  12. Jeff Zhou 于 2011-04-18 5:16 上午

    楼上的说的问题用N-way就可以很好的解决了，当然，如果你交错访问N+1个内存单元，这个时候就需要在N-way里面来做LRU replace之类的事情。因为有这个问题，所以做一些高性能应用的时候程序员应该关注这个，尽量避免这种情况。

    to hanx
    tilera下(使用vliw的私有指令集)已经引入了基于profile的编译器优化。效果据说还可以，我们倒也没有实际测试过，因为这个本身也是非常的应用相关的。

  13. Alex 于 2011-04-18 8:09 上午

    首席离开HW了，内部人很怀念啊

  14. 陈怀临 于 2011-04-18 8:12 上午

    相濡以沫，不如相忘于江湖。。。。。。我非常珍惜华为众多草根阶层弟兄们都我的厚爱。是你们造就了华为。。。。。

    华为不等于中国。哥哥我先走一步了。。。。。。

  15. 天外有天 于 2011-04-18 9:02 上午

    用N-way就可以很好的解决了
    ———————–

    为何n-way可以很好的解决？
    n-way只是多了资源，如果程序访问的内存所要求的cache超出n-way提供的cache资源，一样存在颠簸的问题。

    等首席讲prefetch的细节。

  16. bill 于 2011-04-18 9:10 上午

    首席的博文博大精深，深入浅出。本以为首席定是个德高望重的业界耆老。前天有幸谋面肯谈，想不到首席是位风华正茂的谦谦君子。

    佩服佩服！

  17. 沙加 于 2011-04-18 9:18 上午

    首席来华为一圈，圈到了很多弯曲的fans。O(∩_∩)O~我本人就从弯曲学到了很多东西。年前就有听到消息说首席要走，一直不敢相信，没想到果真应验了。华为的土壤，暂时来说的确不适合完成首席打造自己的OS的愿望，拿首席经常用的一句话来说，情何以堪啊

  18. 理客 于 2011-04-18 1:00 下午

    其实古今中外谷内谷外，本质是一样的，不能让真正能干活的人在合理的期望期得到回报的团队也好，部门也好，公司也好，一定会不能长期很好的成长的。团队/部门/公司的ZZ一定要控制在合理的范围和程度，如果过广过深，一定会出大问题，可以利用ZZ起事，但不用利用ZZ谋私忘公

  19. Tony 于 2011-04-18 5:46 下午

    就像前面的大牛们说的，Sandy bridge直接把page hash到不同的cache line里面了，理论上来说，各个Line上面的访问次数会比较平均，无冲突了。

    这样我们是否仍然需要Page Color呢？

  20. 知迷不悟 于 2011-04-19 5:52 上午

    哈哈哈，首席离开HW是个好事啊，我也曾经是去过华为的，握手！
    平心而论，华为是一个成功的公司，却不是个伟大的企业。

  21. 一条虫 于 2011-04-19 6:00 上午

    啊。。首席离开H了啊。唉……

  22. cracked 于 2011-04-21 12:45 上午

    其实 首席为什么离开华为，也可以给我们说一说，也好长见识。是17楼说的，无法按首席的意思实现华为嵌入式os吗？在不泄密的情况下，首席可否说说，想听这八卦的肯定很多。

  23. 冬瓜头 于 2011-04-21 1:29 上午

    @bill：首席的博文博大精深，深入浅出。本以为首席定是个德高望重的业界耆老。前天有幸谋面肯谈，想不到首席是位风华正茂的谦谦君子。

    看来首席也是个闷骚男：）

  24. 理客 于 2011-04-21 3:03 上午

    用意淫好一些，在红楼里解释还是对男人好色的最高评价

  25. 陈怀临 于 2011-04-21 7:10 上午

    我可不闷骚。我对自己的喜欢通常不隐瞒呀。

    好色看事不看心。知孝读心不读事。

    这说的是：

    如果看心，天下男人都不是好东西。所以，要看事。
    如果看事，天下没有一个人是孝子。所以，要看心。

  26. 理客 于 2011-04-21 7:43 上午

    社会总是有矛盾和悖论让人纠结。
    比如拯救大兵瑞恩，如果要牺牲1千万人，还要不要救？
    比如富翁财产万亿，捐出千万救众多生命，而穷人财产百元，全部捐献，却不能救一人，又如何能比较？
    所以李敖为不让台湾慰安妇领取鬼子的封口钱，自捐+拍卖，奉上同样金钱给慰安妇，无需再领鬼子侮辱，真男人也

  27. 菠-_-萝 于 2011-04-21 9:54 下午

    首席写的真好，详细又生动，读着都挺温馨的

  28. 陈怀临 于 2011-04-22 6:39 上午

    科普和毁人不倦是我强项。。。
    这个周末写（3）
    现在天天写xcode和mysql程序。比较忙。

  29. 胡不才 于 2011-04-22 10:19 上午

    看来首席也在趟social这趟浑水啊。

  30. Will Chie 于 2011-04-22 12:43 下午

    又看了一遍，还是看首席文章过瘾，不像某些只来顾宣传一毛不拔的文章，简直浪费时间。

  31. bill 于 2011-04-22 5:18 下午

    “现在天天写xcode和mysql程序。比较忙”

    怎么跟我搞的一样的名堂？ 忘了问首席下不下棋。下的话可以抽空杀2局。

  32. 刘刚 于 2011-05-31 11:55 下午

    首席的文章太过瘾了，图文并茂啊

  33. zrz 于 2011-08-23 6:49 下午

    每个SET其实有4个CACHE line , 你这边的举例只是其中的1路的sets被占满

  34. 谢婧雅 于 2011-08-28 10:16 下午

    TO 陈老师：
    我用过prefetch做过优化……而且在前后注释写着，不许改……
    不知道那段代码现在是什么样子。

  35. pb 于 2011-08-29 1:06 上午

    4 way与memory的burst有关系吗？

  36. sailing 于 2011-08-31 6:29 下午

    Sandy Bridge的Hash是对LLC的Slice，Coloring对L2 Cache有用，对L1 Cache不行的，因为SNB的L1 Cache相对较小，没有包厢。

    学生上学，导致我从城里开到城里堵了一路车，晕。

  37. sailing 于 2011-08-31 6:33 下午

    又看了看弯曲，首席又开始膨胀了。没有人敢用Prefetch？Linux中Intel的10Ge网卡就在用着。
    前一阵子和LAD一工程师聊天，此人对Linux实现很愤怒，“多好的设计，全被这帮实现的人毁了，许多好功能还没有实现”。
    很好奇有问了问写这些程序的，“什么烂设计，根本不知道操作系统有多难”。

    大家都觉得自己的工作不容易，别人的简单。工程师的通病。

  38. westermann 于 2011-08-31 8:05 下午

    linux的设计和实现不都是同一拨人在搞么？

  39. 一条虫 于 2011-08-31 8:59 下午

    同问。

  40. sailing 于 2011-08-31 10:16 下午

    我是指做e1000e网卡IC designer和写Linux驱动程序的两拨人。一个是Silicon Design层面，一个是Linux实现层面。

  41. 人大门西 于 2011-09-01 8:16 上午

    做silicon design的境界一般只能达到function，而写系统的境界则是architecture。很多IC的功能根本没法在操作系统中发挥作用，比如intel网卡的DCA就是个摆设，让IC的人去定义网卡软件功能通常是闭门造车。

  42. 一条虫 于 2011-09-01 9:06 上午

    我觉得很难区分architecture是IC还是系统的功劳。

  43. Ma Ling 于 2011-09-01 10:03 下午

    指令的 prefetch确实不错，但是数据的prefetch spcjbb, tpcc, 确实没什么用处，amd 还建议关掉 data prefetch 当运行的是服务器程序。

  44. Ma Ling 于 2011-09-02 10:03 下午

    量化方法已经明确说明当cache way 增加到8个以上，cache miss from conflict 明显看不到多少，目前linux kernel 已经不再用染色的方法了。现在我们主要在努力解决cache latency, replacement, off-chip bus trafic 的问题。