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

作者 | 2011-04-11 20:46 | 类型 专题分析 | 60条用户评论 »

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）

现代CPU是越来越狠。x86+PCI-E 3似乎要横扫一切的样子。Tilera等高端CPU也咄咄逼人。RMI 832也似乎在朝着大型CPU的方向靠拢。换言之，经典Server和Desktop CPU与网络CPU在融合，convergence。 你中有我；我中有你。

不久的将来，Software-Based 各种设备，估计顶到Edge的层面，似乎都不奇怪。

但，要把大型CPU用的好，绝非写写胶片，就能搞定。

胶片一分钟；台下N年功。

其中，对大型CPU的大Cache的有效利用是其中重中之重。

这就好比，你忽悠了一个美女到家里，但是美女发现你不能很好的满足她的各种需求【此处省略249字。。。】

观察业界的各种大CPU，最凸显的就是L2，L3 Cache的巨大。而且L3都已经在Die里。

对桌面和服务器系统来说，这些Cache的管理基本上与业务无关。OS基本上全Cover了。

但对于通信系统，必须aware。

为啥涅？

通信系统的Data Path（含数据结构）是非常要求realtime的。是线速要求的关键之处。

友善的Cache命中率可以使得一个系统的性能让人不相信，让人觉得是一个863的成果，或者核高基项目的汇报演出：-）。

那么如何分配数据结构？ 如何Cache Friendly？

有许多方法，但其中一个重要的手筋就是–Page Coloring

Page Coloring方面比较绕人。要搞懂，基本上需要对OS和CPU都明白。要能真正的敢用，估计江湖上也就陈首席一个人了。。。。。。要用好，目前没看见过。 Panabit系统估计在Cache方面用的比较好。但是否用了Page Coloring目前看不出来。

什么是Page Coloring？

首先不要上来就去看学术文章。

最好的学术一定是来源于生活。例如，陈首席的多核与公厕的悖论原理。

× Page Coloring其实就是要让OS在内存管理方面Cache Aware。Cache感知。
× OS VM对物理页面的分配机制与CPU Cache的管理机制不是和谐的。
×Page Coloring的前提是这个CPU必须是Physically Indexed。

下面通过一张精选的图示，来看看什么是Page Coloring。

在大多数OS的VM管理中，当分配一个页面Page[Note: 一定要牢牢记住，Page的概念是OS的概念，而非CPU的概念。这个问题出现混淆，请买豆腐撞死】，通常是4K一个页面。这里是否是4K不重要，就是一个happen to 4K而已。

如果是4K，如何分配的？

一定是0-11 bits是Offset（2^12=4K）。31-12bits是Page Number。这就是上图的所谓Page Frame。

那么请问，这些一个个Physical的Page是如何落入Cache的手里的？

这个问题的等价问题是（用洋文说是，reduced to）：

Cache是如何Allocate，Hit的？

现代CPU基本上都是Set-Associative的管理方式。

我们来简单的看看一个大Cache的Set-Associative的管理方式是如何与经典OS的Page管理方式脱节的。

这种脱节是导致了Page Coloring算法出现的唯一动机。

算法的胶片是要解决问题的。否则就是YY（意淫）。

例如一个1M的Cache Line大小为32Byte的8Way Set Cache。

8Way的意思是：一个SET（集合）有8个Cache Line。

那么这个CPU能有多少个SET？

1M/(32*8) = 2^20/2^8 = 2^12 = 4K = 4096

这个CPU有4096个SET。每个SET是8个Cache Line。

一个问题涌现了： 如何使得OS层面上物理页面（Page）的分配能够比较均匀的落在CPU层面上的SET中。从而可以避免自相残杀和互相挤兑？

上述命题可以reduce成为这样一个命题：

一个基于4K为页面大小的OS层面的Page分配机制与一个基于32 byte Cache Line大型的SET－Assoc分配机制的Cache管理基本上没有任何逻辑关系？

但这种关系的弱映射是至关重要的。

我们如何来解决？如何把一个OS与底层的CPU在语义上来紧耦合？

最关键的地方出现了。

就是上述我辛勤画出的这个x的值。x的位置。

系列下一篇
(36个打分， 平均：4.22 / 5)

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

雁过留声

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

  1. 陈怀临 于 2011-04-11 8:55 下午

    Page Coloring要是不绕人，我都不信。难怪Linux不要（FreeBSD adopt了）。我算是对OS和CPU的概念都比较清晰的了，但每次都要从新走一遍。经常自己绕晕了。

    最关键的就是那个x 大于等于OS的Page Frame的第12bit的时候，Page Coloring就出现了。

    抓住这个x值，就好理解了。我下一篇把Y写清楚。

    这个x就等同于我以前说的去理解Cisco的CRS交换一样。抓住8个独立的交换平面（Switch Fabric），其他的都是纲举目张。。。

  2. tom 于 2011-04-11 9:08 下午

    我决定直接买豆腐撞死算了

  3. Peter 于 2011-04-11 9:11 下午

    TILERA TILE架构CPU应用的核心也是CACHE。

  4. 张俊杰 于 2011-04-11 9:14 下午

    坐等下文。

  5. coder 于 2011-04-11 9:40 下午

    人家现在都 hash 了，不让你控制了…

  6. Mine 于 2011-04-11 9:55 下午

    nice~

  7. kevin 于 2011-04-11 11:18 下午

    4K = 4098。这是为什么。。。首席你伤不起啊。。。

  8. 菠-_-萝 于 2011-04-12 12:01 上午

    嗯，好好学习下。最近接触了点皮毛，有丁点体会。

  9. 陈怀临 于 2011-04-12 6:58 上午

    真不给力。这种文章还没有拿全A。显然出现过3，4分的投票。我相信一定是哪位弟兄的鼠标突然出现了抖动造成的。

    早上6点多就醒了。在被子里推算page coloring的算法。

    不看任何文献，能把page coloring算法推算出来，弟兄们自己试一下。。。。。。

    1. x < = 12
    2. x >= 12

  10. 陈怀临 于 2011-04-12 7:02 上午

    >4K = 4098。这是为什么。。。首席你伤不起啊。。。

    FIXED. 最近白天写xcode iphone程序；突然整CPU的东西，脑袋有点需要调整。

    感觉写应用程序类似与休息。量大但不伤神。基本上不须动脑子。感觉是大傻都能写app。

  11. lofeng 于 2011-04-12 7:54 上午

    坐下好好学习~

  12. 理客 于 2011-04-12 8:08 上午

    首席会围棋？

  13. 白云蓝天 于 2011-04-12 8:23 上午

    4M的cache，为嘛用1M去除，笔误？

  14. Lucifer 于 2011-04-12 9:55 上午

    哈，是，sandy bridge将cache line按源地址hash到不同的cache slide当中去了……

  15. Lucifer 于 2011-04-12 9:57 上午

    不过今年的idf讲的都是老东西，完全没啥好听的东西

  16. james 于 2011-04-12 3:17 下午

    page coloring 就是解决了一个aliasing的问题
    如果你是Cache是virtually addressed，就没有这个问题了。当年Qualify的题啊

  17. kevin 于 2011-04-12 5:02 下午

    楼上搞错了吧
    你说的是cache shadow吧。早年mips virtual index physical tag的cache有问题

    page color优化性能用的，两码事

  18. 陈怀临 于 2011-04-12 5:35 下午

    建议james同学应该中午去买豆腐。。。

  19. 胡不才 于 2011-04-12 5:59 下午

    首席你写啥iphone程序呢？俺想写个wordexpress阅读器。

  20. picktracy 于 2011-04-12 7:16 下午

    提供bare metal或zero overhead linux环境的平台，流行用hash处理cache么？

    snb把ring换成mesh，x86高频缩核版Tile，呃

  21. hanx 于 2011-04-12 7:40 下午

    彻底没看懂，投一个1分，一个5分，强烈要求科普

  22. comcat 于 2011-04-12 8:16 下午

    cache 的背景部分我来帮首席补充吧

  23. 陈怀临 于 2011-04-12 9:30 下午

    没良心的，你不能打1分呀。等我下一篇把x的意义解释完毕，你就觉得简单了。我一定会讲的必教授们清楚，简单。

    当然， Page Coloring确实需要一点基础。我不能学冬瓜，为了讲Fibre Channel，从什么磁盘头，扇区，开始讲吧：－）

  24. boblee2000 于 2011-04-12 11:29 下午

    unaliased和aliased各有优缺，视情况而定

  25. roman 于 2011-04-13 6:29 上午

    刚开始看到关键地方，结果就over了。
    有点像小学时候老师给大家讲难题，关键时刻总要喝口水。

  26. roman 于 2011-04-13 6:30 上午

    另外Cache Line是啥，都还给组成原理的老师了。。。

  27. kernelchina 于 2011-04-14 4:06 上午

    Application aware cache是不是给application带来了更多的限制，如果是cache aware memory management还行，否则就太复杂了，用起来可能不是那么爽。

  28. 雅各 于 2011-04-14 4:59 上午

    看到首席的文章里面有“手筋”出现
    难道首席也爱下围棋？
    棋力如何，八卦一下。。。。。。。。

  29. 胡不才 于 2011-04-14 12:39 下午

    整个嵌入式ARMCPU的例子，
    cat /proc/cpuinfo
    Processor : ARMv6-compatible processor rev 7 (v6l)
    BogoMIPS : 299.00
    Features : swp half thumb fastmult edsp java
    CPU implementer : 0×41
    CPU architecture: 7
    CPU variant : 0×0
    CPU part : 0xb76
    CPU revision : 7
    Cache type : write-back
    Cache clean : cp15 c7 ops
    Cache lockdown : format C
    Cache format : Harvard
    I size : 32768
    I assoc : 4
    I line length : 32
    I sets : 256
    D size : 32768
    D assoc : 4
    D line length : 32
    D sets : 256

    那么assoc 就是N-Way，line length就是cache line。不知然否？

  30. bill 于 2011-04-14 1:58 下午

    首席下围棋，还写app？和我臭味相投呀。后天要不要手谈2局？我可是业余有蛋棋手。

  31. yunhaid 于 2011-04-14 6:23 下午

    首席谈的根本是CPU里的Cache设计,小问一下，首席研究哪些开源的MIPS-CPU 实现？

  32. 沙加 于 2011-04-14 7:47 下午

    基本上明白首席讲的东西了，其实现在虚拟化和nano-kernel领域，一些公司已经将这个理念运用起来了，之前我觉得这思路挺好，只是不知道还有个名字叫做coloring。这样做确实在性能上有很大的好处，可也如kernelchina说的，应用上会有一些限制。所以，还是看具体应用场景了。另外，楼上有的提到了cache aliasing跟这东西不是很一致

  33. 陈怀临 于 2011-04-14 8:06 下午

    我浅尝过OpenRISC…

  34. Puppy 于 2011-04-25 12:12 上午

    以前有个映像，mips R4000有个类别的cpu在cache映射时有使用虚拟地址索引，物理地址tag的现象，后果…

  35. multithreaded 于 2011-05-10 6:04 下午

    建议加以一句话： L1　ｃａｃｈｅ一般是　ｖｉｒｔｕａｌ　ｉｎｄｅｘｅｄ，　Ｌ２／Ｌ３　ｃａｃｈｅ　是ｐｈｙｓｉｃａｌ　ａｄｄｒｅｓｓ　ｉｎｄｅｘｅｄ．　Ｐａｇｅ　Ｃｏｌｏｒｉｎｇ是针对Ｌ２／Ｌ３　大缓存的．

  36. 陈首席的同事 于 2011-09-23 7:09 上午

    首席：Page的概念是OS的概念，而非CPU的概念。能不解释一下啊
    我的理解：每个cpu的MMU一节都会讲page和cache，page理所当然应该是cup的概念啊。比如IA 32，所支持的页大小就4k和2M，这些都是CPU的特性，怎么是os的概念呢
    对于OS的内存管理来说，最小管理单位是page，而对cpu来说，内存管理，最小管理单位是cacheline。你是否是这个意思

  37. 陈首席的另外一个同事 于 2011-09-23 9:06 上午

    首席及各位弯曲大牛：我其实也搞不懂首席说“page的概念是OS的概念”这句话是什么意思。
    买豆腐撞死也要死得瞑目才行哦。
    cpu都是定义好page大小的。OS只是知道cpu的page大小后，才用page做内存管理的。对OS来说，是被动的啊，是被动接受page这个概念的啊，怎么首席说page是OS的概念呢？
    哎，豆腐已经买了很多块了，没搞清楚这个问题，一直舍不得撞死啊。 （今天看到上面有同学有同样的疑惑，终于找到可以一起撞豆腐的人了 呵呵）

  38. kevint 于 2011-09-23 1:24 下午

    看看linux mm， 一个OS要支持n个processor，page从1k-nk.所以逻辑page与物理page是有区别的

    另外，现代os（学术上）基本上已经抽象成与硬件无关的鸟玩意了。

  39. 陈首席的同事 于 2011-09-23 6:35 下午

    1. 从CPU看来：page是cpu的概念，页大小是固定一个或者几个大小。可以让os来按照cpu的页来做地址映射和属性的设置。
    2. 从os来看，page就是os的概念了，考虑到各种cpu的page的差异，vmmu模块就可以实现cpu无关的页的管理

    所以我觉得，page既是cup的概念也是os的概念，还请大牛小牛斧正

  40. awei 于 2011-09-23 8:05 下午

    我是一个CPU文盲。 但是从Linux内核的角度(照顾一下我,只从OS的角度讨论该问题):

    是不是早期UNIX操作系统发展初期. 当时的CPU Cache时是以虚拟地址做HASH. 所以UNIX进程地址空间布局规划时 要考虑 这个CACHE 着色的影响.

    而现在的 CACAHE 都以物理地址为HASH,只有TLB才以虚拟地址做HASH.

    所以现在的这个CACHE 着色概念 对操作系统的设计是不是无所谓????

  41. 陈怀临 于 2011-09-23 8:10 下午

    小同事门都来了。。。：－）。我其实想了一个下午如何回答了。。。还真不好回答。我再想想。。。

  42. duolv 于 2011-09-23 9:04 下午

    如果没记错的话，早年（1960s）的机器是用分段机制的，然后把整个段换进换出，后来为了解决外碎片的问题，发明了demand paging。同一时期为了解决应用程序代码地址relocate的问题，发明了virtual memory。这都是OS实现提出来的，后来为了performance，CPU做了硬件来加速这两个过程。所以从历史来看，page确实是个os的概念。

  43. 陈首席的另外一个同事 于 2011-09-23 9:13 下午

    看了以上大牛的分析，感觉是说“OS的Page是OS的概念，不是CPU的概念；CPU的Page是CPU的概念，不是OS的概念，…《步步惊心》的Page是《步步惊心》的概念，不是OS的概念，也不是CPU的概念”，如果是这样，那倒是很容易能理解，并且觉得首席也不用在原文中这么强调了，呵呵 。 但难道这就是首席原文要表达的意思？ 没搞懂，继续买豆腐。

    To 首席： 谁叫你来H逛了一圈，H可是有十万人啊，突然冒出来很多自称你同事的人是很正常的，呵呵

  44. 陈怀临 于 2011-09-23 9:37 下午

    duolv说的有道理。我下午也是在这个思路上试图给出解释。。。。我一定要给出个先有鸡蛋还是先有母鸡的解释。否则，这些小同事门要把豆腐店整脱销。。。

  45. awei 于 2011-09-23 10:08 下午

    谁是谁的概念这个问题,讨论起来没有意义.
    就好比CACHE这个东西.
    (1) APP开发者只要能写出时间,空间局部性优秀的代码提高CACHE 命中率和降低TLB MISS 就很OK了.
    (2) 内核开发人员不但要写出高速缓存命中高的代码,还需要知道 在什么时候刷CACHE,什么时候刷TLB,而且要少刷
    (3) 至于 首席描述的CACHE着色的问题,可能只有操作系统设计者才会考虑.
    (4) 至于处理器设计人员在想什么,我这个文盲就不知道了.

    所以对于首席来说，将OS,CPU,编译器这些 硬件和软件分开来说,本来就有落入下乘!!!

    所以首席 不好给我们解释! 呵呵.

  46. duolv 于 2011-09-23 10:36 下午

    感谢首席指点～～个人认为首席强调page是个os的概念，应该是为了说明cpu在设计cache的时候，是不考虑有关page的问题的。反过来做系统编程的人以page为粒度使用内存的话，不容易考虑cache的问题，造成某些page由于映射到同一个cache bin，互相拼杀，影响性能。沟通这两者的就是page coloring，其精髓就是引入了cache bin这个概念，目的就是为了在以page为粒度的内存使用时，减少conflict miss（见Mark Hill的分类）。个人感觉理解这个是第一步，难的应该是怎么用起来，估计这就是首席超出一般人的功力所在之处，而Professor Xiaodong Zhang的功力估计可以到宗师级了。

  47. 陈首席的另外一个同事 于 2011-09-23 10:41 下午

    to awei: 所以我们需要首席出来拉通，一定要拉通 呵呵

  48. 陈怀临 于 2011-09-23 10:42 下午

    ummm, 这个duolv很不错。。。确实理解的相当透彻。 希望是个女弟子。。。

  49. 陈怀临 于 2011-09-23 10:43 下午

    “一定要拉通”， 我听见这个词汇就头痛！！！！一定是2012实验室的家伙！！！

  50. 陈首席的另外一个同事 于 2011-09-23 10:53 下午

    其实“拉通”这个词汇在H使用得没这么频繁的，一般都是开会时要引起领导注意时才这么说的（领导喜欢听“拉通”，准备搞个复读机送给领导）。倒是看见首席文章中多次出现“拉通”（虽然首席讨厌“拉通”），但我为了引起首席注意，也只有写写“拉通”了，呵呵。

  51. duolv 于 2011-09-23 10:54 下午

    个人觉得page coloring的第一个难点在于怎么了解程序的memory access pattern，然后tweak this pattern or page allocation rule so that “no two pages with the color are in use at the same time”。对于通用OS和一般的应用程序来说，这个access pattern太难弄了。第二个是page coloring是针对physical address的，OS kernel里好说，在OS之上的应用程序只知道virtual address，所以还需要virtual coloring的转换。因此如果系统和应用本身就在一起的，譬如通信系统fast path上的代码，用起来应该容易些，否则估计就得寄希望与首席的核武器application aware OS了。

  52. 陈怀临 于 2011-09-23 10:57 下午

    duolv, 你是哪个门派的？？？感觉是个隐姓埋名的江湖高手，而且对我在OS方面的理解经过长期潜伏观察。。。多帮帮我，你看看那些小家伙们，一个个求知欲很好的。就是可惜没有好老师。。。

  53. 陈怀临 于 2011-09-23 11:06 下午

    弟兄们，问一个问题，我这些黄色的coloring的文章，有在我司的h3ms上了嘛？反应如何？

  54. duolv 于 2011-09-23 11:08 下午

    感谢首席抬爱，其实我只是个学生，一直对kernel有浓厚兴趣，最近偶然读了篇Xiaodong Zhang大牛的文章而已…

  55. awei 于 2011-09-23 11:10 下午

    其实我也是首席的同事.
    只不过首席不在美研搞OS了.
    瞬间就觉得在HW 玩Linux就没什么意思了. 年底不给配股就滚蛋了

  56. 陈首席的另外一个同事 于 2011-09-23 11:33 下午

    唉，我上h3ms时 一般都是直奔LGZ的去了，没有去搜首席的，主要是觉得要看首席的，直接来弯曲就行了。

  57. 陈首席的同事 于 2011-09-24 6:39 上午

    感谢duolv，居然还是隐居在某学校的大牛啊，我国系统软件有救了，再次跪地拜谢duolv

  58. 理客 于 2011-09-24 9:39 上午

    语言如武器，本无罪无善恶，善恶在人不在词语本身，再好的词在恶人嘴里也可以变成伤人恶语，再坏的词在好人嘴里也能暖人，如因某些人的恶用而使本来好好的词汇为人厌恶，语言和武器何辜啊要蒙此不白大冤？
    胸怀坦荡者，常口无遮拦，首席曾以普朗克在爱因斯坦生日的信劝慰小弟，甚为感怀，而今首席何须为些许wording小事挂怀。
    人生受大辱者，各有各的屈辱，也不是很多人会有这种经历，但受辱后的结果，也各异，有愤而变态，揭竿而起，刀枪扫射的；有独自忧郁，觅死不寻活的，有碌碌终生，幽怨而终的，有大彻大悟，奋起为山的，如周公周易，司马史记，或现代一点的新东方。
    首席智慧，痛批HW，未必就是小乘，笔笔点到华为痛处，倘若有一点能让HW改变，也是HW大幸，中华大幸，首席秉菩萨心，执刀斧笔，“十年以后当思我，举国若狂欲语谁？”古有袁崇焕，后有梁启超，当代马寅初、黄万里、顾准、遇罗克… 此乃大乘

    无论HW还是TG，体制内的高层，都是大聪明人，其实什么都知道，但做不做，要上看头顶乌纱，下望屁股板凳，时机到时，寻炮手炮灰，或自制炮手炮灰，自然炮响发兵，至于能否凯旋，是天地人三才而定，纵神人也难预测。有时人为刀俎，我为鱼肉，牛人无数，我等草根，何须为皇帝多虑

  59. westermann 于 2011-09-25 1:11 上午

    软件访问Memory的pattern能比较清楚的把握的除了电信领域的fastpath之外还有哪些？编解码、加解密？

  60. ULCC 于 2011-10-27 6:28 下午

    最近正好看了zhang xiaodong教授的文章。他们整了个GPL的库： User Level Cache Controller： http://jason.cse.ohio-state.edu/