| 作者 |
 [原创]关于离线最优算法和CPU缓存的理论极限 |
绽铃子
[博客]
[个人文集]
警告次数: 2
头衔: 海归少将 
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
|
|
|
[原创]关于离线最优算法和CPU缓存的理论极限
|
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
离线最优替换算法（offline optimal replacement )是一个无限智能的算法，在现实中不可能实现，只有理论分析的价值。
离线的意思就是”事后“，事后我们大家都是诸葛亮。离线的实现，是把程序运行的内存访问先记录下来，然后一条条分析，找出最优的替换决定。这样我们可以得到一个程序的CPU缓存表现的理论最高值。
现实中可以实现的算法，都是”在线（online）“。在线，就是事前。事前猪一样，事后诸葛亮。在线算法，不知道未来，只能猜测未来。
WLRU和LRU都是在猜测未来。 LRU可以说是”性善论“者，它认为，每个地址都有可能被再次使用，也就是有缓存的价值。 WLRU是”性恶论“者，我认为，大部分地址都不会被再次使用，也就是没有缓存的价值。
事实证明，”性恶论“者是对的。
和离线替换算法比较，可以看出在线替换算法的”聪明程度“。这就好比说，某人90%的决定都和诸葛亮一样，他可以拿诸葛亮90%的工资。
这个手段非常有效，但是30年来，从未被使用过。因为最优算法的计算量非常大。
我在科研上的几个突破之一，就是改进了最优替换算法的实现，加快了大概1000倍。这个改进，主要是利用了新的技术手段，用空间换时间。30年后，硬盘，内存都很便宜了。
Mark Hill是威斯康星的教授，缓存领域的权威，他提出的3C模型，误导了全世界。
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
 |
