海归网首页   海归宣言   导航   博客   广告位价格  
海归论坛首页 会员列表 
收 藏 夹 
论坛帮助 
登录 | 登录并检查站内短信 | 个人设置 论坛首页 |  排行榜  |  在线私聊 |  专题 | 版规 | 搜索  | RSS  | 注册 | 活动日历
主题: [原创]关于离线最优算法和CPU缓存的理论极限
回复主题   printer-friendly view    海归论坛首页 -> 海归商务 -> 项目找投资与合作 -> 新的CPU缓存电路           焦点讨论 | 精华区 | 嘉宾沙龙 | 白领丽人沙龙
  阅读上一个主题 :: 阅读下一个主题
作者 [原创]关于离线最优算法和CPU缓存的理论极限   
绽铃子
[博客]
[个人文集]

警告次数: 2



头衔: 海归少将

头衔: 海归少将
声望: 专家

加入时间: 2006/02/03
文章: 5156

海归分: 288893





文章标题: [原创]关于离线最优算法和CPU缓存的理论极限 (7001 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

返回顶端
阅读会员资料 绽铃子离线  发送站内短信
显示文章:     
回复主题   printer-friendly view    海归论坛首页 -> 海归商务 -> 项目找投资与合作 -> 新的CPU缓存电路           焦点讨论 | 精华区 | 嘉宾沙龙 | 白领丽人沙龙 所有的时间均为 北京时间


 
论坛转跳:   
不能在本论坛发表新主题, 不能回复主题, 不能编辑自己的文章, 不能删除自己的文章, 不能发表投票, 可以 发表活动帖子, 不能添加附件不能下载文件, 
   热门标签 更多...
   论坛精华荟萃 更多...
   博客热门文章 更多...


海归网二次开发,based on phpbb
Copyright © 2005-2024 Haiguinet.com. All rights reserved.