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

作者 | 2011-04-30 18:47 | 类型 专题分析, 科技普及 | 40条用户评论 »

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 Cache的Page Coloring相对而言算OS和【或】系统方面比较高深一点的话题。涉及的技术其实不多，但涉及的概念比较广和杂乱。

为什么我竭尽全力的试图用大白话来把这个专题谈清楚呢？

市场原因如下：

1. 我个人Believe，基于x86或者高端NPU，具备大cache的通信设备会对中低端市场造成倾销似的冲击。 Software Based系统会从接入一直顶到Edge。
2. 我国大量企业缺乏FPGA和ASIC的能力。利用通用CPU，迅速的切入市场，同时可以利用Linux丰富的3rd party的应用。可以迅速的占领市场份额。
3. 对Software Based系统，能把系统做好做精，cache的把握是very important, if not most important.

技术原因如下：
1. 在OS和体系结构的各种经典书籍中，基本上对Cache Page Coloring涉及不多。或者没有提及。同学们在这方面的知识结构需要略微弥补。
2. 对Page Coloring的理解，类似与造大飞机一样：造大飞机重要；但更重要的是，可以拉通一系列产业。通过Page Coloring，可以使得同学们弥补和温习OS和体系结构的许多概念和知识，从而使得大家能够成长。
3. 我自己在看了许多文献之后，有时也是很迷糊。也单独请教过Xiaodong Zhang。感觉Page Coloring的文献都写的比较学术化，处于风花雪月的小圈子里。而且感觉在学校里的教授和博士生，基本上缺乏实战经验，写的东西有点虚。但随着高端CPU的不断应用，工程技术人员，特别是，公司里的系统骨干人员，有必要了解和even掌握。

从这节开始，我会试图对page coloring开始做定性和定量的分析（Qualitative and Quantitative Analysis of Cache Page Coloring)。

要掌握Page Coloring，首先大家要从概念补起。

下面是我个人阅读和参阅的一些OS和体系结构的书籍：
×Unix Systems for Modern Architectures -Curt Schimmel
×Unix Internals -Uresh Vahalia
×Computer Architecture-A Quantitative Approach -Hennessy & Patterson
×The Art of Multiprocessor Programming -Maurice Herlihy et. al.,
×The Design and Impl of the FreeBSD OS -Marshall Kirk et. al.,
×Computer Systems-A Programmer’s Perspective – Randal Bryant et. al.,
×Understanding the Linux Kernel – Daniel Bovet, et. al.,

上述书籍基本上涵盖了OS和体系结构的概念，知识和相关技能。但基本上对大Cache的Page Coloring是篇幅很少, if not ZERO。

这里面的原因有三：

1. Page Coloring只能在大Cache的情况下才能出现，例如L2，L3 Cache。对L1 Cache基本上没有任何意义。
2. Page Coloring是一个OS与体系结构相碰撞时，而产生的问题。是一个介于工程和学术之间的问题。
3. 作者要么来自OS方面，要么是来自体系结构方面。很难有时间和精力在这个交叉的专题方面专门讨论。

为什么Page Coloring容易迷糊人？

结果如下：基本上所有的教科书没有introduce一个重要的概念给学生。从而使得，学生的知识结构出现了一个hole。而这个hole一旦在开始的阶段没有被introduce，后来看Page Coloring的文章，就总是迷糊。

这个被教科书忽略或者miss掉的概念就是：Cache Bin。

Cache Bin是一个逻辑概念。不是CPU Cache机制里的任何实现；也不是OS内部数据结构里的任何Struct_。

Cache Bin是一个当OS或者以后要谈的应用程序利用大Cache的时候，做映射时，产生的一个Cache SET的集合。

每一个Cache Bin其实就是一个所谓的颜色（Color）。

下面我们试图对Cache Bin做一些略微学术化的定义。

