当页面错误或缓存未命中时,我们可以使用最近最少使用(LRU)、先进先出(FIFO)或随机替换算法。我想知道哪种算法提供了最佳性能,即最小化未来缓存未命中/页面错误的可能性?
架构:Coldfire处理器
当页面错误或缓存未命中时,我们可以使用最近最少使用(LRU)、先进先出(FIFO)或随机替换算法。我想知道哪种算法提供了最佳性能,即最小化未来缓存未命中/页面错误的可能性?
架构:Coldfire处理器
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,因为这很常见)。基本上这取决于处理器的路数...
如果只有2条路,我可以优化类似memcpy和其他算法以完成一个好的工作。随机替换会导致一半的错误。 如果是4条路,则在切换到其他任务时可能不会对高速缓存造成太大伤害,因此其数据仍然保持本地。随机替换会导致四分之一的错误率。 现在是8条路,统计学效果开始发挥作用,memcpy的7/8%命中率并不像1023/1024%(完全关联或优化代码)那样好,但对于未经优化的代码来说确实有所改善。
那么人们为什么不使用采用随机替换策略的全关联缓存呢?
这不是因为他们无法生成好的随机数,事实上,伪随机数发生器同样好用,而且我可以编写一个程序获得100%的未命中率,但这不是重点。使用LRU或FIFO算法,我可以编写一个有用的程序,使其具有100%的未命中率。
A 32k 32字节行完全关联高速缓存需要比较1024个值,在硬件上通过CAM完成,但这是一种昂贵的硬件,并且在“快速”处理时间内比较这么多的值是不可能的,我想知道量子计算机是否可以...。我研究过的许多架构都使用LRU,因为它不仅在实现效率上提供了帮助,而且平均来说也很好地避免了缺失。然而,在最新的x86架构中,我认为有一些更复杂的事情正在发生。LRU是一种基本模型。
这实际上取决于您在设备上执行的操作类型。根据操作类型,不同的撤离策略会起到更好的作用。例如,FIFO与顺序遍历内存配合得很好。
希望这能帮到您,我并不是一个架构专家。
在这三种算法中,我建议使用LRU。首先,在假设有局部性的情况下,它是最优调度的良好近似值(事实证明这是一个很好的假设)。随机调度无法从局部性中受益。其次,它不会遭受Belady异常(例如FIFO)的影响;也就是说,较大的缓存并不一定意味着更好的性能,而LRU则没有这个问题。
除非您的特定问题领域强烈建议使用其他算法,否则在一般情况下,很难打败LRU算法。
在这三种算法中,LRU通常是最好的,而FIFO是最差的,随机算法则介于两者之间。您可以构造访问模式,使得其中任何一种算法优于其他两种,但这有点棘手。有趣的是,这个顺序也大致反映了它们实现的成本-- LRU是最昂贵的,而FIFO是最便宜的。这说明,没有免费的午餐。