| 作者 |
 绽铃子专利的另一处硬伤 |
ChargePump2
头衔: 海归下士
声望: 学员
加入时间: 2010/04/05
文章: 6
海归分: 342
|
|
|
绽铃子专利的另一处硬伤
|
作者：ChargePump2 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
居然半年前话题又炒起来了 
绽铃子专利核心是 Weighted LRU, 本来 LRU 是把最近没有用到的先换出 Cache， 绽铃子认为可以引入另一个条件：把最近没用到而且是最不常用到的先换出去。理由是：最常用的以后也很有可能会用到，所以应该放在 Cache 里长一些。但事实并非如此。举一简单例子：
for(i = 0; i < 1000; i++) {
j = ...
k = ...
l = ...
}
这个loop 里所有的变量都被用了无数次，意味着在WLRU 算法下他们将在Cache 里放很长的时间， 但很有可能在这个 loop 以后，这些变量都不会被用了，但他们又占住了 Cache， 被他们占用的Cache就浪费掉了，因为别的变量也没法用了。
这种 loop 在任何一个程序里都比比皆是，我很难想象WLRU会比LRU有更优越。
以前有提过 WLRU 在实现上比LRU 会更麻烦，DATAPATH 有可能被 slow down, 那些倒还不算根本上的缺陷了。
作者：ChargePump2 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
 |
绽铃子
[博客]
[个人文集]
警告次数: 2
头衔: 海归少将 
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
|
|
|
好，你够聪明。你这个例子，在LIRS里面也提到过。
|
假设，这个Loop里面，要解一个全高清的数据帧，每次循环有几百万字节的数据冲进来。
你的那些常用的，local 变量还会在缓存里面吗？
许多人都发现了这个问题。比如韩国棒子有一个发明，也是引入了历史，可是效果一塌糊涂。
细节太多太多。要不然，祖国为什么总是搞不定飞机发动机。
|
|
|
| 返回顶端 |
|
|
xia2
头衔: 海归少尉
加入时间: 2006/02/02
文章: 60
海归分: 3434
|
|
| 返回顶端 |
|
|
ChargePump2
头衔: 海归下士
声望: 学员
加入时间: 2010/04/05
文章: 6
海归分: 342
|
|
|
这个例子或类似的 loop 在任何一个程序中都会出现很多次，
|
作者：ChargePump2 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| 绽铃子 写道: | | 好，你够聪明。你这个例子，在LIRS里面也提到过。 |
你的 WLRU 在这种情况下会比 LRU 差很多。这是你的 WLRU 在算法上的根本缺陷。
基于这个分析，我不认为你的专利有任何实际的意义。 It is not even good on paper.
作者：ChargePump2 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
Sarakawa
头衔: 海归准将 
声望: 教授
加入时间: 2006/04/07
文章: 797
海归分: 134579
|
|
|
我在芯片上写过汇编程序，对CPU的工作过程和寻址等有一点儿概念，在你举的这个例子里面
|
作者：Sarakawa 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| ChargePump2 写道: | | 这个例子或类似的 loop 在任何一个程序中都会出现很多次， |
没看出来为什么WLRU一定会比LRU差很多？
在你举的例子里，因为jkl等变量在循环内里面被反复计算，所以会被WLRU算法赋予更高的权限，那么当程序还在loop里面时，WLRU的效果应该不会比LRU差，对吧？而在loop结束之后，这些变量的权重会不会快速下降？比方说程序又进入了下一个loop，这时新loop里面新的变量就会因为短时间内使用次数的急剧增加而获得高的权重。
不知道我的理解对不对：在WLRU算法里，一个地址要不要保留在缓存里，是受时间和使用情况双重制约的，所以你说的问题并不大，是这样吗？
绽玲子的WLRU算法到底怎么处理这个问题？麻烦给大家说说看。
作者：Sarakawa 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
禾乃才
头衔: 海归少校 
声望: 学员
性别: 
加入时间: 2009/04/08
文章: 680
海归分: 23538
|
|
|
这个需要绽铃子的数学逻辑能力的旁证了。所谓算法都是可以比较的。比起其它的算法又和优越性？
|
| Sarakawa 写道: | | 我在芯片上写过汇编程序，对CPU的工作过程和寻址等有一点儿概念，在你举的这个例子里面 |
|
|
|
| 返回顶端 |
|
|
绽铃子
[博客]
[个人文集]
警告次数: 2
头衔: 海归少将
声望: 专家
加入时间: 2006/02/03
文章: 5156
海归分: 288893
|
|
|
你说的这个有个专门的术语，叫：slow aging。基于访问计数的LFU算法的问题。
|
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
| ChargePump2 写道: | | 这个例子或类似的 loop 在任何一个程序中都会出现很多次， |
韩国棒子发明的LRFU算法里，这个问题非常大。而且，他想不出解决办法。
韩国棒子看到了 LRU， LFU，是两个极端，他想求个中道。
但是，LRU和LFU在某种新的角度，都是一样的。
我的专利里面有一个例子，你可以看看，我是怎么对付这个问题的。
作者：绽铃子 在 新的CPU缓存电路 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
|
|
|
|
