LRU vs FIFO vs Random

Question

当存在页面错误或高速缓存未命中时，我们可以使用最近最少使用（LRU），先入先出（FIFO）或随机替换算法。我在想，哪一个能够提供最好的性能，也就是尽可能最少的缓存未命中/页面错误？

架构：处理器的Coldfire

Answer 1

没有完美的缓存策略存在，因为它需要知道未来（程序如何访问内存）。

但是，在普通存储器访问模式的情况下，其中一些在测量上比其他人好得多。 LRU就是这种情况。 LRU历来在整体使用方面表现出色。

但是，对于你想要做的，另一个政策可能会更好。总会有一些内存访问模式会导致缓存策略执行得不好。

你会发现这个线索有用的（和更复杂！） Why is LRU better than FIFO?

Answer 2

很多我学习使用LRU，因为它通常不仅提供了效率的实现，也就是防止遗漏平均相当不错的架构。但是，在最新的x86架构中，我认为还有一些更复杂的事情正在进行。 LRU是一种基本模型。

这真的取决于您在设备上执行的操作类型。根据不同的行动类型，不同的疏散政策会更好。例如，FIFO顺序遍历存储器就能很好地工作。

希望这有助于我，我不是一个真正的建筑家伙。

Answer 3

三者之间，我建议LRU。首先，当假设地点时，这是一个很好的近似优化调度（这是一个很好的假设）。随机调度不能从地方获益。其次，它不受Belady的异常（如FIFO）的影响;也就是说，更大的缓存意味着更好的性能，这在FIFO中不一定是正确的。

只有当您的特定问题域强烈建议使用别的东西时，LRU在一般情况下将很难被击败。

Answer 4

这三者中，LRU通常是最好的，而FIFO是最差的，随机来自两者之间的某处。您可以构建访问模式，其中三者中的任何一个都优于其他任何一个，但它有点棘手。有趣的是，这个订单大概也是他们要实现的成本 - LRU是最昂贵的，FIFO是最便宜的。只是去显示，没有免费的午餐

Answer 5

如果您想要两全其美，请考虑一种基于实际使用模式改变策略的自适应方法。例如，查看算法IBM的Adaptive Replacement Cache：http://code.activestate.com/recipes/576532-adaptive-replacement-cache-in-python/

Answer 6

表达式“没有愚蠢的问题”非常适合这一点。这是一个很好的问题，我必须创建一个帐户并在其上发布信息，并分享我的观点，作为在多个CPU上建模缓存的人员。

您指定架构的68000这是一个CPU，而不是GPU或USB控制器或其他硬件然而，其可存取缓存...

因此，您在68000上运行代码将使这个问题：“最可能的未来高速缓存未命中/页面错误”的部分的巨大差异。在这里你区分缓存未命中和页面错误，我不确定你正在引用哪个coldfire体系结构，但我假设这没有硬件TLB替换，它使用了一个软件mechansim（so缓存将与应用程序的数据共享）。

在替换政策的最重要因素是关联（或方式）的数量。 （直接映射缓存（1种方式）直接与地址的低位比特（比特数量指定缓存的大小）相关联（因此，32k缓存将是最低的15比特）。在这种情况下，替换algorthims LRU，FIFO或随机将是无用的，因为只有一个可能的选择。

然而回写或高速缓存的直写选择将有更多的影响。对于写入到存储器仅直写意味着高速缓存行没有被分配为并列于回写高速缓存，其中当前在共享相同低15位高速缓冲存储器行被喷射出来的高速缓存和读回然后修饰，使用IF运行在CPU上的代码使用这些数据）。

对于写入和不对数据执行多个操作的操作，写入操作通常要好得多，同样在现代处理器上（我不知道这个架构是否支持它），但可以选择写入操作或写入操作一个TLB /页面的基础。这可能会对缓存产生比策略更大的影响，您可以对系统进行编程以匹配每个页面中的数据类型，尤其是直接映射缓存;-)

因此直接映射缓存很容易要理解，也很容易理解缓存的最坏情况，最佳情况和一般情况的基础。

IMAGIN其中复制数据被对准到高速缓存大小的memcpy例程。例如，一个32K的直接映射的缓存，搭配上32K boundry对准的两个32K缓冲区....

0x0000 -> read 
0x8000 -> write 
0x8004 -> read 
0x8004 -> write 
... 
0x8ffc -> read 
0x8ffc -> write 

这里你可以看到读取和复制这些数据的每个字写的，发现低15位是每次读写操作都一样。

使用回写直接映射缓存（记得写回分配线执行以下操作）

0x0000 -> read 
cache performs: (miss) 
    0x0000:0x001f -> READ from main memory (ie. read 32 bytes of the source) 

0x8000 -> write 
    cache performs: (miss) 
    invalidate 0x0000:0x001f (line 0) 
    0x8000:0x801f -> READ from main memory (ie. read 32 bytes of the destination) 
    0x8000   (modify this location in the cache with the read source data) 

