缓存替换：LRU
Published:
上次提到最常用的 PLRU(Pseudo Least Recently Used) 的实现理论，这里介绍一下其原型 LRU 的理论和软硬件实现方式。
理论
LRU 原理上，遵循了局部性原理，最近被访问的缓存行更有可能在不久的将来再次被访问。故当容量受限时，会将最近最少使用的缓存行数据换出，并换入新数据。
LRU 实现上，主要是保证不同缓存行的访问顺序，通常会使用一些数据结构来辅助实现。
软件实现
参考题目 146. LRU 缓存 - 力扣（LeetCode） 实现 O(1) 的读、写和替换，其中最重要的是 STL 的选择，一个满足不了 O(1)的话，就设计两个，思路如下：
- 要满足
O(1)的读、写，直观想到哈希表unordered_map。 - 在替换上，需要维护访问的次序，直观解决方式是维护一个双向链表
list，插入和删除操作都是O(1)。每次访问时，将该节点移动到链表对头，这样链表尾部的节点就是最久未使用的节点。但是为了不会出现遍历list的情况（O(n)），list 存储的对象应当是一个指针，这个指针由访问哈希表来获得。
参考代码：
class LRUCache {
public:
LRUCache(int capacity) {
size = capacity;
}
int get(int key) {
auto e = cache.find(key);
if(e != cache.end()){
// update lru
auto it = e->second;
lru.splice(lru.begin(), lru, it);
// return value
return it->second;
}else{
return -1;
}
}
void put(int key, int value) {
auto e = cache.find(key);
if(e != cache.end()){
auto it = e->second;
lru.splice(lru.begin(), lru, it);
it->second = value;
}else{
// replace
if(cache.size() == size){
auto tmp = lru.back();
cache.erase(tmp.first);
lru.pop_back();
}
// allocate
lru.push_front(make_pair(key,value));
cache[key] = lru.begin();
}
}
private:
list< pair<int, int> > lru;
unordered_map<int, list< pair<int, int> >::iterator > cache;
size_t size;
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
硬件实现
硬件上的设计，其实和上述软件逻辑类似，cache 的 CAM（Content Addressable Memory）结构充当了哈希表的职责，用于数据的访问（读和写）；而在替换上，会采用单独的结构来尽可能快地实现顺序的判断（利用矩阵的并发特性）。下文主要介绍替换的结构的硬件实现方式。
矩阵法
原理: 使用一个存储单元矩阵，每个单元代表一个缓存行，当一个缓存行被访问时，会将对应的行全置为1，对应的列全置为0，未访问的行对应的列全置为1。
实现:
- 构建一个 $n\times n$ 的存储单元矩阵，其中 n 是组相联的数量。常见的 m-set n-way 的缓存需要 $m \times n^2$ 比特。
- 初始化所有存储单元为0。
- 当缓存行被访问时，将对应行置为1，对应列置为0。
- 找到全零的行对应的缓存行，即为最近最少使用的行。
注意： $n\times n$ 的存储单元矩阵本质，是想维护 1…n 缓存行的访问顺序矩阵。故存储上，最少只需要矩阵上三角的数据即可，即最少需要 $\log n$ 比特。
module matrix_lru #(parameter SIZE=8)(
input clk,
input rstb,
input update,
input [2:0] update_index,
output [2:0] lru_index
);
reg [(SIZE-1):0] matrix [0:(SIZE-1)];
reg [(SIZE-1):0] matrix_next [0:(SIZE-1)];
reg [2:0] lru_index;
reg [2:0] lru_index_next;
generate
genvar i;
for(i=0; i<SIZE; i=i+1) begin
always@(posedge clk or negedge rstb) begin
if(!rstb) matrix[i] <= 0;
else matrix[i] <= matrix_next[i];
end
end
endgenerate
generate
genvar j, k;
for(j=0; j<SIZE; j=j+1) begin
for(k=0; k<SIZE; k=k+1) begin
always@(*) begin
matrix_next[j][k] = matrix[j][k];
// 行置为1，列清为0
if(update && (j == update_index) && (k!=update_index))
matrix_next[j][k] = 1'b1;
else if (update && (k==update_index))
matrix_next[j][k] = 1'b0;
end
end
end
endgenerate
always@(*) begin
lru_index_next = lru_index;
if(matrix[0] == 8'b0)
lru_index_next = 0;
else if(matrix[1] == 8'b0)
lru_index_next = 1;
else if(matrix[2] == 8'b0)
lru_index_next = 2;
else if(matrix[3] == 8'b0)
lru_index_next = 3;
else if(matrix[4] == 8'b0)
lru_index_next = 4;
else if(matrix[5] == 8'b0)
lru_index_next = 5;
else if(matrix[6] == 8'b0)
lru_index_next = 6;
else if(matrix[7] == 8'b0)
lru_index_next = 7;
end
always@(*) begin
if(!rstb) lru_index <= 0;
else lru_index <= !lru_index_next
end
endmodule
移位寄存器
每个缓存行对应一个 m 位的移位寄存器。当缓存行被访问时，将寄存器的最高位置为1。每隔一定时间，将寄存器右移一位，低位溢出。数值最小的寄存器对应的缓存行是最近最少使用的。
值得注意的是，这种方法无法保证严格的 LRU。比如2, 3, 1, 4, 1, 1, 1, 1 一段时间后，2, 3, 4 的移位寄存器都右移至 0 后，无法选出严格 LRU 下的最近最少使用的缓存行。