| 作者 |
 [CPU cache 问题技术讨论] 自称外行的请入 |
logic
头衔: 海归中士
加入时间: 2010/11/03
文章: 8
海归分: 623
|
|
|
[CPU cache 问题技术讨论] 自称外行的请入
|
作者：logic 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
其实CPU，cache management, hit rate，听起来神秘，道理很简单。
我就是要写给不懂的人看的。
作个简单对比：
这个世界每个人都是一个程序（Program）,
假设去医院就是Memory access.
而不需要处方，直接交钱就能买药的药房就是cache.
药房能卖什么药，就是cache algorithm，
多大比例的病能在药房直接解决，就是hit rate.
又假设医院的垄断寡头叫Yitel.
LRU就是纯卖最普通，通用的药，伤风感冒的，加创可贴什么的，是Yitel自带的。但即使是最普通的药店，经过这么多年的发展，也知道哪些药必备，相对达到了成本/效益的比较好的比例。
那么在中国，药店配一个中医，在美国，配一个可以开处方的，肯定能提高hit rate。（WLRU）
现在有人发表了一篇博士论文，号称有一个新的算法(就是药房准备什么药的专利，比如在药店增加小手术)，可以提高某些人（program）的hit rate，而其他人的hit rate不下降。而成本只需要增加店面1%的面积。如果Yitel不理他,就要破产，买了他，Yitel的股票就要大涨50%，如果你是Yitel的人，会怎么反应。
理论上也不是不可以提高Hit rate，就像理论上也不是不可能更多的病在药店搞定。但是你如果说，你的药店通过库陈存新算法，要推翻整过医疗系统，真正懂的人会觉得不靠谱。
那这种新算法是不是一无是处勒？也不是，就像有些地区是近视高发区，你搞一个配眼镜的在药店，还是有用的。何况，现在的程序的历史比人类的历史短多了，程序的access pattern 分类比人的病的分类不成熟多了，也许你的算法能很好的满足某些程序的access pattern，也未可知。
作者：logic 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
 |
