《浅谈高端CPUCachePage-Coloring》由会员分享，可在线阅读，更多相关《浅谈高端CPUCachePage-Coloring（25页珍藏版）》请在金锄头文库上搜索。
1、 浅浅谈谈高高端端CPU Cache Page-Coloring作作者者：陈陈怀怀临临 前前言言：本文通过读者们比较熟悉的妈咪和包厢场景，阐述了高端CPU和大Cache结构中的一个比较略微高深的工程话题Cache Coloring。高端通信系统设计和实践中，对Cache和性能的把握是至关重要的。希望这篇文章对大宋的读者，特别是熟悉妈咪的读者有所帮助。世界上的再高深的技术和理论都可以在现实生活中找到映射。这就是所谓的：得其意；忘其形。方为做学问之最高境界了。OS和体系结构的关系是：OS是形而上；体系结构是形而下。一个高手对这两面都必须有相当得修养，缺一不可。希望这篇文章能起到抛美女引客人的目的
2、，使得读者们能够在业余时间去体验生活，阅读相关资料。提高自己的各方面的能力。浅浅谈谈高高端端CPU的的Cache Coloring（1）现代CPU是越来越狠。x86+PCI-E 3似乎要横扫一切的样子。Tilera等高端CPU也咄咄逼人。RMI 832也似乎在朝着大型CPU的方向靠拢。换言之，经典Server和Desktop CPU与网络CPU在融合，convergence。 你中有我；我中有你。不久的将来，Software-Based 各种设备，估计顶到Edge的层面，似乎都不奇怪。但，要把大型CPU用的好，绝非写写胶片，就能搞定。胶片一分钟；台下N年功。其中，对大型CPU的大Cache的有
3、效利用是其中重中之重。这就好比，你忽悠了一个美女到家里，但是美女发现你不能很好的满足她的各种需求【此处省略249字。】观察业界的各种大CPU，最凸显的就是L2，L3 Cache的巨大。而且L3都已经在Die里。对桌面和服务器系统来说，这些Cache的管理基本上与业务无关。OS基本上全Cover了。但对于通信系统，必须aware。为啥涅？通信系统的Data Path（含数据结构）是非常要求realtime的。是线速要求的关键之处。友善的Cache命中率可以使得一个系统的性能让人不相信，让人觉得是一个863的成果，或者核高基项目的汇报演出：-）。那么如何分配数据结构？ 如何Cache Friend
4、ly？有许多方法，但其中一个重要的手筋就是Page ColoringPage Coloring方面比较绕人。要搞懂，基本上需要对OS和CPU都明白。要能真正的敢用，估计江湖上也就陈首席一个人了。要用好，目前没看见 过。 Panabit系统估计在Cache方面用的比较好。但是否用了Page Coloring目前看不出来。什么是Page Coloring？首先不要上来就去看学术文章。最好的学术一定是来源于生活。例如，陈首席的多核与公厕的悖论原理。 Page Coloring其其实实就就是是要要让让OS在在内内存存管管理理方方面面Cache Aware。Cache感感知知。 OS VM对对物物理理页
5、页面面的的分分配配机机制制与与CPU Cache的的管管理理机机制制不不是是和和谐谐的的。Page Coloring的的前前提提是是这这个个CPU必必须须是是Physically Indexed。下面通过一张精选的图示，来看看什么是Page Coloring。在大多数OS的VM管理中，当分配一个页面PageNote: 一定要牢牢记住，Page的概念是OS的概念，而非CPU的概念。这个问题出现混淆，请买豆腐撞死】，通常是4K一个页面。这里是否是4K不重要，就是一个happen to 4K而已。如果是4K，如何分配的？一定是0-11 bits是Offset（212=4K）。31-12bits是Pa
6、ge 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 Ca
7、che。8Way的意思是：一个SET（集合）有8个Cache Line。那么这个CPU能有多少个SET？ 1M/(32*8) = 220/28 = 212 = 4K = 4096 这个CPU有4096个SET。每个SET是8个Cache Line。一个问题涌现了： 如何使得OS层面上物理页面（Page）的分配能够比较均匀的落在CPU层面上的SET中。从而可以避免自相残杀和互相挤兑？上述命题可以reduce成为这样一个命题：一一个个基基于于4K为为页页面面大大小小的的OS层层面面的的Page分分配配机机制制与与一一个个基基于于32 byte Cache Line大大型型的的SETAssoc分分配
8、配机机制制的的Cache管管理理基基本本上上没没有有任任何何逻逻辑辑关关系系？但但这这种种关关系系的的弱弱映映射射是是至至关关重重要要的的。我我们们如如何何来来解解决决？如如何何把把一一个个OS与与底底层层的的CPU在在语语义义上上来来紧紧耦耦合合？最关键的地方出现了。就是上述我辛勤画出的这个x的值。x的位置。浅浅谈谈高高端端CPU的的Cache Coloring（2）为了理解Page Coloring，需要把握或者记住下面几点： OS的的内内存存管管理理的的基基本本分分配配粒粒度度是是Page，例例如如经经典典的的4K大大小小；CPU的的Cache管管理理的的基基本本上上分分配配粒粒度度是是
9、基基于于Way-SET的的Cache Line。例例如如，32bytes。大大Cache，例例如如，L2，L3，很很大大，很很大大。在上述个前提下，如果理解Page Coloring？思考了好几天，如何用大白话来说，而非玩学术。玩胶片。我的理解大概是这样的：理解一：大宋姐妹一盘棋如果北京八大胡同的姐妹们和东莞的姐妹们都是我大宋服务业的一盘棋，我们就要一盘棋来考虑，要拉通【注：某司的专门术语。好像意味着互通有无，或者有一个 良好的通信Channel】。 因此，不要都往北京的天上人间或者地下人间跑，我们可以定一个政策，南方人就去东莞折腾；北方人就在北京。再整一个成都，西北人都去成都耍。Page C
10、oloring其实就是这个意思。南方人，北方人，西北人就是所谓的识别着色（Coloring）。这样的好处是啥涅？不会导致大家都往成都跑【我的 YY呀。没去过。成都的应该好点吧。北京的姐妹们的一口东北口音让人基本上无言以对，情何以堪呀】。亮亮点点： 相相对对均均匀匀的的分分配配落落脚脚点点的的好好处处是是都都整整体体经经济济拉拉通通有有好好处处。理解二：不要输在起跑线上现在凡是都要计划。据说小朋友还没有出身，妈妈们就要开始琢磨上什么亲子班和各种攻略。为了就是让孩子们有个好的落脚点。可怜天下父母心。出身论在我大宋 是根深蒂固的。红N代估计从来就看不起贫M代。富K代估计从来都忘了自己的贫K-j的祖先
11、。如果不输在起跑线上？ 就是planning，把自己的孩子往中关村幼儿园整；往深圳的实验小学整。如何整？ Coloring！ 户口，买房子的地点等等。亮亮点点：人人为为调调整整住住房房和和户户口口【含含假假离离婚婚（据据说说最最后后都都变变成成真真离离婚婚）】信信息息，映映射射到到最最好好，或或者者次次好好的的校校区区。Coloring的的目目的的就就是是把把一一个个东东西西的的落落脚脚点点，有有目目的的地地，设设置置好好，从从而而获获得得最最大大利利益益。这这个个设设置置就就是是通通过过在在可可控控的的范范围围内内（OS），把把物物理理Page的的Page Frame信信息息调调配配好好，从
12、从而而最最大大程程度度上上的的利利用用大大Cache。现在我们来看看CPU的Page和Cache是如何协同工作的。现在考虑一个L2 Cache，参数如下：大小： 2MSET/Way： 4 Way SET Line: 32 Bytes 这个2M的L2 Cache有多少SET（集合或者组）？2M/（32 4） = (2 20)/ (25 * 22)=214=16K=16*1024 =10240+6144=16384 这个2M的cache是分成了16384个SET。每个SET里含有和管理4个Cache Line。这个管理算法可以是P-LRU，当然，也可以是王大师的WLRU算法。这个SET里面的替换算
13、法在此不讨论。基本上类似于贵族幼儿园内部的潜规 则。例如，送礼多的，老师就照顾多点。或者不送礼的，下个学期突然就让你的孩子out了，被另外一个小replace你们家小孩的名额了。我们现在来看一个OS层面的Page，4K大小。是如何落在这16384个SET里的。不失一般性，我们假设这个Physical Page是00. 最低端的4K内存。其地址范围是：（K）。我们来考察其在这个2M Cache中的分布情况。问题一： 一个Page有多少Cache Line？K 。也就是说每个OS层面分出来的物理页面会占据个CPU层面的Cache Line。现在假设我们对这个K的区域做一个（， ）显然，在M Cac
14、he的CPU下，这个K的内存一定都会被带到Cache中来。但是如何分布的？是散落在这个SET中的某一个连续的个SET中的。这里的某一个，其实就是第一个个SET。上上述述的的这这段段话话要要绝绝对对的的理理解解清清楚楚。否否则则下下面面的的图图都都无无法法看看，和和对对Page Coloring无无法法理理解解。一个4K大小的物理内存的东西被按照每32字节大小放在了128个不同的SET中reduced to：4千个贪官，来自不同的机关单位。每个单位是32个人，排队去天上人间（北方干部），或者去东莞（南方干部），或者去成都（西部干部）。妈咪是这样处理的： 来自同一个机关的干部们（32人一组）都在一
15、个包厢（SET）里。【妈咪注：每一个包厢其实可以容纳4组（324）贪官。但另外3组席位那是为另外贪官队伍准备的。目前，就只放一组进来】不同单位的干部们都在相邻的前后左右包厢里。4千个贪官整了128个包厢那么物理页面是如何在Cache中分布的？以此类推，第3，4，5个物理页面也都会被分配和跟在后面的Cache SET 中，而不会与前面的物理页面占据的Cache位置相冲突。Until 第（16386/128=214/27=27=128）个物理页面被分配之后。换言之，如果我们连续对128个物理页面做memset清0，就会把这个2M的L2 Cache的每个SET中放上一个Cache Line。而且没有
16、任何冲突。问题就是出在128个物理页面之后的事情。 事情要绕回去，从头来了。为什么？浅浅谈谈高高端端CPU的的Cache Coloring（3）上节中我们讲到，如果对内存的0-127（总共128）个物理页面做内存清零（memset）的话，其在cache中的分布是正好每一个SET（包厢）里，放入了一个cache line（包厢里的长凳子。每个凳子上32个人。每个包厢是4个凳子：4 Way）。现在来考虑，接着对第128th 物理Page清零。我们来考察其在Cache中会落在哪里。我们先谈结论。结结论论： 第第128th物物理理页页面面会会与与第第0个个页页面面占占据据同同样样的的Cache Sets。推推论论：* 第第ith物物理理页页面面会会与与
