没有完美的缓存策略,因为它需要了解未来(程序如何访问内存).
但是,在常见的内存访问模式案例中,有些内容明显优于其他内容.这是LRU的情况.从历史上看,LRU在整体使用方面表现非常出色.
但是,对于你想要做的事情,另一项政策可能会更好.总有一些内存访问模式会导致缓存策略执行不佳.
您可能会发现此线程有用(并且更详细!) 为什么LRU优于FIFO？
小智 8
"没有愚蠢的问题"这句话很适合.这是一个非常好的问题,我不得不创建一个帐户并在其上发布并分享我的观点,因为有人在几个CPU上建模了缓存.
您可以将架构指定为CPU,而不是GPU或USB控制器,或者可以访问缓存的其他硬件......
因此,您在68000上运行的代码将对"最不可能的未来缓存未命中/页面错误"问题的部分产生巨大影响.
在这个你区分缓存未命中和页面错误,我不确定你正在引用哪个coldfire架构,但我假设这没有硬件TLB替换,它使用软件mechansim(所以缓存将是与应用程序的数据共享).
在替代政策中,最重要的因素是协会(或方式)的数量.
直接映射高速缓存(1路)直接与地址的低位相关(最常见)(位数指定高速缓存的大小),因此32k高速缓存将是低15位.在这种情况下,替换算法LRU,FIFO或随机将是无用的,因为只有一种可能的选择.
但是,Writeback或Writethrough选择缓存会产生更多影响.仅用于写入内存写入意味着高速缓存行未分配为与写回高速缓存相关联,其中当前位于高速缓存中的共享相同低15位的行从高速缓存中弹出并读回然后进行修改,以供使用IF CPU上运行的代码使用此数据).
对于写入和不对数据执行多个操作的操作,然后写入通常要好得多,在现代处理器上也是如此(我不知道这个架构是否支持它),但可以在TLB/Page上选择Writethrough或Writeback基础.这可以对缓存产生比策略更好的效果,您可以对系统进行编程以匹配每个页面中的数据类型,尤其是在直接映射缓存中;-)
所以直接地图缓存很容易理解,它也很容易理解缓存最坏情况,最佳情况和平均情况的基础.
想象一个memcpy例程,它复制与缓存大小对齐的数据.例如32k直接映射缓存,在32k边界上对齐两个32k缓冲区....
0x0000 -> read
0x8000 -> write
0x8004 -> read
0x8004 -> write
...
0x8ffc -> read
0x8ffc -> write
在这里,您可以看到复制每个数据字时的读写操作,注意每个读写操作的低15位是相同的.
使用writeback的直接映射缓存(记住writeback分配行执行以下操作)
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)
当你看到很多内存操作继续下去时,这实际上被称为"颠簸",并且是最坏情况scenairo的最佳示例.
现在假设我们使用了一个写入缓存,这些是操作:
<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我总是可以写一个程序,将"捶打",即.总是导致最坏情况的行为(即0%命中).
显然,如果你有一个完全关联的缓存,你只能选择LRU或FIFO,如果该程序是已知的,并且已知该程序的确切行为.
对于没有99.9%可预测的任何东西,你会选择RANDOM,它只是最好的不是最差的,并且是最好的平均值之一,但最佳情况如何(我获得最佳性能)...
那它主要取决于方式的数量......
2种方式,我可以优化像memcpy和其他algorthims这样的东西来做好工作.随机会在一半时间内弄错.4种方式,当我在其他任务之间切换时,我可能不会破坏缓存,以至于他们的数据仍然是本地的.随机会让时间错误.8种方式现在统计可以生效,memcpy的7/8%命中率不如1023/1024%(完全关联或优化的代码),但对于非优化代码,它会有所不同.
那么为什么人们不用随机替换策略来制作完全关联的缓存呢!
那么这不是因为他们不能产生良好的随机数字,其实是一个伪随机数生成器是一样的好,是的,我可以写一个程序,获得100%的命中率,但是这不是重点,我不能写一个有用的程序,可以100%错过,我可以使用LRU或FIFO算法.
32k 32字节线完全关联缓存要求您比较1024个值,硬件中这是通过CAM完成的,但这是一个昂贵的硬件,并且也不可能在"快速"处理中比较这么多值那时候,我想知道量子计算机能不能......
无论如何回答你的问题哪一个更好:
参考文献: