Question

举例说明用LRU替换策略cache命中率如何计算

Answer 1

近期最少使用法（LRU法）
近期最少使用（Least Recently Used，LRU）算法。这种方法是将近期最少使用的Cache中的信息块替换出去。该算法较先进先出算法要好一些。但此法也不能保证过去不常用将来也不常用。
LRU法是依据各块使用的情况， 总是选择那个最近最少使用的块被替换。这种方法虽然比较好地反映了程序局部性规律，但是这种替换方法需要随时记录Cache中各块的使用情况，以便确定哪个块是近期最少使用的块。LRU算法相对合理，但实现起来比较复杂，系统开销较大。通常需要对每一块设置一个称为计数器的硬件或软件模块，用以记录其被使用的情况。
实现LRU策略的方法有多种。 下面简单介绍计数器法、寄存器栈法及硬件逻辑比较对法的设计思路。
计数器方法：缓存的每一块都设置一个计数器，计数器的操作规则是：

(1) 被调入或者被替换的块， 其计数器清“0”，而其它的计数器则加“1”。

(2) 当访问命中时，所有块的计数值与命中块的计数值要进行比较，如果计数值小于命中块的计数值，则该块的计数值加“1”；如果块的计数值大于命中块的计数值，则数值不变。最后将命中块的计数器清为0。

(3) 需要替换时，则选择计数值最大的块被替换。

Answer 2

没法算啊，这个怎么算啊，这个是内容相关的，跟内容局部性密切相关。不知道你是设计软件cache还是硬件cpu cache。。。
要是后者的话，一般cache size/code size>4/1000的话，cache命中率会达到90%以上，也就是说cache大小很影响命中率，其他还受相联度啊cache line size啊之类的影响。一般相联度可以是4路、8路、64路，cache line可以是8B、16B、32B、64B，具体取舍需要弄个具体代码进行实测，类似跑个benchmark
要是前者的话，嗯嗯。。访cache行为的局部性很重要，并行线程越多，访cache的地址越离散，对替换的效率要求越高，不过软件实现LRU比较麻烦哎。。。随机或round-robin算了吧
说了半天。。好像没有回答你的问题。。呵呵呵

追问

表示我还是不懂、。

Answer 3

为什么一到比较高深的问题，百度就解决不了了呢？？看看那些百度知道上能解决的问题都是百科上就能找到的！