计算所 。张晓东 。multicore（3）
作者 陈怀临 | 2009-11-20 11:31 | 类型 专题分析, 弯曲推荐, 行业动感 | 16条用户评论 »
|
张老师的忽悠基本上从cache的pollute开始的。啥是cache的pollute涅？ 张老师给了一个非常恰当的比喻。大家都用手机。手机的calling list里有您最近用过的手机号码。。。基本上是按照一个堆栈的方式存放着，最近打的那个放在最上面。 但，这时突然一个unsolicited的流氓电话打进来，问你要不要买保险。 一下子就把您的电话记录搞乱了。系统算法就是所谓的LRU–Least Recently Used。啥意思，就是先把最近没有用的那个记录换掉。 这就是一种对你通信系统的污染（pollute）。如果10个这样的流氓电话进来，你要给朋友打电话，就要从新从地址簿里开始，而非按一个快速键，就可以与朋友或者小蜜通话了。当然，是否在cache里存有小蜜的通话记录不太好。应该做出non-cachable。慢点，但是稳当。。。在计算机系统中，无数的bug其实都是cache造成的，大量的家庭也就是从小三的手机号码被缓存在最近通话记录中被发现而稀里哗啦的。。。 如果一个刚出校门的【学/硕/博】士说他（她）过了体系结构的Quality Exams，张老师就笑了； 如果一个刚出校门的【学/硕/博】士说他（她）懂Cache，懂CPU，懂体系结构，陈首席就笑了； 关于cache pollute的学术解释可参阅： Cache Pollute。 其摘要如下： “Cache pollution describes situations where an executing computer program loads data into CPU cache unnecessarily, thus causing other needed data to be evicted from the cache into lower levels of the memory hierarchy, potentially all the way down to main memory, thus causing a performance hit.” 张老师在解释了cache pollute和LRU算法的局限性之后，谈了一下他们的工作和在数据库系统中的应用，例如mySQL。 他们的算法大概就是把一个cache拆成两部分，一部分为正常的，基于LRU的。一个小cache是留给那些不太常用的数据集的。因此，即使那些不太常用的数据被访问，从而进入cache，但因为是被放到了那个小cache里，从而不会pollute正常的cache管理。。。 张老师的这一研究成果的学术算法为： Low Inter-reference Recency Set(LIRS)。LIRS已经被mySQL采纳。 要注意的是，在cache研究方面，其内涵是比较广泛的，而非仅仅指CPU中的cache。LIRS所解决（Alleviate）的问题是数据库系统中的一些buffer management的一些东西。显然，在操作系统中文件系统中，LIRS是同样可以被应用的。 但LIRS在CPU的Cache中是不太方便利用的。 这里面最大的问题就是你如何知道一个数据集（Working Set）是高访问率，还是低访问率。这个语义CPU的Load/Store Unit是没法知道的。。。。。。 后来，张老师又解释了他们最近的另外一个工作，在Linux系统中的页面管理（Page Table）中，对Cache Friendly的配合。 这个工作确实有点新意。我当时听了，也是觉得眼睛一亮，虽然这个工作有一定局限性。我个人虽然认为我对OS方面应该比大多数叫兽们狠。但还确实对张老师他们的思路很佩服。自己确实没有想到过的Idea。 其工作的基础是针对于一些是Physically Indexed的Cache的CPU。对于什么是Physically Indexed的Cache机制，可参阅：Cache 入门。 对于没法轻易Cache入门的人们，这样理解一下：拿你的QQ或者MSN ID去寻找你，这就是Virtually Indexed。没人知道你是一个狗狗，还是一个美眉，或者一个猥琐男。但是，如果拿你的身份证号码做检索（Physically Indexed），你是谁基本上没法躲。 这个工作的重点是理解Page Coloring。如果您知道Linux的Page，vmalloc，kmalloc，其实一说啥都简单。就是，你在brk的时候，最后的最后，您要落实不是。生意场上，忽悠到最后，要见钱。 操作系统里，虚拟地址忽悠到最后，要见物理地址。 张老师的工作就是在分配一个物理页面的时候，考虑考虑是否cache friendly。对不对？有点道理。例如，如果人家Phycial 页面 PA非常需要在Cache中呆着，您就尽量少分配一下与PA在cache在有冲突的页面了。。。这样就可以减少一些cache的thrashing或者污染了。 学术的东西，如果用大白话来解释，其实都简单。难处在于把工作做细，量化。 这也就是张晓东能做OSU计算机系的系主任，IEEE Fellow 的原因之一。没有量化的工作，就不是科学。 关于张老师这方面的工作，可参阅： 这个PDF有点玄，工程师们可参阅Jiang Lin的PPT文件。 但这个工作的前提是你的CPU的cache必须是Physically Indexed。 张老师在谈这个工作的时候，我特意打断了一下，确认了一些这个前提。 总的而言，张老师在谈cache的性能优化方面，提出了如下方法论: 1. 通过应用把cache friendly的语义带进来 2. 通过编译把cache friendly的语义提取出来。 3. 通过操作系统吧cache的friendly忽悠出来 4. CPU自己聪明的一塌糊涂，自己整。 在参考或者阅读张老师的工作时，对cache的理解要稍微广义话一点，例如，数据缓存等，其实都是一种cache。不要把cache概念只理解为经典的CPU中的所谓L1，L2 等cache。 | |
 (17个打分， 平均：5.00 / 5) |
