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

作者 | 2011-05-08 17:58 | 类型 专题分析 | 18条用户评论 »

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）

上几节中，笔者试图介绍并强调了Cache Bin在理解大CPU大Cache中Cache Coloring的关键作用。读者最关键要理解的是： Cache Bin是当OS或者应用程序分配数据结构时，最后映射Cache这个层面中出现的一个“逻辑”概念，而非CPU中存在一个类似的的电路【Cache对SET中TAG和内容的寻找，是具体的电路的，通过一个Local Bus寻址。】

上图所示的就是两个层面的映射图。

在Cache中，这个x的位置或者值取决与Cache的大小。

在上几节中，这个x的值是18.

为什么？
“
现在考虑一个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
”
一个cache line是32byte的cache有2^14个SET,意味着：需要14个bit来贡献给CPU的local bus电路来做寻址。

大家知道，0-4bit是32bytes cache line的offset。所以，贡献的bit是从5开始的。

因此， x-5+1=14–》x=19-1=18.

换言之，一个32位的物理地址的5-18是SET的bits。

在上图的第一个部分是一个物理页面的分解图。0-11是4K的offset。 5-31是Page Frame.

现在把Cache的分解图平移上去，我们会发现一个（x-12+1）的红色区域。

这个红色区域就是：Color Bits。或者说，Cache Bin Bits。再或者说，决定了上节所描绘的一个4K的物理页面会去那个Cache Bin。

同学们，这个时候要非常注意了：Page　Frame是OS或者应用程序在做物理内存分配时可以控制的。

换言之：OS和/或应用程序可以控制Color Bits，或者Cache Bin，从而把一个物理内存，有意思的（Intentionally) 布局。

这类似与，中央或者机关的部长可以指派手下的小部长或者经理们去外研所当个钦差大臣。喜欢的去美国；不喜欢的去古巴。或者反之。总之，权力就是春药。

也也类似于，妈咪看见一个大款来了，或者公安局长来了，一定是去西厢。好好伺候。如果是个煤老板；让他去东厢。应付一下算了。

总之，有了Cache Bin，就预备了权力，具备了预算，有了权力，就可以调配了。

下面我们来做一些case study：
当x=18的时候，18-12+1=7。
这就是本文中的例子的情况。系统有2^7=128 Cache Bin。
当x=19的时候，显然是256个Cache Bin。

x=19是什么意思？

如果仍然是一个4Way和32Byte的Cache，其意味着是一个4M的Cache。

依次类推，

当x=20的时候，是一个4Way/32byte的8M Cache。系统有9个color bit，有2^（20-12+1）=512个Cache Bin区域。
当x=21的时候，是一个4Way/32byte的16M Cache。系统有10个color bit，有2^（21-12+1）=1024个Cache Bin区域。
当x=22的时候，是一个4Way/32byte的32M Cache。系统有11个color bit，有2^（22-12+1）=2048个Cache Bin区域。

同学们这时会问一个问题了。。。

陈首席你现在，up to now，讲的都是经典的4K Page。这已经out of date了。。。

现代操作系统和CPU都已经支持大页面（Big Page）的allocation了。

那么Page Coloring或者Cache Coloring还适合嘛？

Yes，kids。

其实数学就是一个抽象。学术就是玩符号。

我们把12这个fixed的value变成y。

我们就得到了下面这张General的图：

在这个通用模型下，

Number of Color/Bin Bits

b= (x-y+1).

Number of  Bins

BIN = 2^B , if b>=0;

BIN = 0 , if b<0;


例如，如果一个操作系统或者应用程序分配的物理页面上512K。其y的值就是18.

下面来做一些定量讨论：

如果系统还是我们文章中例子的2M Cache。其x是18.
(18-18+1)=1.
这意味这什么？ 这意味着，一个2M的cache在OS或者应用程序的512K的页面分配机制下，cache其实就是被拆成了两个Bin。（2^1=2)

任何两个512K的物理页面或者数据结构，一不小心就在一个Bin里。

512K的数据结构在大型通信系统里比比皆是。

有多少人想过，两个512K的数据结构有可能是在互相残杀？？

例如，如果一个操作系统或者应用程序分配的物理页面上1M。其y的值就是20.

如果系统还是我们文章中例子的2M Cache。其x是18.
（x-y+1）=(18-20+1)=-1.
这意味这什么？ 这意味着，一个2M的cache在OS或者应用程序的1M的页面分配机制下，cache bin其实已经失效。就是一个bin了。

大家随便踩了。 OS或者应用程序脱离对Cache Friendly的任何控制。

换言之，如果想通过应用程序或者OS对Cache能够进行干涉，要确保：

x>=y.

从而，（x-y+1）>=1.

从而 2^(x-y+1)>=2.

从而确保系统中至少存在2个Cache Bin区域。

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

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