BWolfe_2001
警告次数: 1
头衔: 海归准将 
声望: 博导
性别: 
年龄: 44
加入时间: 2009/01/15
文章: 1222
来自: 堪培拉
海归分: 101100
|
|
|
那么，我们应该学习总统奥巴马，从医疗改革开始吗？估计也不行，如今中国卖假药的比卖真药的多得多！
|
|
|
|
| 返回顶端 |
|
|
禾乃才
头衔: 海归少校 
声望: 学员
性别:
加入时间: 2009/04/08
文章: 680
海归分: 23538
|
|
|
通俗易懂。Yitel几乎是垄断的药店。如果有足够资本开一家小一点的药店，顾客肯定去取药速度更快的药店
|
|
|
|
| 返回顶端 |
|
|
绽铃子
[博客]
[个人文集]
警告次数: 2
头衔: 海归少将 
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
|
|
|
假如说，你在一个多种族社区开一小店，你如何布置。
|
每一个人种都有太多特色的需求，而且作为人又有很多共同的需求。
你怎么办？这里面最基本的智慧，就是长尾分布。
你的例子，似是而非，并不恰当。
你知道那些药常用，那些不常用，这已经是有先见之明的最优替换算法了。
当数据量远远大于缓存的容量，你就知道W更好，还是L更好了。
|
|
|
| 返回顶端 |
|
|
绽铃子
[博客]
[个人文集]
警告次数: 2
头衔: 海归少将
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
|
|
|
喜见讨论趋于客观。深入讨论，小店的例子。
|
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
哪里有延迟，哪里就有缓存。
缓存的替换算法的哲学，可以非常准确地用小店的例子来说明。
最优替换算法，就是”早知半夜事”。楼主例子里说的，就是最优替换算法。 你知道，什么东西需求量大，而且知道什么时候需要。在这个前提下，当然店面的货物布置是最优的。问题是我们不知道。或者说我们知道，但是CPU电路不知道。因此，有些阿三科学家提出了这么个想法，对每个地址，设置一个缓存的优先级。等等。这样CPU缓存设计思想，我研究过。在此先不阐述。
LRU的思想是假设，下一个客户会重复上一个客户的需求。这个思想很聪明，比如节假日，你买酒，我也买酒，大家的需求差不多。30年来，我们都认为这是最好的办法。LRU目前是CPU缓存的唯一选择。
不过，30年后，事情变了。大量外国移民涌入。比如阿三，他们的数量已经超过了本地人。如果小店继续用LRU算法。节假日，一个白人来来买了瓶酒。然后，涌入一群阿三，买这买那。LRU算法下，酒就会被挤出店面去。下一个白人来买酒，就需要到库房里拿。
我就只说到这里，再多不想谈了。
不过欢迎提问。
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
logic
头衔: 海归中士
加入时间: 2010/11/03
文章: 8
海归分: 623
|
|
|
Yitel不会考虑中国，美国，多种族
|
作者：logic 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| 绽铃子 写道: | | 假如说，你在一个多种族社区开一小店，你如何布置。 |
我的意思正是：Yitel不会考虑中国，美国，多种族。对Yitel来说，中国，美国，多种族地区是一样的。。他针对的是general computing.不能搞具体针对某个群体（某些programs)的优化。所以对Yitel，所有小店都一个样。都是简单的。
但是这个简单也是数十年行业经验以及无数人的研究得来的。如果你说Yitel这个已经过时，那是另外一回事。
而世界上有千千万万个针对具体地区的优化方案，但那不是Yitel的Business，也不可能对Yitel造成什么大影响。
作者：logic 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
绽铃子
[博客]
[个人文集]
警告次数: 2
头衔: 海归少将
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
|
|
|
现在的主流应用就是“多种族”，科学计算已经只占1%不到了。
|
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| logic 写道: | | Yitel不会考虑中国，美国，多种族 |
现在的应用，99%都是上网，多媒体。所谓通用CPU，就是用来上网，多媒体的。
我的论文评审让我把SPEC CPU2000的模拟结果拿掉，因为能够提高网络命中率一项，就已经很了不起了。
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
logic
头衔: 海归中士
加入时间: 2010/11/03
文章: 8
海归分: 623
|
|
|
我上个贴子的“多种族“指“一个多种族社区“。
|
作者：logic 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| 绽铃子 写道: | | 现在的主流应用就是“多种族”，科学计算已经只占1%不到了。 |
我的意思是说：Yitel不会考虑具体社区。他考虑的正是所有人的共同东西。从这个角度来说，他正是考虑的最最多的种族。为了满足说有人(general computing)。
作者：logic 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
网客JT
[博客]
头衔: 海归上校 
声望: 博导
加入时间: 2008/01/11
文章: 1021
海归分: 97014
|
|
|
？？？
|
作者：网客JT 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| 引用: |
30年来，我们都认为这是最好的办法。LRU目前是CPU缓存的唯一选择。
|
这种似是而非的含糊话。。。成了认真研究和大夸海口的基础？
1) 是30多年吗？
2) “我们”在这里是谁？ 是Mark Hill吗？ 实际上cache algorithm领域有很多research 和 pubications, patents, etc. 怎么会是LRU 被认为是最好的办法？
3) LRU 目前是CPU 缓存的唯一选择？ LRU一直被使用，但不是因为它的algorithm最好。你不是literature review总结了很多算法吗？ 其它选择还是有的， Intel一直没有用， 是因为LRU的hit rate 最高吗？ by the way, Mark Hill 是个大牛，但你是否认为Intel做CPU几十年，cache design是听他的？（请看看他的简历） 
其实作为一个PhD的论文题目，你的工作应该是很不错的。所以说你的研究能力绝非唐骏、张悟本之流可比。 我相信没有人怀疑你的博士质量或你的论文反映了实实在在的作研究的功夫，即使没发表在杂志上。
但是，漫无边际地宣称你的“成果”能冲破“内存墙”，解决CPU 能耗问题，带来CPU行业的革命，Intel不理你就必垮台无疑，。。。这方式也太不靠谱了。 真学习忽悠，你得学史玉柱。唐骏，相对效果差多了。非学张悟本，要倒霉的。 不是规则老变，是你应用的有问题，没有因场合制宜。
祝你在国内的项目忽悠成功。（这话不是sarcastic,是真的。）
作者：网客JT 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
绽铃子
[博客]
[个人文集]
警告次数: 2
头衔: 海归少将
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
|
|
|
用你的例子来说，LRU只考虑白人，把所有的人，都当作白人。
|
白人购买力高（缓存价值高），阿三购买力低（缓存价值低）。
当阿三占到90%以上，LRU就不行了。
|
|
|
| 返回顶端 |
|
|
SeamusGOGOGO
[博客]
头衔: 海归少校
声望: 院士
性别:
年龄: 47
加入时间: 2007/06/04
文章: 11439
海归分: 12644
|
|
|
只看到您在发泄怀疑与焦虑的情绪，未看到理性的分析结构。
|
|
|
|
| 返回顶端 |
|
|
网客JT
[博客]
头衔: 海归上校
声望: 博导
加入时间: 2008/01/11
文章: 1021
海归分: 97014
|
|
| 返回顶端 |
|
|
SeamusGOGOGO
[博客]
头衔: 海归少校
声望: 院士
性别:
年龄: 47
加入时间: 2007/06/04
文章: 11439
海归分: 12644
|
|
|
谢了。
|
听人赞美，也是挺开心的。
保留点虚荣心，人生多一点乐趣，
不坏，不坏。
|
|
|
| 返回顶端 |
|
|
乐闻德
[博客]
声望: 院士
性别:
年龄: 48
加入时间: 2009/08/02
文章: 6342
来自: Den Vereinigten Staaten
海归分: 47
|
|
|
你的这个例子在现实生活中可以通过centralized inventory来解决
|
作者：乐闻德 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
这也是高效解决长尾的方案。可以有以下三种方式：
（1）建一个巨大的实体中心仓库，任何分店订单（local request）都在中心匹配，假设物流成本可以忽略不计。这就是 NetFlix 的经营模式；
（2）把所有分店的库存都看成一个巨大的虚拟中心仓库，任何分店订单（local request）都第一时间在中心匹配，然后通知下属分店进行配送。这就是 Amazon 的经营模式；
（3）Hybrid of 1 and 2。所有local request 先在分店完成匹配，不能匹配的再去中心仓库（可以是虚拟的，也可以是实体的）进行二次匹配，然后配送。这就是 Blockbuster 的经营模式。
看看这三种思路有哪一种是大师所说的W或者是L ?
对了，顺便问一句：W = Winner, L = L*ser 吗？ 
作者：乐闻德 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
上一次由乐闻德于2010-11-03 周三, 21:27修改，总共修改了1次 |
|
|
| 返回顶端 |
|
|
网客JT
[博客]
头衔: 海归上校
声望: 博导
加入时间: 2008/01/11
文章: 1021
海归分: 97014
|
|
|
不客气。 一点儿微不足道的表扬，就让你这么爽，真让我感动。
|
有机会一定多多赞扬你。
|
|
|
| 返回顶端 |
|
|
SeamusGOGOGO
[博客]
头衔: 海归少校
声望: 院士
性别:
年龄: 47
加入时间: 2007/06/04
文章: 11439
海归分: 12644
|
|
| 返回顶端 |
|
|
Sarakawa
头衔: 海归准将
声望: 教授
加入时间: 2006/04/07
文章: 797
海归分: 134579
|
|
|
你用的这个药店的比喻可能正好搞反了
|
作者：Sarakawa 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
LRU才是一个什么药都不预先准备好的药店，也可以说是一个什么药都先预备一点的药店，它并不专门备好大量感冒和过敏等常用药。然后他们根据进来的客户要什么药，就认为什么药接下来会继续有需求，就去补这种药，增加一点儿储备，LRU基本上是很被动的去应付病人的需求的。如果店里一下子连续来很多要十全大补膏的人，按照LRU的思维，短时间内就会把店里储备药全腾空，换成十全大补，感冒药等常用药没了，下一个来的人很可能是感冒或者过敏，那就只能去大仓库拿货了。
WLRU才是预先备好足够比例的感冒药，过敏药和创可贴的药店，不管短时间内连续进来多少个人要十全大补膏，他们根据以前感冒药和创可贴被使用的频度，他们仍然会备有足够的此类常用药，所以hit rate比较高。
当然，象哪个文豪说过：“比喻总是蹩脚的“，强调了这边的相同之处，那边又不太对，也属正常。
作者：Sarakawa 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
绽铃子
[博客]
[个人文集]
警告次数: 2
头衔: 海归少将
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
|
|
|
这个比喻好。采用LRU替换算法，如果进来一群阿三，店里就全部摆上咖喱了。
|
|
|
|
| 返回顶端 |
|
|
创思
头衔: 海归少校
声望: 学员
加入时间: 2007/07/19
文章: 220
海归分: 23833
|
|
|
把长期历史和短期历史相结合？
|
是不是可以这样理解，LRU把短期内最常用的数据保留在缓存中；WLRU不但考虑短期内的常用数据，同时也考虑长时间段内的常用数据。
|
|
|
| 返回顶端 |
|
|
Sarakawa
头衔: 海归准将
声望: 教授
加入时间: 2006/04/07
文章: 797
海归分: 134579
|
|
|
是啊，logic举例的时候搞反了！
|
作者：Sarakawa 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
作者：Sarakawa 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
|
|
|
