# LRU Cache 的硬體實現方法

前陣子在公司要做 cache 時部門前輩提供了一個還滿厲害的 LRU 的實作方法。

一般 Cache 通常採用 LRU 機制，全名為 Least Resently Used。LRU Cache 的概念用一句話來描述就是:

「當有新的資料要存到 cache 但其空間不夠時，丟掉最久沒用的資料。」

這樣的做法非常的直覺，我們就試著想想在日常生活中那些被我們堆滿物品的置物空間，若我們要清理它勢必會先從最不會用到的東西開始清理。而 cache 作為儲存資料的空間勢必也會需要清理空間供新的資料儲存。

## LRU 基本做法

實作 LRU 的基本想法就是我們需要額外的儲存單元來記錄每個儲存位址的順序。

下面我們用一個只有三個儲存位址的 cache 作為範例。

下圖左邊為 cache 的儲存位址，有三個位址 A, B, C，其儲存的資料分別為 D0, D1, D2，這三筆資料是按順序寫進去的，也就是 D0 是最早寫進 cache，接著是 D1，而最後寫入的是 D2。

而下圖右邊則是紀錄儲存位址儲存資料的順序，由剛剛資料寫入 cache 位址的順序，其順序為 A: 0, B: 1, C: 2，而 0 代表其位址所儲存的資料是最早被寫入的。


接著我們看當有一筆新的資料 D3 要寫入的話會是什麼情況。

因為 D3 要寫入時已經沒有空間可以儲存，所以 cache 必須要清出一個位址來儲存 D3。根據上圖，位址 A 中的資料是最早被寫入的代表期最久沒被使用，因此 D3 會被儲存到位址 A，並且順序會更新為下圖右邊，B: 0, C: 1, A: 2。


另外，順序並不只會因為寫入新的資料而改變。當已經存在 cache 的資料被讀取時也會使得順序改變。根據上圖，位址 B 中的資料是目前最久沒被使用到的資料，但若此時有人讀取 D1 則 D1 就不會是最久沒被使用的資料。

如下圖，因為讀取了 D1 使得順序更新成 C: 0, A: 1, B: 2。


由上面講解的方法，基本的 LRU 實現方法是需要額外的儲存單元，而這個儲存單元要多大呢？

以只有三個儲存位址的 cache 來說，紀錄順序的值最多是 2，也就是每個儲存位址需要花 2-bit 來紀錄順序，因此需要額外的 3x2-bit 的儲存單元。

若 cache 的儲存位址為 $n$，則我們可以推得所需額外儲存單元的大小為:

$$n\times\lceil\log_2n\rceil\text{-bit}$$

另外我們還需要額外的比較器來對每個位址的順序進行比較以及加法器來更新順序。

## mor1kx CPU 的 LRU 做法

好了我們終於可以進入正題了，前輩所提的這個方法其目的是為了簡化 LRU 的做法。這個方法可以在 OpenRISC 開源的 [mor1kx](https://github.com/openrisc/mor1kx) CPU 中找到。

這個方法的概念是紀錄每個儲存位址***彼此之間的先後順序***。請注意這邊並不是紀錄絕對順序，而是要兩兩位址間的順序。

這個方法的概念是紀錄每個儲存位址**彼此之間的先後順序**，請注意這邊並不是紀錄絕對順序，而是紀錄兩兩位址間的順序。

這邊一樣用剛剛前面的範例來說明。

首先，D0, D1, D2 已經依序寫入 cache。但我們不再紀錄這三個位址的順序，而是改用一個表來紀錄 A, B, C 兩兩位址的前後順序。

我們知道位址 A 比位址 B 的資料放更久，也就是順序上 A < B。位址 A 的資料也比位址 C 的資料放得更久，也就是順序上 A < C。而位址 B 的資料放的比位址 C 得更久，也就是順序上 B < C。

由此，我們可以列出下表:

|<|A|B|C|
|-|-|-|-|
|A|1|1|1|
|B|0|1|1|
|C|0|0|1|

若值為 1 表示左邊位址的順序小於上面位址。另外，對角線恆為 1。而且當我們算出這個表對角線上的值就可以得出對角線下的結果，因為其值必相反。所以在儲存這個表時，我們只需要存其一半的結果。

那我們要如何透過這個表知道當新的資料被寫入時要清除哪個位址呢？

這很簡單，我們只要把這個表的每列各自做邏輯 AND 就可以了。只要某個列上做完邏輯 AND 後結果為 1 代表這個列的位址是順序最小的。

以上表來說，我們可以得到位址 A 那列做完邏輯 AND 後為 1，代表位址 A 的資料是最久沒被使用的。

接著決定要清除的位址後，位址的順序會更新所以這個表也要更新。更新這個表的方法也很簡單，我們知道更新資料的位址其順序一定會是最大的，因此只要把原本位址 A 那列的值除了對角線的位址恆為 1 不改變外，其餘的值都做邏輯反向處理就行了，同樣的就可以得到位址 Ａ 那行的值也會被反向，因為對角線下的值必為對角線上的值的相反。

更新後的表如下:

|<|A|B|C|
|-|-|-|-|
|A|1|0|0|
|B|1|1|1|
|C|1|0|1|

這個方法所需要額外儲存的是一個兩兩順序關係的表，這個表中的每個元素都是 1-bit，而且只需要儲存這個表對角線上的元素及可。所以以三個儲存位址的 cache 來說只需要額外儲存 3x1-bit 的表。

若 cache 的儲存位址為 $n$，則我們可以推得所需額外儲存的表的大小為:

$$n\times(n-1)>>1\text{-bit}$$

以這個方法來說，儲存表的花費是比較大的，相較於第一個方法其額外的儲存單元大小是以對數增長，這個方法表的增長是線性的。不過在一般來說 cache 儲存空間並不會太大，且在控制邏輯上，這個方法只需要簡單的邏輯 AND/NOT 即可。