Q041FreeComputer Architecture
Control a tiny exact-LRU associative cache
Interview prompt
Question
Build a 2-to-8-way fully associative cache controller with serialized read (GET) and write/update (PUT) commands, exact least-recently-used (LRU) replacement, and a stallable one-entry response channel. TAG_W and DATA_W are positive. GET miss returns zero data; PUT returns zero read data. When rsp_evict_valid is low, return zero eviction tag and data. Metadata changes once when the command is accepted and then stays unchanged while its response is pending.
Candidate starting point
Implementation scaffold
module exact_lru_cache #(
parameter int unsigned WAYS = 4,
parameter int unsigned TAG_W = 8,
parameter int unsigned DATA_W = 32,
localparam int unsigned RANK_W = (WAYS <= 2) ? 1 : $clog2(WAYS)
) (
input logic clk,
input logic rst_n,
input logic cmd_valid,
output logic cmd_ready,
input logic cmd_put,
input logic [TAG_W-1:0] cmd_tag,
input logic [DATA_W-1:0] cmd_wdata,
output logic rsp_valid,
input logic rsp_ready,
output logic rsp_hit,
output logic [DATA_W-1:0] rsp_rdata,
output logic rsp_evict_valid,
output logic [TAG_W-1:0] rsp_evict_tag,
output logic [DATA_W-1:0] rsp_evict_data
);
logic valid_q [0:WAYS-1];
logic [TAG_W-1:0] tag_q [0:WAYS-1];
logic [DATA_W-1:0] data_q [0:WAYS-1];
logic [RANK_W-1:0] rank_q [0:WAYS-1];
logic hit, have_invalid;
int unsigned hit_idx, invalid_idx, victim_idx;
assign cmd_ready = !rsp_valid || rsp_ready;
always_comb begin : lookup_hit_invalid_and_victim
// TODO: Implement lookup_hit_invalid_and_victim using the supplied state and interface.
end
always_ff @(posedge clk) begin : accept_command_and_respond
int unsigned target;
// TODO: Implement accept_command_and_respond using the supplied state and interface.
end
endmoduleReviewed example
Trace one case
Input
2-way empty cache: PUT A, PUT B, GET A, PUT CExpected output
GET A hits and makes A MRU; PUT C evicts B and reports B's tag/dataAfter the hit, B is exact LRU; the full-cache insertion replaces only that way while A and C remain unique valid tags.
What to cover
Requirements
- A GET hit returns data and becomes most recently used (MRU); a GET miss leaves recency unchanged.
- PUT updates a hit, otherwise uses the lowest-index invalid way before evicting the exact LRU way.
- Keep tags unique among valid ways and report evicted tag/data only for a full-cache replacement.
- Hold every response field and all cache metadata stable while a response is stalled.