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