Tree-PLRU cho cache 4 đường: bit chỉ ra xa, đừng chạm nửa kia

Cache set-associative cần chọn đường nạn nhân (victim) để thay khi miss. LRU thật với 4 đường cần nhớ thứ tự đầy đủ của 4 đường (4! = 24 trạng thái, ≥ 5 bit, logic cập nhật phức tạp). Tree-PLRU chỉ dùng 3 bit xếp thành cây nhị phân và cho kết quả gần LRU, đủ tốt cho hầu hết CPU.

module plru4 (
  input  logic       clk,
  input  logic       rst_n,    // reset bất đồng bộ: mọi bit = 0 (victim = 0)
  input  logic       access,   // 1: có truy cập (hit hoặc lấp đầy) vào way ở cạnh lên này
  input  logic [1:0] way,
  output logic [1:0] victim    // đường nên thay, tính tổ hợp từ trạng thái hiện tại
);

Cây 3 bit, mỗi bit chỉ về phía nên thay:

            b0
         0 /  \ 1
         b1    b2
       0/ \1  0/ \1
      w0  w1 w2  w3

• victim: đi từ gốc theo các bit. Ví dụ b0 = 1, b2 = 0 → victim = 2.
• Truy cập way w: mọi bit trên đường từ gốc tới w được đặt chỉ ra xa w. Bit không nằm trên đường đó giữ nguyên.

Ví dụ từ reset: truy cập 0 → b0 = 1, b1 = 1, victim = 2. Truy cập tiếp 2 → b0 = 0, b2 = 1, victim = 1.

Testbench đổi access, way ở cạnh xuống và kiểm victim trước khi đổi.