浅谈高端CPU Cache Page-Coloring（3）
作者 陈怀临 | 2011-04-24 14:49 | 类型 专题分析 | 35条用户评论 »
系列目录 高端CPU Cache Page Coloring上节中我们讲到，如果对内存的0-127（总共128）个物理页面做内存清零（memset）的话，其在cache中的分布是正好每一个SET（包厢）里，放入了一个cache line（包厢里的长凳子。每个凳子上32个人。每个包厢是4个凳子：4 Way）。 我们先谈结论。 结论： 第128th物理页面会与第0个页面占据同样的Cache Sets。 * 第ith物理页面会与第（128+i）th个物理页面在Cache中占据同样的Cache Sets。 * 第ith物理页面会与第（128*j+i)th个物理页面中Cache中占据同样的Cache Sets。（i,j = 0,1,2….)
× 占据同样的Cache Sets，会导致潜在的Cache冲突，替换。例如，当一个N-Way的Set，如果所有的Way（长凳子）都被坐满的时候，必须按照某种算法，把倒霉蛋踢出局。 × 我们把i, 128×j+i(i，j=0,1,2,3…)等属于同一个Cache Sets映射的物理页面，称为具备同样颜色（Color）的物理页面。 ×请注意，每一个4K的物理页面上映射到127个连续的SET中。是Cache SetS。学术上，这个相应的容纳这个4KPage的Cache SET的集合，叫做 Cache Bin。 我们讨论的这个Cache是一个L2 Cache，参数如下： 16K的SET。意味着2^14。 换言之，需要物理地址贡献出14个bit，来做为定位其落在哪个Cache Set. 从上图我们知道，bit 5-18是用来选择属于哪个SET的。 × 由于一个物理Page的5-11是可变的【4K的物理Page】。因此这就是为什么上节所解释的一个物理Page一定是占据了连续的128个SET中的某一个cache line： 11-5+1 = 7. 2^7= 128. 很显然，物理页面i与物理页面i+128*j的低7位数完全一致的。换言之，bit 12-18是完全一致的。 例如， 128×j – 0= j(128-0) = j * (0b 1 0000000); 由此可见对于任何一个物理页面i，对应的128+i页面，128×2+i，128×j+i页面的bit 12-18是相同的。 这意味着什么？ 请注意，Cache的SET的选择就是通过5-18bit来决定的。 如果两个物理页面的12-18bit是一样的， 这意味着： 这些页面的4K内容都会落在相同的128个SET中（5-11位决定的）。这些页面属于一个相同的颜色（Color）。 下图所示是当4个具有同样颜色的物理页面都被读到Cache中后，Cache的SET和Way的情况–“属于你的”包厢的4条凳子都全部坐满。 这里面， “属于你的”这个词非常重要。即使妈咪有别的包厢，但如果不属于你，你是不行的。有钱都不灵。“属于你的”其实就是你的颜色；你的颜色决定了你的出路和你的地位； 这有点类似与当年，你的阶级成分决定了你许多的将来。。。。。。由于出身论被枪毙的遇罗克同学是一个英雄。。。。。。
| |
 (6个打分， 平均：5.00 / 5) |
