海归网首页
海归宣言
导航
博客
广告位价格
会员列表
收 藏 夹
论坛帮助
登录
|
登录并检查站内短信
|
个人设置
论坛首页
|
排行榜
|
在线私聊
|
专题
|
版规
|
搜索
|
RSS
|
注册
|
活动日历
主题:
[原创]关于离线最优算法和CPU缓存的理论极限
海归论坛首页
->
海归商务
->
项目找投资与合作
->
新的CPU缓存电路
焦点讨论
|
精华区
|
嘉宾沙龙
|
白领丽人沙龙
分屏
表形显示
阅读上一个主题
::
阅读下一个主题
作者
[原创]关于离线最优算法和CPU缓存的理论极限
绽铃子
[
博客
]
[
个人文集
]
警告次数: 2
头衔: 海归少将
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
标题:
[原创]关于离线最优算法和CPU缓存的理论极限
(8804 reads)
时间:
2010-10-18 周一, 19:53
作者:
绽铃子
在
新的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
相关主题
[原创]枯萎铁线莲的优雅
海天文学
2009-2-06 周五, 21:44
想来重庆安家落户的有福了: 重庆海归创业园热线电话 023-8907726...
海归酒吧
2007-10-21 周日, 12:05
[原创]【全职】沃优(上海)招聘 运营专员
海归招聘
2013-7-11 周四, 13:47
[原创]【全职】沃优(上海)招聘 运营专员
海归招聘
2013-6-28 周五, 14:02
[原创]【全职】沃优(上海)招聘 运营专员
海归招聘
2013-6-13 周四, 14:43
[原创]【全职】沃优(上海)招聘 运营专员
海归招聘
2013-6-08 周六, 14:41
[老中原创] 爱的底线和男人的花心度从零演变到100的全过程
海归酒吧
2010-9-15 周三, 14:26
[原创]“写意”米线
海天文学
2008-10-25 周六, 12:58
返回顶端
[原创]关于离线最优算法和CPU缓存的理论极限
--
绽铃子
- (596 Byte) 2010-10-18 周一, 19:53
(8804 reads)
归网难道没人知道现在的内存传输速度已经是10.67GB/s, 足够CPU用的了
--
over123
- (13 Byte) 2010-10-21 周四, 11:05
(2388 reads)
不是速度,是延迟。 DRAM有100多纳秒的延迟。
--
绽铃子
- (90 Byte) 2010-10-21 周四, 11:56
(2532 reads)
抱歉,查到的是15纳秒读写延迟
--
over123
- (29 Byte) 2010-10-21 周四, 12:57
(2495 reads)
L2缓存都不止15纳秒。有一本专著《cache,memory,disk》
--
绽铃子
- (60 Byte) 2010-10-21 周四, 13:18
(2459 reads)
就问一个,搞出一个样品,需要花多少钱,多少时间?有什么难度吗?
--
易千钧
- (149 Byte) 2010-10-18 周一, 23:11
(2631 reads)
那你得少吃几百万顿金钱豹!
--
Sarakawa
- (97 Byte) 2010-10-18 周一, 23:15
(2591 reads)
那就再减减不必要的开发过程中的开支,总会有办法的。
--
易千钧
- (109 Byte) 2010-10-19 周二, 00:01
(2492 reads)
有大拿给我估计,全部搞出来要300万美元。 所以,卖专利是最好的。
--
绽铃子
- (154 Byte) 2010-10-19 周二, 07:37
(2437 reads)
我也觉得你的那根筋拧不清,Intel的电话谁都会有,上网站看看就知道了。300百万就难倒了?
--
BWolfe_2001
- (104 Byte) 2010-10-21 周四, 10:41
(2203 reads)
睡觉去了,养足精气,断事如神
--
易千钧
- (0 Byte) 2010-10-19 周二, 00:03
(2321 reads)
要么注册专利,要么发表论文,在这谈论没啥用.
--
xmen03
- (40 Byte) 2010-10-18 周一, 22:52
(2239 reads)
恳请大师把在海归网上灌水的时间拿出来会见投资人,或者做一个prototype出来。
--
乐闻德
- (57 Byte) 2010-10-18 周一, 22:41
(2352 reads)
被灌了这么多CPU缓存的科普,我来民科一把。
--
uda1341
- (208 Byte) 2010-10-18 周一, 21:24
(2748 reads)
其实绽玲子说的挺清楚明白的,你一民科我就看糊涂了
--
Sarakawa
- (737 Byte) 2010-10-18 周一, 22:26
(2594 reads)
我说得太简略了
--
uda1341
- (254 Byte) 2010-10-18 周一, 22:46
(2670 reads)
Adaptive Cache有太多太多论文。 问题是,现在是多核,多线程,网络环境,
--
绽铃子
- (138 Byte) 2010-10-19 周二, 07:30
(2293 reads)
这个主意靠谱, 不过确实有很多人做了
--
创思
- (126 Byte) 2010-10-19 周二, 00:16
(2200 reads)
这个绽玲子也提过了
--
Sarakawa
- (135 Byte) 2010-10-18 周一, 23:03
(2342 reads)
真狠,1000倍,你要说提高10%我没准还真信了。
--
uda1341
- (11 Byte) 2010-10-18 周一, 21:09
(2456 reads)
过去的离线最优算法的实现,需要read ahead,每做一次替换,要读不定长的磁盘。
--
绽铃子
- (84 Byte) 2010-10-19 周二, 07:25
(2322 reads)
以空间换时间, 你的发明权要一半还给白崇禧, 一半给毛主席.
--
aomen
- (12 Byte) 2010-10-18 周一, 20:10
(2244 reads)
显示文章:
所有文章
1天
7天
2周
1个月
3个月
6个月
1年
时间顺序
时间逆序
海归论坛首页
->
海归商务
->
项目找投资与合作
->
新的CPU缓存电路
焦点讨论
|
精华区
|
嘉宾沙龙
|
白领丽人沙龙
所有的时间均为 北京时间
论坛转跳:
您
不能
在本论坛发表新主题,
不能
回复主题,
不能
编辑自己的文章,
不能
删除自己的文章,
不能
发表投票,
可以
发表活动帖子,
不能
添加附件
不能
下载文件,
热门标签
更多...
论坛精华荟萃
更多...
博客热门文章
更多...
海归网二次开发,based on phpbb
Copyright © 2005-2024 Haiguinet.com. All rights reserved.