LRU、FIFO和随机算法的比较

3

当页面错误或缓存未命中时,我们可以使用最近最少使用(LRU)、先进先出(FIFO)或随机替换算法。我想知道哪种算法提供了最佳性能,即最小化未来缓存未命中/页面错误的可能性?

架构:Coldfire处理器


2
肯定有专门研究不同环境下不同方法的书籍吧? - user166390
有一个普遍的答案/共识吗?我不需要详细的具体信息... - rrazd
Stack Overflow不是用来提问“具体问题”的地方吗?回答这个问题高度依赖于环境。 - YetAnotherUser
我添加了一个特定的架构,所以问题现在应该足够具体了。 - rrazd
6个回答

11
The expression "There are no stupid questions" fits this so well. This was such a good question I had to create an account and post on it and share my views as somebody who has modelled caches on a couple of CPUs.
You specify the architecture a 68000 which is a CPU rather than a GPU or USB controller, or other piece of hardware which may access a cache however...
Therefore the code you run on the 68000 will make a huge difference to the part of the question "least possible future cache miss'/page faults".
In this you differentiate between cache miss's and page faults, I'm not sure exactly which coldfire architecure you are refering to but I'm assuming this doesn't have a hardware TLB replacement, it uses a software mechansim (so the cache will be shared with the data of applications).
In the replacement policy the most important factor is the number of associations (or ways).
A direct map cache (1 way), directly correlates (all most always) with the low order bits of the address (the number of bits specify the size of the cache) so a 32k cache would be the lower 15bits. In this case the replacement algorthims LRU, FIFO or Random would be useless as there is only one possible choice.
然而,对于缓存的写入,Writeback或Writethrough的选择会产生更大的影响。对于仅写入内存的操作,只有Writethrough意味着缓存行未被分配,而写回缓存则会将当前在缓存中共享相同低15位的行弹出缓存并读取再修改,以供CPU上运行的代码使用。对于只写入数据且不执行多个操作的操作,通常使用writethrough更好。此外,在现代处理器上(我不知道这种架构是否支持),可以按TLB /页面选择Writethrough或Writeback。这可能对缓存产生比策略更大的影响,您可以编程系统以匹配每个页面中的数据类型,特别是在直接映射缓存中。因此,直接映射缓存非常容易理解,也很容易理解缓存的最坏情况,最佳情况和平均情况。想象一下一个memcpy例程,它复制与缓存大小对齐的数据。例如,具有两个32k缓冲区,对齐于32k边界的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位)。不能少于一行。在DDR内存系统中,32字节通常是最优操作(还有其他原因,有时16或64字节可能更好,在算法情况下1字节最优,让我们使用32,因为这很常见)。
为了帮助理解LRU、FIFO和Random,请考虑高速缓存是完全关联的,在32k 32字节行高速缓存中,这是1024行。
随机替换策略会在每1024次替换时随机导致最坏情况的命中(即99.9%的命中),在LRU或FIFO中,我可以编写一个程序来“折腾”,即始终导致最坏的行为(即0%的命中)。
显然,如果您拥有完全关联的高速缓存,则只有在已知程序并且已知程序的确切行为时才会选择LRU或FIFO。
对于任何不可预测99.9%的东西,您将选择RANDOM,它简单地是最好的不是最差的,并且是平均水平中最好的之一,但是最好情况如何(我获得最佳性能)...

基本上这取决于处理器的路数...

如果只有2条路,我可以优化类似memcpy和其他算法以完成一个好的工作。随机替换会导致一半的错误。 如果是4条路,则在切换到其他任务时可能不会对高速缓存造成太大伤害,因此其数据仍然保持本地。随机替换会导致四分之一的错误率。 现在是8条路,统计学效果开始发挥作用,memcpy的7/8%命中率并不像1023/1024%(完全关联或优化代码)那样好,但对于未经优化的代码来说确实有所改善。

那么人们为什么不使用采用随机替换策略的全关联缓存呢?

这不是因为他们无法生成好的随机数,事实上,伪随机数发生器同样好用,而且我可以编写一个程序获得100%的未命中率,但这不是重点。使用LRU或FIFO算法,我可以编写一个有用的程序,使其具有100%的未命中率。

A 32k 32字节行完全关联高速缓存需要比较1024个值,在硬件上通过CAM完成,但这是一种昂贵的硬件,并且在“快速”处理时间内比较这么多的值是不可能的,我想知道量子计算机是否可以...。
无论如何,回答你的问题,哪一个更好:
1. 考虑写穿可能比写回更好。 2. 对于大的路数,随机更好。 3. 对于未知代码,4路或以上的随机更好。 4. 如果它是单一功能或者你想从某些你愿意优化的东西中获得最快的速度,并且你不关心最坏情况,那么LRU可能是你想要的。 5. 如果你只有很少的路数,除非你有一个非常特殊的场景,否则LRU很可能是你想要的,然后FIFO可能会好一些。
参考资料:

9
没有完美的缓存策略,因为它需要对未来(程序如何访问内存)有所了解。但是,在常见的内存访问模式情况下,有些策略比其他策略表现更好,例如LRU。在实际使用中,LRU一直表现非常出色。但是,对于你正在尝试做的事情,可能会有其他策略更好。总会存在某些内存访问模式会导致缓存策略性能不佳。你可能会发现这个线程很有帮助(并且更详细!为什么LRU比FIFO更好?)。

随机替换怎么样?它在哪里适用? - rrazd
8
随机替换算法比最近最少使用算法(LRU)在最坏情况下具有更好的性能。经典例子是在略大于缓存大小的内存中以线性方式重复扫描。在这种情况下,LRU和先进先出算法(FIFO)都会表现不佳,在所需数据项之前将其删除。 - Chris Dodd

2

我研究过的许多架构都使用LRU,因为它不仅在实现效率上提供了帮助,而且平均来说也很好地避免了缺失。然而,在最新的x86架构中,我认为有一些更复杂的事情正在发生。LRU是一种基本模型。

这实际上取决于您在设备上执行的操作类型。根据操作类型,不同的撤离策略会起到更好的作用。例如,FIFO与顺序遍历内存配合得很好。

希望这能帮到您,我并不是一个架构专家。


有什么随机替换的想法吗?我认为这比LRU更好? - rrazd
2
随机替换有点像赌博。虽然实现起来非常简单和高效,但它可能会取代你经常使用的某些内容。它不考虑任何关于你通常所做事情的启发式信息。除此之外,我对它并不很了解。 - Chad La Guardia

2

在这三种算法中,我建议使用LRU。首先,在假设有局部性的情况下,它是最优调度的良好近似值(事实证明这是一个很好的假设)。随机调度无法从局部性中受益。其次,它不会遭受Belady异常(例如FIFO)的影响;也就是说,较大的缓存并不一定意味着更好的性能,而LRU则没有这个问题。

除非您的特定问题领域强烈建议使用其他算法,否则在一般情况下,很难打败LRU算法。


2

在这三种算法中,LRU通常是最好的,而FIFO是最差的,随机算法则介于两者之间。您可以构造访问模式,使得其中任何一种算法优于其他两种,但这有点棘手。有趣的是,这个顺序也大致反映了它们实现的成本-- LRU是最昂贵的,而FIFO是最便宜的。这说明,没有免费的午餐。


0

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接