雁过留声
“浅谈高端CPU Cache Page-Coloring（3）”有35个回复
下一篇，我要上公式了，做量化分析了。
看了《Computer Systems A Programmer’s Perspective_2nd》再来看首席的文章，增加了不少领悟。我觉得首席的文章深入浅出的程度跟Bryant的书有得一比，而书里面主要对direct-mapped cache进行分析，适合入门者了解cache原理，而首席的文章对set associative cache进行分析，同时结合OS的page概念，更具实战价值。。。首席你真的可以考虑出一本系统架构和软件的书，广大大宋民工必定受益匪浅。
目前我理解page frame到cache的映射还是比较直接的。32位地址的中端部分5-18bit对应set index，高端部分19-31bit对应set里面的tag，因此0-127个page中任意两个line都不能存在于同一个cache set之中，因为他们的tag是一样的，而set index必定不一样。这样的{m,t,s,b}分配方式可以让cache hit or miss直接快捷，如果任何一个set里面都没有不超过1个line，则对任一line通过set index也就是5-18 bit和cache line的valid bit就可以判断hit or miss，否则，则进一步判断tag。而page的coler通过对内存地址进行取模也可以直接得到。
目前还不太明白page coloring需要软件做什么？需要保留额外的数据结构来trace和balance内存分配吗？
还是首席的货比较硬
按首席的话说，就是减少各位大爷在同一时间点某一个小妹的概率
不知道page coloring 和linux的slab coloring有什么区别？
我的理解是，对于首席里面的例子，如果CPU在某段时间里面频繁的交替访问页0,128,256,384,512五个页的0-31字节处的数据，那么从第5次访问开始，每次都会miss。因为偏移量相同，这五个页的起始数据都放在SET 0里面，而实际上cache的其他set很可能是空的。可行的做法是以bit[18-12]作为color值，color offset 为一个cache Line的字节，在每个页的相同数据结构前偏移color*line个字节。这样上面5个页的原0-31字节处的数据结构现在的偏移分别是0,32,64,96,0，全部load进cache后分别位于set 0,1,2,3,0,不会冲突，提高了cache的性能。
pf同学基本上全部get points了。基础非常不错。
我会在以后谈 Page Coloring与Slab Coloring的等价问题。
受教了，虽然很多看不懂。
首席，我的那篇软货您老啥时候给审批一下啊
8楼，有时候太硬了，会一碰就碎的，软一点也有好处。
期待量化中
这样上面5个页的原0-31字节处的数据结构现在的偏移分别是0,32,64,96,0，全部load进cache后分别位于set 0,1,2,3,0,不会冲突，提高了cache的性能
—————————————
如何确定那些页有可能冲突？
结合到软件，
我们可以知道那些数据是同时访问的。
如何确定这些数据在那些页里面？（全局的，kmalloc的，vmalloc的）。
如何确定这些页同时访问到相同的地址偏移，从而造成cache不够哪？
To冬瓜头：你如果遇到的是不欣赏你的人，并且如果不幸不是首席这样的君子，你就不好玩了
冬瓜头，我今天早晨6点多就帮助您老编辑您的文章。。。后来give up。原因如下：
1。 您简单的copy paste，把大量的link embedded在文字里。
2。 您自己preview一下。看看效果。就知道以后该如何做了。
3。 静下心来是一种磨练。共勉。例如，我写的那些略带算法分析的文章。写到最后，半天头痛。但要么不写，要么try best。
塞塞。
实在对不住了，这个word express，实在不会玩，怎么编辑最后都是那个样，但是又不能一个字一个在重新敲一边，我再搞一搞，搞不好就不发了。
理客，不好玩可以不玩啊，生来不是被人玩的。每个人性格不同，如果都一个所谓完美性格，那是你写出来的代码。
当年一篇文章编辑了20次的飘过:)
刚编辑完，这次应该符合首席要求了，不过可悲的是，我司的安全设备实在是牛的让人咗舌，能自动识别上传太大数据的话，给你禁了，哈哈！只能晚上再搞了。
我来吧。。。你司实在是，唉。。。
我花一个小时整你的文章，基本上是对人类文明进步的犯罪。
首席一个小时写的代码可能会推动GDP大幅增长，罪过罪过。。
问首席个问题，这CPU的2M cahce是如何分布和访问的，也像内存一样吗，set[16384][4]? 内存上连续的4K内存映射到cpu上128个连续的set，但这128个连续的set是物理上并不是连续的？
下面是量化的理解
set[0][0] = 32 bytes 0×0 – 0x1f
set[0][1] = 0×80000 – 0x8001f
set[0][2] = 0×100000 – 0x10001f
set[0][3] = 0×180000 – 0x18001f
set[1][0] = 32 bytes 0×20 – 0x3f
set[1][1] = 0×80020 – 0x8003f
set[1][2] = 0×100020 – 0x10003f
set[1][3] = 0×180020 – 0x18003f
…
set[127][0] = 32 bytes 0xfe0 – 0xfff
set[127][1] = 0x80fe0 – 0x80fff
set[127][2] = 0x100fe0 – 0x100fff
set[127][3] = 0x180fe0 – 0x180fff
0x7f
…
set[16383][0] = 32 bytes 0x7ffe0 – 0x7ffff
set[16383][1] = 0xfffe0 – 0xfffff
set[16383][2] = 0x17ffe0 – 0x17ffff
set[16383][3] = 0x1fffe0 – 0x1fffff
0x3fff
1) windows live writer本来是个很好的工具，但是在弯曲用不起来，首席注册一个测试帐号，用普通用户试一下，看看行不行
2)page color解决什么问题？进程之内的冲突，还是进程之间的冲突？还是两者都有？slab color解决内核里面对象之间的冲突，但是实际效果并没有多好，而且用color的方式解决冲突，在对象很多的情况下，由于cache容量有限，冲突是不可避免的。能不能在l2就把code和data分开，我现在还没有一个感觉，就是code和data之间的冲突有多大？
In general(不同的vendor有不同的设计），cache mem是SRAM。physically分为两块： Tag SRAM和Data SRAM。各种管一滩。
SET，不管是V还是P Index。一个local add bus，直接打到Tag和Data SRAM。同时结果都出来。。。然后一通胡比较。。。
反正最后就落到AND， OR等电路级别上了。。。。。。
关注了近几期陈首席的关于Page Coloring解析，深感受用，比看英文文献了解得透彻多了（不是别人写的不好），感谢首席。
谢谢。学术的东西一定可以从生活中找到映射。。。
Page coloring的paper都写的比较晦涩。
写好技术文章，尤其是书，是需要有相应的素质、功夫和训练的，能写得上好的人不多
to 5/6楼：“0,128,256,384,512五个页的0-31字节处的数据“ 如果这样做coloring,是否会在另外一种模式遇到同样的问题？
不得不提一下Octeon的cache算法，他是有一种模式是对所有物理比特做hash再来去计算set index. 这样，从硬件上就解决了cache coloring 的问题。
首席好，经常看您写的文章，注意到网友pf关于page color留言 “用bit[18-12]作为color值，color offset 为一个cache Line的字节，在每个页的相同数据结构前偏移color*line个字节。这样上面5个页的原0-31字节处的数据结构现在的偏移分别是0,32,64,96,0，全部load进cache后分别位于set 0,1,2,3,0,不会冲突”，有点不是很明白，bit 18-12共7bit表示为 00（color吗？） 00000（color offset吗？），即color*line字节.这里有点晕。
12-18就是所谓的color bit了。别再在color bit再做细分了。
这里面关键的关键是：12-18是OS可以操控的了。【属于OS 层面Page Frame的bits】。
Thus，OS可以影响cache的行为了。。。
首席有个问题，如果加一个2M的cache给应用程序直接用，那么OS的优化是不是就不那么重要了？
看应用，2M的cache，即使只用指令，也支持不了多大应用程序。intel类通用CPU属于计算型，对数据cache要求低，而通讯设备里业务处理用的处理器，是一定要集成大的数据cache
首席讲得有意思，看起来也过瘾。有个问题没明白，请教一下：
进了包厢以后，怎么知道哪个凳子是自己的？
很简单的道理。如果你在包厢里，占了凳子。但相比其他哥哥，你不办事。。。，不消费，妈眯一定是赶你走。。。，留下有动作的。。。－－LRU算法。
你经常光顾，跟妈咪混个脸熟，妈咪看见你，即使你不消费，也能让你多待一会。。。。。。–WLRU算法。。。不过妈咪累的半死不说，新来的客人可惨了。可能刚进门，还嘿咻的时候就被踢到大街上去了。。。
To 首席，kevin，
哈哈，多谢。这个倒是明白，让我把问题改一下：
现在假设你指挥扫黄，包围了一个包厢，妈咪告诉你县委书记在里面，你如何找到他？进一步讲，如果你就是去抓书记的，这个问题就更准确了嘿
谷哥说，进包厢的时候，书记身上挂了个牌子（31-18bits），写了“我是书记”，是这么个事么？
似乎没有这种场景
一般你问妈咪，书记在不在
妈咪回答
1.不在。今天没来。
2.在，人已经给你抓来了。你自己看着办吧
看来不在工作范围呢，O了，谢啦