Q050FreeComputer Architecture
Compact valid cache-line words in place
Interview prompt
Question
Compact the valid words in a bounded cache-line register bank toward slot zero while preserving order. Clear every vacated valid bit and data slot. Assume static N >= 1 and DATA_W >= 1.
Candidate starting point
Implementation scaffold
module cache_line_compactor #(
parameter int N = 8,
parameter int DATA_W = 16
) (
input logic clk,
input logic rst_n,
input logic load,
input logic compact,
input logic [N-1:0] line_valid_in,
input logic [DATA_W-1:0] line_data_in [N],
output logic busy,
output logic done,
output logic [N-1:0] line_valid_out,
output logic [DATA_W-1:0] line_data_out [N]
);
logic [N-1:0] compact_valid;
logic [DATA_W-1:0] compact_data [N];
integer write_idx;
always_comb begin : build_compacted_line
// TODO: Implement build_compacted_line using the supplied state and interface.
end
always_ff @(posedge clk) begin : load_and_commit_line
// TODO: Implement load_and_commit_line using the supplied state and interface.
end
endmodule
Reviewed example
Trace one case
Input
valid=5'b10110; data=[dirty,A,B,dirty,C] by slot 0..4Expected output
valid=5'b00111; data=[A,B,C,0,0]Compaction reads only original valid slots in order and clears both data and validity in every vacated suffix slot.
What to cover
Requirements
- Use the valid bitmap, not the data value, to decide which words to retain.
- Preserve the original order of all valid entries.
- Replace the internal line state with the compacted result without overwriting unread values.
- While idle, load has priority over compact. An accepted compact updates the line and raises busy after edge C0; after C1, lower busy and pulse done for one cycle. Ignore both commands while busy. Support all-valid and all-invalid lines.