海归论坛 :: 阅读主题 - [原创]关于离线最优算法和CPU缓存的理论极限

through

#1: [原创]关于离线最优算法和CPU缓存的理论极限 (7891 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

海归论坛 -> 新的CPU缓存电路

output generated using printer-friendly topic mod. 所有的时间均为北京时间

第1页，共2页