<loop> 

0x0004 -> read 
    cache performs: (miss) 
    writeback 0x8000:0x801f -> WRITE to main memory (ie. write 32 bytes to the desitnation) 
    0x0000:0x001f -> READ from main memory (ie. read 32 bytes of source (the same as we did just before) 

0x8004 -> write 
    cache performs: (miss) 
    invalidate 0x0000:0x001f (line 0) 
    0x8000:0x801f -> READ from main memory (ie. read 32 bytes of the destination) 
    0x8004   (modify this location in the cache with the read source data) 

</loop> <--- (side note XML is not a language but we use it as such) 

正如你看到很多内存操作下去，这其实是所谓的“颠簸”，是最好的例子最糟糕的情况。

现在假设我们使用直写高速缓存，这些都是操作：

<loop> 
0x0000 -> read 
cache performs: (miss) 
    0x0000:0x001f -> READ from main memory (ie. read 32 bytes of the source) 

0x8000 -> write 
    cache performs: (not a miss) 
    (not a lot, the write is "posted" to main memory) (posted is like a letter you just place it in the mailbox and you don't care if it takes a week to get there). 

    <loop> 

    0x0004 -> read 
    cache performs: (hit) 
     (not a lot, it just pulls the data it fetched last time which it has in it's memory so it goes very quickly to the CPU) 

    0x8004 -> write 
    cache performs: (not a miss) 
    (not a lot, the write is "posted" to main memory) 

    </loop until next 32 bytes> 
</loop until end of buffer> 

正如你可以看到一个巨大的变化，我们现在不鞭打，其实我们在这个例子中最好的情况下。

好吧，这就是写通与写回的简单情况。

但是，直接映射缓存现在并不是很常见，大多数人使用2,4或8路缓存，即一行中有2,4或8种不同的可能分配。所以我们可以在4路或8路高速缓存中同时存储0x0000,0x8000,0x1000,0x1800（显然8路也可以存储0x2000,0x2800,0x3000,0x3800）。

这将避免这种颠簸问题。

只是为了阐明32k直接映射缓存中的行号是地址的底部15位。 以32k 2的方式，它是最低的14位。 在32k 4种方式中，它是底部的13位。 在32K 8种方式中，它是最低的12位。

而在完全相关联的缓存中，它是行大小（或32位字节的最低5位）。你不能少于一条线。 32字节通常是DDR存储器系统中最优化的操作（还有其他原因，有时16个或有时64个字节可能更好，1个字节在algorthmic情况下是最优的，因此使用32是非常常见的）

为了帮助理解LRU，FIFO和Random，考虑缓存是完全关联的，在一个32k的32字节行缓存中，这是1024行。

随机替换策略会随机产生每1024次替换（即99.9％命中）的最坏情况，在LRU或FIFO中，我总是可以编写一个程序，这个程序会“th”“。总是会导致最坏的情况行为（即0％命中）。

很明显，如果你有一个完全关联的缓存，你只能选择LRU或FIFO，如果程序是已知的并且它已知程序的确切行为。

任何东西这是不是99.9％预测的，你会选择随机，它只是最擅长的不是最坏的，而最好的是平均一个，但如何最好的情况下（在那里我获得最佳性能）。 ..

那么这基本上取决于路数...

2种方式，我可以优化的东西像memcpy和其他algorthims做了很好的工作。随机会在一半时间内出错。 4种方式，当我在其他任务之间切换时，我可能不会损坏缓存，以至于他们的数据仍然是本地的。随机会得到错误的时间。 8种方式现在统计数据可以生效memcpy的命中率为7/8％不如1023/1024％（完全关联或优化的代码），但对于非优化的代码，它有所不同。

那么为什么人们不用随机更换策略制作完全关联缓存！

嗯，这不是因为他们不能生成好的随机数，实际上一个伪随机数生成器一样好，是的，我可以编写一个程序来获得100％的遗漏率，但这不是重点，我无法写出一个有100％错过的有用程序，我可以使用LRU或FIFO算法。

一个32K 32字节行全associatve缓存的要求你比较1024个值，在硬件这是通过CAM完成，但是这是一个昂贵的硬件，并且也只是不可能这么多价值的比较“快”处理的时候，我不知道如果量子计算机能够....

反正回答你的问题哪一个更好：

1. 考虑一下，如果一直写可能比写回更好。
2. 大方法的随机更好
3. 未知代码RANDOM更适合4路或更高。
4. 如果它是单一功能，或者您希望获得最佳速度，或者您不关心最坏情况，那么LRU可能就是您想要的。
5. 如果你很少有方法的LRU可能是你想要的，除非你有一个非常具体的场景，那么FIFO可能是好的。

参考文献：

• http://www.freescale.com/files/training/doc/APF_ENT_T0801_5225_COLDFIRE_MCU.pdf
• http://en.wikipedia.org/wiki/Cache_algorithms