Cache Bin： 在基于SET/Way的高端CPU中，给定（Given）一块连续的OS或者应用程序分配的物理内存，会按照一定的映射算法，落在（Fall Into）一块连续的Cache SET中。这个连续的Cache SET 集合，我们称之为：Cache Bin。

用类BNF范式，我们可以这样来定义：

[Cache Bin]::={Cache SET}^M(对于给定大小的物理Page，例如4K，其Cache Bin所Cover的Cache SET的M是固定的，例如，上节所case study的128个SET）

[Cache SET]::={Cache Way}^N (N means N-Way Cache）

在OS和CPU Cache之间引入一个Cache Bin的概念之后，对OS和CPU Cache的整体关系图，就与经典的OS和体系结构有了一点区别。这个区别是一个逻辑上的理解的区别，而非任何物理的实现：

上述体系结构图基本上是把握高端CPU Page Coloring的总图。从物理内存上面，就是OS的Memory Management的Allocator或者应用程序，例如，通信系统的Data Path的内存管理了。然后通过一个个的mapping，最后落得某一个包厢（Set)的长凳子（Way）上。

这样OS与CPU之间的语义就存在了一定程度的Aware了。

下图所示为在上几节中，given 一个2M的4Way SET-Assoc L2 Cache，4K的物理Page的case study中，Cache Bin的分布情况illustration：

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

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

雁过留声

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

  1. 中医码农 于 2011-04-30 7:32 下午

    首席你又是党委书记，又是小姐妈咪的，看了有点晕。。。

  2. 陈怀临 于 2011-04-30 8:24 下午

    贤弟真土：-）。从计算理论的角度，只要是Decidable的问题，党委书记与妈咪一定存在这一个P时间的映射关系。。。

  3. 陈怀临 于 2011-04-30 9:20 下午

    愚兄我改了一下。从新画图。保持比喻的一致性。把party的书记换成妈咪了。真是的，其实不一样嘛。。。我没看出啥区别。

  4. Amy 于 2011-05-01 7:15 上午

    呵呵，首席又发page coloring文章了，继续关注中…
    根据您的理解，现有OS和体系结构间没完全处理好，所以存在OS处理的页面经映射到Cache时会导致缓存行利用冲突（首席Case里面0，128,256,384等填充完Set 0后，之后的访问落在Set 0都会出现不命中），利用page coloring方法通过设置颜色位控制物理页面在Cache Set中存储，尽量让冲突的物理页面存储在连续的Cache Set中。瞎理解的，哈哈…
    如果按照page coloring方法，当Set 0又被填满时，不是又产生了miss，不解？
    每次看首席文章，总有收获，感谢…

  5. multithreaded 于 2011-05-01 11:08 上午

    >1. 我个人Believe，基于x86或者高端NPU，具备大cache的通信设备会对中低端市场造成倾销似的冲击。 Software Based系统会从接入一直顶到Edge。

    只限于企业网络上的应用。 在接入层功耗是一个大问题。

  6. 陈怀临 于 2011-05-01 11:24 上午

    多线程，我已经是个体户了。。。哪天一起吃个饭。syncup一下。

    另外，您老一身武艺。要应该多写写才是。否则，难道还真带（得）走不成？：-）

    合肥出来的人不要忘了方校长的教诲嘛：–）

  7. multithreaded 于 2011-05-01 6:37 下午

    写科普我不在行！以后自己的英文科技文章被录取了，可以到这里来晒一晒，搭一个连接工业界和学术界的桥梁，让弟兄们砸一砸，出出气：-）

    最后这句话：“cache的把握是very important, if not most important”应该加重语气：

    cache的把握是最重要的 （THE MOST IMPORTANT）！！

  8. 陈怀临 于 2011-05-01 7:23 下午

    谢谢多贝勒的支持。。。期待ing。您老应该是对大CPU大Cache的世界级的高手了。一定要多多发力才是。否则可惜了，您老的才华对贡献给了大辽了。。。

  9. 胡不才 于 2011-05-02 6:45 下午

    首席啊，在Intel的Software Developer’s Manual 3A中第11章关于cache的控制，好像没有提到你说的coloring，但这将是融合中出现的趋势，是这样理解吗？

  10. 陈怀临 于 2011-05-02 7:12 下午

    coloring不是CPU的概念和机制；也不（单纯）是OS的概念和机制。是当大CPU，大Cache出现的时候，出现的一个荒岛。。。

  11. kernelchina 于 2011-05-02 7:14 下午

    cache对通用系统的意义有多大？比如家用电脑？感觉这个对服务器或者是嵌入式系统有很大的意义，因为应用比较少，而且是长期驻留内存的。

  12. multithreaded 于 2011-05-02 7:27 下午

    CACHE对任何要算的快的问题都有用！可以这么说：一个程序的的性能取决于CACHE的MISS trate有多低而不是指令的执行个数有多少！

    家用电脑上的应用一般没有性能优化的需要，所以看不出来cache有多有用。但当你用netbook时（Intel ATOM）， 立刻可以感觉到CACHE小的感觉：-（

  13. 陈怀临 于 2011-05-02 7:29 下午

    具体benchmark不详。Windows和FreeBSD都已经考虑Coloring。Linus拒绝了，因为从模拟的效果看，slab mm的功效 ==coloring。

    我会慢慢谈到。。。

  14. 经常路过 于 2011-05-02 9:43 下午

    首席，这个图是不是Windows附件的画图弄的？

  15. wu xingbo 于 2011-05-03 12:27 上午

    Cahce Coloring的概念和page是另一种微妙的关系吧.
    coloring想解决的问题是多个领导都被按jj大小安排上一个小姐, 而其他对应罕见jj-size的小姐则没客人的问题.
    而面向page方面的优化是这样的:为了给客户办理准嫖证明, 每个店都来一张就太麻烦了, 所以按区办理, 办了一张海淀的准嫖证就可以在海淀随便开了, 顾客为了省事, 应该好好用这张来之不易的证,尽量在海淀消费, 不要浪费时间在每个区每个县都办一张证.
    cache问题的产生和解决之道与page的关系甚少,这些是我认为的.

  16. hh 于 2011-05-03 5:15 上午

    楼上精辟，哈哈

  17. 陈怀临 于 2011-05-03 6:44 上午

    韦小宝太有才了。哪个部队的？

  18. 我才是缓存的专家 于 2011-05-03 7:29 上午

    哈哈，

    我们考虑冲突的时候，不仅要考虑大小，还要考虑时间。

    90%的，时间都很短。

    所以，冲突的情况并不像想象的严重。

  19. Leenzb 于 2011-05-03 7:56 上午

    >1. 我个人Believe，基于x86或者高端NPU，具备大cache的通信设备会对中低端市场造成倾销似的冲击。 Software Based系统会从接入一直顶到Edge。

    在嵌入式领域工作甚久，对大Cache很不感冒。大Cache是电老虎，还占用宝贵的die size。Cache机制出现在几十年前，当时人们基本上只关注性能，而很少考虑尺寸和功耗。所以，档我们用21世纪的苛刻眼光来看时，Cache难免存在低效的问题。
    我猜Cache是硬件工程师的杰作，所以没有充分利用软件特性。Cache的命中就是一个撞大运的过程，为了增加几率，只有不断增加尺寸。但是，每一个多余的Cache单元都是要耗电的啊！这是个恶性循环。
    将来的Cache或许需要向智能化发展，以达到减少尺寸并提高命中率的目的。
    例如：memset(addr, size=4K, xx)；由于4K内存分布在128个Cache Line上（假设Cache Line是128比特的），因此正常运行时，系统会连续产生128次Cache Miss。但实际上，我们在编译阶段就已经知道我们要访问的是连续的4K内存，所以聪明的Cache模块在调入第一个Cache Line后，不用等来自CPU的下一条写指令就可以提前调第二个Cache Line，依次操作，可以大大减少Cache Miss的次数。

  20. multithreaded 于 2011-05-03 8:49 上午

    简单的预取硬件早就做了，用不着用户担心：-）
    比如要想加速 memcpy， 只预取下一条CACHE LINE是远远不够的，因为硬件早就帮你做了！

    难一点的问题是如何预取 Linked List：-（

  21. 我才是缓存的专家 于 2011-05-03 9:19 上午

    高级的缓存有一个 Initial Memory Setting的指令。直接就在缓存中开一片为0的区域出来，根本不需要去DRAM。

    预取是很失败的想法。 本来就很挤的地方，再多叫一些无关的人来凑热闹。

  22. coder 于 2011-05-03 5:00 下午

    *Cache 不是电老虎。跟Core logic 比， Cache logic 狠省电

    *Modern processors adopts aggreasive hardware auto prefetching. 但是 Prefetching 如果不能 reduce latency, 就是浪费空间了。

    *Zeroing the cacheline without fetching 跟是不是高级缓存没有关系，是有的体系结构有这样的指令，PPc有，Azul 的机器也有, 是ISA设计人员的trade-off

    *想加速 memset, 可以用 non-temporal instructions, high memory bandwidth utulization, 又不污染 cache, 问题是temporal locality 可能很差。

  23. shuyong 于 2011-05-03 10:03 下午

    CACHE对软件的性能还是很有影响的。我测试了几个CORTEX-A8的平台，发现在memcpy的测试中，一是CACHE SIZE，特别是L1 CACHE SIZE，二是读写CACHE的数据宽度(64-bit or 128-bit)，对性能影响很大。

    有几个有趣的现象：
    1) 当copy block size < L1 size，memcpy的速度比memset的要快。
    2) 随着CPU内部的优化，硬件级的预取效果是越来越好，而采用软件预取指令越来越显得画蛇添足。
    3) 软件主动影响CACHE的填充，很容易就造成低效率。

    测试结果我已经放在弯曲的BLOG里了。等弯曲审查通过后大家看吧。

    从ARM的发展看，有加大CACHE SIZE的趋势。不过都是L2 CACHE。到CORTEX-A9，L1 CACHE还是I:32k/D:32K。samsung exynos4210 L2 CACHE = 1MB。过两天测测OMAP4430 & exynos4210看看有什么样的性能。

    偏向实时的嵌入式应用，大多会关闭CACHE，因为要确定的行为。而开启CACHE会带来性能的波动。CORTEX-M系列即没有ARM指令，也没有CACHE，那是省钱又省电。CORTEX-R系列有可能有L1 CACHE。看来实时应用还是无法回避CACHE性能的诱惑。

  24. 瞎扯 于 2011-05-03 11:21 下午

    一些基于CORTEX-M的SoC直接on-chip memory了，cache不cache无所谓。

  25. kevint 于 2011-05-04 12:44 上午

    @ 23

    1.不明白为什么拿memcpy测cache性能。。。
    2.memcpy比memset快，逻辑上讲不通，可以看看IPC
    3.L1运行core speed，L2运行bus speed。不是L1做不大，而是把L1做大和把L2做大，性价比后者要好得多。

    @ 24

    你的观点在TSV火热的时候流行过一段时间
    but
    L1 cache重要的作用就是简化流水线，如果没有L1，去L2最最快也要20+cycle，什么onchip memory更慢。pipeline需要巨大的reassembly buffer去处理on the fly request，才能填补流水线的空白。

    so，一些奇门歪道的设计，仅限于低端处理器，主频一般不超过500Mhz，IO intensive，并不代表未来的方向

  26. shuyong 于 2011-05-04 2:06 上午

    不是用memcpy测cache性能，而是测各种memcpy实现的时候发现cache对memcpy性能影响很大。

    memcpy是一种无回溯的应用，其实对cache很不利。至于< L1 SIZE的条件下，memcpy比memset要快，我也想不通。所有的memcpy & memset的代码都是open source的，等着设计CPU的人解释吧。

  27. 瞎扯 于 2011-05-04 4:02 上午

    25, 我说的是一些基于CORTEX-M的小SoC。 on-chip memory只要single cycle就能取指，根本就不需要cache。

  28. 瞎扯 于 2011-05-04 4:07 上午

    26，有没有disassemble看看memcpy和memset的汇编？

  29. shuyong 于 2011-05-04 4:35 上午

    memcpy & memset的源代码，全是open source的。汇编代码，纯手工制作，不用反编译。:-)

  30. 采莲南塘秋 于 2011-05-04 6:06 上午

    弯曲就是好，评论不用事先注册。我决定换个ID:)

    1.RE: *Cache 不是电老虎。跟Core logic 比， Cache logic 狠省电
    那得看谁的core，Intel的core做得极其复杂，超深流水+高主频，自然耗电。有一次他们来向我们推销一款芯片，说是既强大又省电，只要40几瓦。唉，超预算数倍…… 我很怀疑Intel在嵌入式领域的前景
    2M的cache内含2M*8*6=96M个Transistor，单静态功耗就不是小数目了。
    到了多核时代，还有头疼的Cache一致性问题；到了众核时代……

    2.硬件预取
    通过硬件预取来提高Cache命中率的方法依然是靠运气，最终还是要增大Cache

    3.RE：难一点的问题是如何预取 Linked List：-（
    例如：
    ;LinkList * searchList(LinkList *head, int key) {
    ; for (LinkList *p = head; p && p->data != key; p = p->next);
    ; return p;
    ;}
    编译器可以知道：
    ; a.当访问p之后，很可能马上要访问p->next；
    ; b.指针p只有key和next两个字段会被使用
    所以，一个智能的Cache模块应该做到当p的值发生变化时，
    ; 1.调入p->key和p->next；
    ; 2.根据需要，提前调入p->next->key和p->next->next，甚至可以多调入几级；
    显然现有的CPU做不到这些，从编译器到处理器都需要改变。

  31. dahanlinux 于 2011-05-05 4:46 上午

    关注首席的文章。

  32. 我才是缓存的专家 于 2011-05-05 11:35 上午

    楼上算少了。

    2MB的缓存，有Data和Tag，还都带ECC。

    你那个晶体管数目最少还要多30%。

  33. 采莲南塘秋 于 2011-05-06 7:52 上午

    多谢楼上的指正。

    再补充一下，缓存不一定要带ECC，可以只带奇偶校验。当校验失败时，直接作为Cache Miss处理，这样可以稍微节省点。

  34. kevint 于 2011-05-06 11:03 下午

    to 33

    再给你指正一下吧，奇偶校验2n bit错检查不出来。CPU直接machine check或者bus error。

    SUN以前范过一次这种错误，服务器销量小，一年卖个10几w片，结果出一次错误，就再也没有人敢买你的东西了。

    从那以后，没人敢做没ECC的cache了

  35. 王去非 于 2011-05-07 1:00 上午

    最终目标灭掉intel。

  36. joke 于 2011-05-07 1:27 上午

    干脆连那美克星一起灭掉好了!

  37. jhs 于 2011-05-07 9:34 上午

    求大师嘴下留情，美国人民虽然不是什么好鸟，但也不都是坏鸟，至少我华人后裔就是好人，看在人性的份上，灭门前还请三思，给美国人民留一条生路胜造七级浮屠呀

  38. 我才是缓存的专家 于 2011-05-11 8:38 上午

    智商贴。

  39. Amy 于 2011-05-19 5:30 上午

    问下首席，
    如果”color bit”数目小于”cache line bit数”，是不是OS就不可以控制cache行为了？而是，必须要”color bit”数目大于”cache line” bit数？

  40. lisa 于 2012-02-05 7:40 下午

    感谢！说的很清楚！