CPU Cache Page-Coloring.pdf-资料库

wingfiring-9170277-4744302542990782010.pdf-第1页.png

第1页 / 共25页

wingfiring-9170277-4744302542990782010.pdf-第2页.png

第2页 / 共25页

wingfiring-9170277-4744302542990782010.pdf-第3页.png

第3页 / 共25页

wingfiring-9170277-4744302542990782010.pdf-第4页.png

第4页 / 共25页

wingfiring-9170277-4744302542990782010.pdf-第5页.png

第5页 / 共25页

wingfiring-9170277-4744302542990782010.pdf-第6页.png

第6页 / 共25页

wingfiring-9170277-4744302542990782010.pdf-第7页.png

第7页 / 共25页

wingfiring-9170277-4744302542990782010.pdf-第8页.png

第8页 / 共25页

浅谈高端CPU Cache Page-Coloring 作者：陈怀临 huailin@gmail.com

前言：本文通过读者们比较熟悉的妈咪和包厢场景，阐述了高端CPU和大Cache结构中的一个比较略微高深的工程话题－－Cache Coloring。高端通信系统设计和实践中，对Cache和性能的把握是至关重要的。希望这篇文章对大宋的读者，特别是熟悉妈咪的读者有所帮助。世界上的再高深的技术和理论都可以在现实生活中找到映射。这就是所谓的：得其意；忘其形。方为做学问之最高境界了。 OS和体系结构的关系是：OS是形而上；体系结构是形而下。一个高手对这两面都必须有相当得修养，缺一不可。希望这篇文章能起到抛美女引客人的目的，使得读者们能够在业余时间去体验生活，阅读相关资料。提高自己的各方面的能力。。。。。。浅谈高端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的有效利用是其中重中之重。这就好比，你忽悠了一个美女到家里，但是美女发现你不能很好的满足她的各种需求【此处省略 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的位置。浅谈高端CPU的Cache Coloring（2）为了理解Page Coloring，需要把握或者记住下面几点： × OS的内存管理的基本分配粒度是Page，例如经典的4K大小； ×CPU的Cache管理的基本上分配粒度是基于Way-SET的Cache Line。例如， 32bytes。 ×大Cache，例如，L2，L3，很大，很大。在上述３个前提下，如果理解Page　Coloring？思考了好几天，如何用大白话来说，而非玩学术。玩胶片。我的理解大概是这样的：理解一：大宋姐妹一盘棋如果北京八大胡同的姐妹们和东莞的姐妹们都是我大宋服务业的一盘棋，我们就要一盘棋来考虑，要拉通【注：某司的专门术语。好像意味着互通有无，或者有一个良好的通信Channel】。因此，不要都往北京的天上人间或者地下人间跑，我们可以定一个政策，南方人就去东莞折腾；北方人就在北京。再整一个成都，西北人都去成都耍。Page Coloring其实就是这个意思。南方人，北方人，西北人就是所谓的识别着色（Coloring）。这样的好处是啥涅？不会导致大家都往成都跑【我的 YY呀。没去过。成都的应该好点吧。北京的姐妹们的一口东北口音让人基本上无言以对，情何以堪呀】。亮点：相对均匀的分配落脚点的好处是都整体经济拉通有好处。理解二：不要输在起跑线上现在凡是都要计划。据说小朋友还没有出身，妈妈们就要开始琢磨上什么亲子班和各种攻略。为了就是让孩子们有个好的落脚点。可怜天下父母心。出身论在我大宋是根深蒂固的。红N代估计从来就看不起贫M代。富K代估计从来都忘了自己的贫K-j的祖先。如果不输在起跑线上？就是planning，把自己的孩子往中关村幼儿园整；往深圳的实验小学整。如何整？ Coloring！户口，买房子的地点等等。。。。亮点：人为调整住房和户口【含假离婚（据说最后都变成真离婚）】信息，映射到最好，

或者次好的校区。 Coloring的目的就是把一个东西的落脚点，有目的地，设置好，从而获得最大利益。这个设置就是通过在可控的范围内（OS），把物理Page的Page Frame信息调配好，从而最大程度上的利用大Cache。现在我们来看看CPU的Page和Cache是如何协同工作的。现在考虑一个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 这个2M的cache是分成了16384个SET。每个SET里含有和管理4个Cache Line。这个管理算法可以是P-LRU，当然，也可以是王大师的WLRU算法。这个SET里面的替换算法在此不讨论。基本上类似于贵族幼儿园内部的潜规则。例如，送礼多的，老师就照顾多点。或者不送礼的，下个学期突然就让你的孩子out了，被另外一个小replace你们家小孩的名额了。我们现在来看一个OS层面的Page，4K大小。是如何落在这16384个SET里的。不失一般性，我们假设这个Physical Page是0×0. 最低端的4K内存。其地址范围是：０－（４K－１）。我们来考察其在这个2M Cache中的分布情况。问题一：　一个Page有多少Cache　Line？４K／３２＝　２＾７＝１２８。也就是说每个OS层面分出来的物理页面会占据１２８个CPU层面的Cache　Line。现在假设我们对这个４K的区域做一个ｍｅｍｓｅｔ（０ｘ０，０，　４＊１０２４）．显然，在２M　Cache的CPU下，这个４K的内存一定都会被带到Cache中来。但是如何分布的？是散落在这１６３８４个SET中的某一个连续的１２８个SET中的。这里的某一个，其实就是第一个１２８个SET。上述的这段话要绝对的理解清楚。否则下面的图都无法看，和对Page Coloring无法理解。一个4K大小的物理内存的东西被按照每32字节大小放在了128个不同的SET中 reduced to： 4千个贪官，来自不同的机关单位。每个单位是32个人，排队去天上人间（北方干部），

或者去东莞（南方干部），或者去成都（西部干部）。妈咪是这样处理的： × 来自同一个机关的干部们（32人一组）都在一个包厢（SET）里。【妈咪注：每一个包厢其实可以容纳4组（32×4）贪官。但另外3组席位那是为另外贪官队伍准备的。目前，就只放一组进来】 ×不同单位的干部们都在相邻的前后左右包厢里。 ×4千个贪官整了128个包厢那么物理页面１是如何在Cache中分布的？

以此类推，第3，4，5个物理页面也都会被分配和跟在后面的Cache SET 中，而不会与前面的物理页面占据的Cache位置相冲突。 Until 第（16386/128=2^14/2^7=2^7=128）个物理页面被分配之后。

资料库

CPU Cache Page-Coloring.pdf

相关推荐

操作系统

热门标签

最新资料