Q057FreeComputer Architecture
Detect duplicate valid cache tags
Interview prompt
Question
Design a checker for a small fully associative cache set that reports whether any two valid ways contain the same tag and returns the earliest matching way pair. Assume static WAYS >= 1 and TAG_W >= 1. A one-way bank has no distinct pair.
Candidate starting point
Implementation scaffold
module duplicate_tag_detector #(
parameter int WAYS = 8,
parameter int TAG_W = 12,
localparam int WAY_W = (WAYS <= 1) ? 1 : $clog2(WAYS)
) (
input logic clk,
input logic rst_n,
input logic check,
input logic [WAYS-1:0] way_valid,
input logic [TAG_W-1:0] tag [WAYS],
output logic check_ready,
output logic done,
output logic duplicate_found,
output logic [WAY_W-1:0] way_a,
output logic [WAY_W-1:0] way_b
);
logic pending;
logic [WAYS-1:0] valid_q;
logic [TAG_W-1:0] tag_q [WAYS];
logic duplicate_next;
logic [WAY_W-1:0] way_a_next, way_b_next;
assign check_ready = !pending;
always_comb begin : select_duplicate_pair
// TODO: Implement select_duplicate_pair using the supplied state and interface.
end
always_ff @(posedge clk) begin : capture_and_publish
// TODO: Implement capture_and_publish using the supplied state and interface.
end
endmodule
Reviewed example
Trace one case
Input
valid=4'b1111; tags by way=[A,B,A,A]Expected output
duplicate_found=1; way_a=0; way_b=2Pairs (0,2), (0,3), and (2,3) match. Lexicographic priority chooses (0,2); invalid ways do not participate.
What to cover
Requirements
- Compare only distinct valid ways and return way_a < way_b.
- Ignore equal tags in invalid ways.
- Use lowest-way lexicographic priority when several duplicate pairs exist.
- Capture check only when check_ready is high. Register duplicate_found and the pair on the following edge with a one-cycle done pulse; return zero indices for a miss.