雁过留声

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

  1. 陈怀临 于 2011-05-08 6:02 下午

    写了1个小时。就这么对着键盘现敲和画图。。。当然，脑子里在除草的时候，先构思了如何忽悠。。。

  2. kernelchina 于 2011-05-08 7:10 下午

    学习中，有几个问题
    1)Page coloring是尽量减少分配给进程的page有冲突，这会导致物理页面不连续，如果应用程序有使用连续物理页面的要求，怎么办？
    2)Page coloring是基于page，而SLAB是基于对象（小于一个页面或者大于一个页面），SLAB通过一个简单的移位就实现了，这两者有什么优劣？
    3)Page coloring和SLAB color结合起来用行不行？

  3. 吴朱华 于 2011-05-08 7:12 下午

    收藏，有空再深入学习:)

  4. Puppy 于 2011-05-08 8:24 下午

    谢谢，明白了。
    感觉2楼的kernelchina 的第一个问题相当于pagesize增大的情况。
    SLAB忘了，回去看看。

  5. pf 于 2011-05-09 12:06 上午

    一个小笔误，第二张图的注(x-12+1)没改过来

    对2楼的第一个问题。我的理解是OS关注的是整体的性能，即OS只要保证页面的分配比较均匀地落在各个COLOR上即可。

  6. wangsec 于 2011-05-09 7:00 上午

    首席，发个帖子审核周期太长了吧。
    每个帖子你都审核，您日理万机，岂不是效率偏低。

  7. 陈怀临 于 2011-05-09 8:17 上午

    5： fix 了
    6： 发了。

  8. multithreaded 于 2011-05-10 6:50 下午

    〉换言之，如果想通过应用程序或者OS对Cache能够进行干涉，要确保：
    〉x>=y.

    如果只想通过应用程序来控制Ｃａｃｈｅ，　可以让　Ｙ〉〉Ｘ。

    比如Ｙ＝１ＧＢ的Ｈｕｇｅｐａｇｅ　（Ｉｎｔｅｌ　Ｓａｎｄｙ　Ｂｒｉｄｇｅ）．这样你想干吗就干吗　：－）

  9. xx 于 2011-05-10 9:37 下午

    如果ＡＰＰ对硬件的直接控制，如何保证其它ＡＰＰ的安全？

  10. deltali 于 2011-05-11 9:05 下午

    例如，如果一个操作系统或者应用程序分配的物理页面上512K。其y的值就是18

    首席这个时候y值应该是19吧

  11. xxchu 于 2011-05-22 1:09 上午

    如果Cache只有1M，但程序中又确实需要使用512K的数据结构，怎么办呢?

  12. multithreaded 于 2011-05-22 8:23 上午

    512K的数据都会在1M的cache里面，你担心啥？

  13. Amy 于 2011-05-24 7:26 下午

    问下首席，页面颜色怎么定义？
    看到网上有这样定义的页面颜色的，不是很理解，
    #define Color_of_page(page) ((page >> PAGE_SHIFT)% get_num_colors())，页面物理地址向右偏移PAGE_SHIFT位，再对颜色数目求余，不是很理解？

  14. 陈怀临 于 2011-05-25 9:34 下午

    这就比较细了。。。

    我们来解剖一下Linux的这块代码吧：

    #define get_num_colours() (262144 >> PAGE_SHIFT)

    陈怀临： 262144右移12个bit=64.表示系统是6个color bit。2^6=64.

    #define COLOR_OF_PAGE(page) (page >> PAGE_SHIFT)% get_num_colours
    陈怀临： 这是一个宏，拿一个具体的Page Frame作为输入参数，与64做余。得到的就是最后的6个bit的value。color bit的value就取出来了。

    从上面，我们还可以推算出，这个case的cache大小。
    例如，

    12+6=18.
    说明，这个cache set有18-5+1=14个bit。

    系统有2^14 x 2^5(cache line) = 2^19

    512K的一个L2 cache：–）

  15. 陈怀临 于 2011-05-25 9:37 下午

    弟兄们一定要注意： 忘掉Linux，或者各种blah blah的细节。把概念把握住。

    例如，我刚才也是当场拿了一张纸，现推算的。但只要概念在脑子里，就什么都可以推出来了。

    我记得我有一次对Cisco CRS突然糊涂了。但我牢牢把握住独立交换平面的概念。结果，我把所有的东西，都可以推算出来。

  16. 三千大千世界 于 2011-05-29 6:48 上午

    抽象，抽象，透过现象看到了本质。拜读了！如果如果N way的这个N的值大一点的话，是否也就不容易发生踩踏了？

  17. oizys 于 2011-05-29 6:19 下午

    其实首席在第三篇就可以把这个概念引出来的,感觉绕了一圈又绕回来了。

  18. Alfnoso 于 2011-12-22 11:34 下午

    oizys所言甚是啊..有点绕,感觉光看文章不够啊,评论里面的东西也很助于理解