aomen
头衔: 海归中校 
声望: 讲师
加入时间: 2008/12/01
文章: 1368
海归分: 44707
|
|
|
以空间换时间, 你的发明权要一半还给白崇禧, 一半给毛主席.
|
还敢挤兑毛主义的龙心么?
|
|
|
| 返回顶端 |
|
|
uda1341
头衔: 海归中尉
声望: 讲师
加入时间: 2009/09/01
文章: 110
海归分: 4371
|
|
|
真狠，1000倍，你要说提高10%我没准还真信了。
|
1000倍从何而来呢？
|
|
|
| 返回顶端 |
|
|
uda1341
头衔: 海归中尉
声望: 讲师
加入时间: 2009/09/01
文章: 110
海归分: 4371
|
|
|
被灌了这么多CPU缓存的科普，我来民科一把。
|
作者：uda1341 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
既然事后诸葛亮是最好的办法。
那么我们可以在CPU缓存上做一些柔性设置，可以动态的改变算法的属性，例如改变一些寄存器的值应该不会有太大的影响。
这样的话，如果在编译器的设计中，可以为代码打上一些标记，通过这个标记来柔性的设置缓存策略，从而接近理想值。
补充：以我的经验，一定可以找到某篇早就发表过的论文是关于这种方法的，这样的事情碰到好多回了，一般说来不紧跟学术前沿相当一段时间创新的可能性非常小。
作者：uda1341 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
Sarakawa
头衔: 海归准将 
声望: 教授
加入时间: 2006/04/07
文章: 797
海归分: 134579
|
|
|
其实绽玲子说的挺清楚明白的，你一民科我就看糊涂了
|
作者：Sarakawa 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| uda1341 写道: | | 被灌了这么多CPU缓存的科普，我来民科一把。 |
“那么我们可以在CPU缓存上做一些柔性设置，可以动态的改变算法的属性，例如改变一些寄存器的值应该不会有太大的影响。
这样的话，如果在编译器的设计中，可以为代码打上一些标记，通过这个标记来柔性的设置缓存策略，从而接近理想值。 ”
你说“动态地改变算法的属性”是什么意思？你上面这段话，我看不明白？ 
缓存算法的关键在于：对已经调入缓存的数据的“可复用性”做一个评估（其实就是一个事前猪哥亮式的猜测），对下次会被继续使用的可能性不高的数据，就丢弃了。这么做的原因是缓存的空间有限，而且再次去内存取同样的数据过来，代价非常高，所以必须评估已经取来的数据值不值得保留在缓存里，等待继续使用。
你可以对每个数据做各种标记（比方加个权重），以确定它的可“复用性”的高低，但是如果你做标记的复杂程度太高（比方说要涉及的数据过多），或者要占用的空间太多，那就抵消了缓存算法的好处。所以缓存算法在online工作的时候是不能大量采样，做很复杂的比较的。
权威的LRU算法认为最后被使用的数据有被重复使用的最高可能性，绽玲子说他通过试验认为不是这样的。LRU默认数据或多或少总是会被重复使用的（性本善），绽玲子认为这个假设不必要，除非得到确认，否则应该默认数据不会被重复使用（性本恶），我觉得他这个比喻非常精辟！
还有他对offline和online的关系的描述，也很简洁漂亮，我想除了因为他语言表达的能力好之外，主要还是因为他对这个领域很了解。我建议绽玲子，如果这个WLRU算法不成功，卖不到钱，那可以去当科普作家，不会比方舟子差。 
作者：Sarakawa 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
上一次由Sarakawa于2010-10-19 周二, 00:51修改，总共修改了2次 |
|
|
| 返回顶端 |
|
|
乐闻德
[博客]
声望: 院士
性别: 
年龄: 48
加入时间: 2009/08/02
文章: 6342
来自: Den Vereinigten Staaten
海归分: 47
|
|
|
恳请大师把在海归网上灌水的时间拿出来会见投资人，或者做一个prototype出来。
|
连我都看出来了：在这里，懂行的不一定有钱，有钱的不一定懂行。
既有钱又懂行的也没时间上这个网。恳请大师三思！
|
|
|
| 返回顶端 |
|
|
uda1341
头衔: 海归中尉
声望: 讲师
加入时间: 2009/09/01
文章: 110
海归分: 4371
|
|
|
我说得太简略了
|
作者：uda1341 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| Sarakawa 写道: | | 其实绽玲子说的挺清楚明白的，你一民科我就看糊涂了 |
我的意思是先有这样一个前提：
程序A使用X缓存算法效率最高。
程序B使用Y缓存算法效率最高。
如果把缓存部分设计成可以配置的那种，跑程序A的时候就配置成X，跑程序B的时候就配置成Y。
虽然完全柔性的配置是不可能的，但可以尽量接近这种效果。
简单点，粗略点，比如跑数据库和跑多媒体就可以用不同的配置嘛。
我是顺着那个离线的思路来的，反正程序又不会变，用工具先模拟跑一遍好了，得出最优策略，然后把缓存配置成最优策略，不就变成事前诸葛亮了？
反正我也是民科YY，侃侃好啦。
作者：uda1341 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
xmen03
头衔: 海归上尉
性别:
加入时间: 2006/01/23
文章: 101
来自: 辽宁
海归分: 7859
|
|
|
要么注册专利,要么发表论文,在这谈论没啥用.
|
找几个业界专家 一 聊，人家都 能给你 点明白
你这东西 到底 有没有用。
|
|
|
| 返回顶端 |
|
|
Sarakawa
头衔: 海归准将
声望: 教授
加入时间: 2006/04/07
文章: 797
海归分: 134579
|
|
|
这个绽玲子也提过了
|
作者：Sarakawa 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
你这么一解释，我明白你的意思了。但是你让硬件部分去附和不同软件的特质，这个思路是不合算的，这需要在硬件那里保留很大的冗余。基本上我们只看到软件去迁就硬件。
不过据绽玲子宣称：在处理互联网方面的应用，他那套WLRU算法最好使。所以他说要从Server CPU先做起。
作者：Sarakawa 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
上一次由Sarakawa于2010-10-19 周二, 01:06修改，总共修改了1次 |
|
|
| 返回顶端 |
|
|
易千钧
头衔: 海归上校 
声望: 讲师
加入时间: 2008/05/19
文章: 689
海归分: 74212
|
|
|
就问一个，搞出一个样品，需要花多少钱，多少时间？有什么难度吗？
|
技术上，不懂。经过你的普及，明白了一点点。
我以一个朴实的农民想法提问，什么能搞出个样品出来给瞧一瞧？从设计到成品，需要花多少钱，多久？
如今，最不值钱的就是钱了。捐点钱，搞出个样品出来试一试，最直接了。
就当是勒紧裤带，少去几次8号公馆，少吃几次金钱豹，支援网友搞原子弹开发了。
|
|
|
| 返回顶端 |
|
|
Sarakawa
头衔: 海归准将
声望: 教授
加入时间: 2006/04/07
文章: 797
海归分: 134579
|
|
|
那你得少吃几百万顿金钱豹！
|
作者：Sarakawa 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| 易千钧 写道: | | 就问一个，搞出一个样品，需要花多少钱，多少时间？有什么难度吗？ |
做个样品（好像行话叫做“流片”）就得几百万美元。而且这离能成功商业化还差十万八千里，不过如果能把咱党忽悠进来，那钱就是小事了。
作者：Sarakawa 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
易千钧
头衔: 海归上校
声望: 讲师
加入时间: 2008/05/19
文章: 689
海归分: 74212
|
|
|
那就再减减不必要的开发过程中的开支，总会有办法的。
|
作者：易千钧 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| Sarakawa 写道: | | 那你得少吃几百万顿金钱豹！ |
作商人的，就得像洛克菲勒那样，先学会控制成本和风险，然后是敢于下注和投机。
CCP不好忽悠滴，看起来可能是。人家只会撒钱给嫡系花，或者孝敬美国老大。
哇塞，要这么多？所以嘛，我们需要说客、金融家和投机份子。
作者：易千钧 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
易千钧
头衔: 海归上校
声望: 讲师
加入时间: 2008/05/19
文章: 689
海归分: 74212
|
|
|
睡觉去了，养足精气，断事如神
|
| 易千钧 写道: | | 那就再减减不必要的开发过程中的开支，总会有办法的。 |
|
|
|
| 返回顶端 |
|
|
创思
头衔: 海归少校 
声望: 学员
加入时间: 2007/07/19
文章: 220
海归分: 23833
|
|
|
这个主意靠谱, 不过确实有很多人做了
|
作者：创思 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
我也认为对每个程序profiling 之后再采用专用的cache 算法是最佳决策.
在google上搜索: reconfigurable cache 有一大堆的研究工作, 至少2000年就开始做
了. 既然现在还没用到工业界上,想必有什么难点.
作者：创思 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
绽铃子
[博客]
[个人文集]
警告次数: 2
头衔: 海归少将
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
|
|
|
过去的离线最优算法的实现，需要read ahead，每做一次替换，要读不定长的磁盘。
|
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| uda1341 写道: | | 真狠，1000倍，你要说提高10%我没准还真信了。 |
我做了一个“数据库”，把每个地址的全部访问历史，写在数据库里，这样就不需要反复地读磁盘了。
30年前，磁盘小，现在磁盘很大，又便宜。
这就是“空间换时间”。
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
绽铃子
[博客]
[个人文集]
警告次数: 2
头衔: 海归少将
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
|
|
|
Adaptive Cache有太多太多论文。 问题是，现在是多核，多线程，网络环境，
|
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
许多不同种类的程序共同share缓存。
数据密集型程序会“洗刷(flush)"j计算密集型程序的缓存。
这也是为什么过去几款Intel多核产品的L2缓存都是设计成”私有“的。
缓存是CPU的最关键，全世界都在拼命研究，可惜没有人怀疑最基本的假设。
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
绽铃子
[博客]
[个人文集]
警告次数: 2
头衔: 海归少将
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
|
|
|
有大拿给我估计，全部搞出来要300万美元。 所以，卖专利是最好的。
|
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| 易千钧 写道: | | 那就再减减不必要的开发过程中的开支，总会有办法的。 |
但是，我脑子里不知道有那根筋不对，手里有Intel的电话，就是不愿意去联系。
难道我真的想把Intel搞掉？那可是美国人民的养老金重仓的股票。
我都不知道自己应该怎么做。
65纳米流片的钱大概100万美元，买ARM的授权需要一百万，然后其他的费用，制造。
300万美元总投资，够了。
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
BWolfe_2001
警告次数: 1
头衔: 海归准将
声望: 博导
性别:
年龄: 44
加入时间: 2009/01/15
文章: 1222
来自: 堪培拉
海归分: 101100
|
|
|
我也觉得你的那根筋拧不清，Intel的电话谁都会有，上网站看看就知道了。300百万就难倒了？
|
作者：BWolfe_2001 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| 绽铃子 写道: | | 有大拿给我估计，全部搞出来要300万美元。 所以，卖专利是最好的。 |
问题不是300百万，而是弱肉强食的商业战场。你就认了吧，卖专利许可。人家买你是看得起你，不买你也照样挣大钱。买了你，你跟着挣钱，何乐而不为？
年轻人，别太好高骛远了。仅凭一项专利就要颠覆世界是痴人说梦。
作者：BWolfe_2001 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
over123
头衔: 海归少尉
声望: 学员
加入时间: 2008/09/16
文章: 223
海归分: 2173
|
|
|
归网难道没人知道现在的内存传输速度已经是10.67GB/s， 足够CPU用的了
|
有必要改良什么缓存算法吗？
|
|
|
| 返回顶端 |
|
|
绽铃子
[博客]
[个人文集]
警告次数: 2
头衔: 海归少将
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
|
|
|
不是速度，是延迟。 DRAM有100多纳秒的延迟。
|
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| over123 写道: | | 归网难道没人知道现在的内存传输速度已经是10.67GB/s， 足够CPU用的了 |
延迟占大头，速度再快也没有用。就算是0速度，延迟在，还是空闲。
Intel的Core i7的L3缓存12MB，占总晶体管的80%。
如果缓存不重要，有必要这么过分吗!~
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
|
|
|