雁过留声
“计算所 。张晓东 。multicore（3）”有16个回复
我觉得张老师的思路也能用在数通上，比如把DCACHE分成两块，一块是普通的cache，一块专门用来存放数据头。然后通过TLB来指定某块内存对应的cache块，或者添加特定的L/S指令。很多CPU/NPU都有stash、CacheAlloc之类的功能在DMA的时候顺便把报文头放到cache里面去。可是等你CPU响应中断，开始处理的时候，可能头一个报文已经被flush出去了。提前prefetch也有类似的问题，我处理当前报文，一般顺便prefetch下一个的BD、buffer之类的。可是等你做一堆事的之后，之前prefetch的可能也没了。至于lock，只适合特定优化算法，也不方便，还会影响同set的效率。
不错，我的文章除了特严肃的专题，很难有连续4个5的。。。同学们还是很爱护首席的吗。
其实我能用下三滥的话语诠释一个IEEE Fellow的学术东东，多不容易呀。。。
听起来像是一个两级的cache,把替换出去的放到二级cache里面，避免去memory里面去取。如果是header和body分离的设计，谁来提取header哪？如果提取和处理在同一个线程里面，就没有必要再划一块cache，因为header应该已经在cache里面了。
首席好棒，技术白话文的先驱！！！
写过userspace下的slab，能够体会到cache的重要性，影响性能的最关键的是lock, kernel下的mm 给每个cpu都分配了一个cache的原因就是尽量避免lock 操作。
多核及并发程序的性能没办法变增的根本也是因为lock. 当然cache也有重要作用，白话来说就是历史列表的作用.
幽默的比喻来源于对事物本质的深刻理解：）
深入浅出
大家实在太过分了。给这么多5分：）
Cache问题实在太重要。其实说心里话，工作这么多年，我就没见过真正明白的。一到具体问题就犯毛病。最后其实都是概念问题。
Cache这个关不过，基本上没法做系统，或者成为一个architect，首席，或者院长：-）
陈sir，在下实在佩服您的深入浅出：）
依首席见，architecter的充分必要条件是什么呢？看过首席写的一篇如何成为系统工程师的PPT，有没有补充啊？ ：）
做一个好的architect的必要条件是：理解Divide and Conquer。这是我当年的manager教我的。他说我见过最sharp的人之一。他现在就是某冉冉升起的某公司的co-founder和cheif architect。他的思维方式，看问题抓7寸的能力确实世界一流。
充分条件就比较多了。对80后，爱情甜蜜也应该是一条。据说这样创造力才好。。。：）
冉冉升起的某公司？国内的还是国外的呀？
你别问了；打死我也不说。他没事也在这上面晃。没事就打个电话教训我一通。别看我首席来，首席去。他的电话我要么是乖乖的听，要么是故意不接：-）
80后爱情未到甜蜜刚出校门自以为懂Cache，懂一点点CPU，不敢说懂体系结构的X士，拜读大作后飘过~~
首席，我最近签名状态是：
久寂成妖|久孤成魔|非孤非寂|亦妖亦魔
奢望一下楼上的80后爱情未到甜蜜时还有个盼头～～～
80后，体系结构，Cache，编译器，算法，本来以为很懂，看了弯曲评论并有幸听过首席的一个presentation，和首席聊过几句spinlock以后，发现自己什么都不懂的小男生飘过～
把这篇文章顶起来。里面有张老师关于Page Coloring工作的一些讨论。