Q025FreeComputer Architecture
Stably sort records in a local cache-line buffer
Interview prompt
Question
Load up to 16 key/payload records into one local synchronous storage array, stably sort them by nondecreasing key, and stream the sorted records with backpressure. Use positive KEY_W and DATA_W and 1 <= MAX_N <= 16. Each frame contains 1 through MAX_N records; assert load_last only on its final accepted record. Pulse start after that record has been accepted, while the loaded frame is waiting to start. The 900-cycle bound is measured from acceptance of start through acceptance of the final output with out_ready continuously high; input loading and output stalls are excluded.
Candidate starting point
Implementation scaffold
module local_record_sorter #(
parameter int unsigned MAX_N = 16,
parameter int unsigned KEY_W = 12,
parameter int unsigned DATA_W = 20,
localparam int unsigned ADDR_W = (MAX_N <= 1) ? 1 : $clog2(MAX_N)
) (
input logic clk,
input logic rst_n,
input logic load_valid,
output logic load_ready,
input logic load_last,
input logic [KEY_W-1:0] load_key,
input logic [DATA_W-1:0] load_data,
input logic start,
output logic busy,
output logic done,
output logic out_valid,
input logic out_ready,
output logic out_last,
output logic [KEY_W-1:0] out_key,
output logic [DATA_W-1:0] out_data
);
typedef struct packed {
logic [KEY_W-1:0] key;
logic [DATA_W-1:0] data;
} record_t;
typedef enum logic [3:0] {
LOAD, WAIT_START, READ_A, CAPTURE_A, READ_B, CAPTURE_B,
WRITE_A, WRITE_B, NEXT_PAIR, DRAIN_READ, DRAIN_CAPTURE, DRAIN_HOLD
} state_t;
state_t state_q;
record_t mem [0:MAX_N-1];
record_t mem_rdata, mem_wdata, a_q, b_q;
logic mem_we;
logic [ADDR_W-1:0] mem_addr;
int unsigned load_count_q, n_q, pass_q, pair_q, drain_q;
assign load_ready = (state_q == LOAD) && (load_count_q < MAX_N);
assign busy = (state_q != LOAD) && (state_q != WAIT_START);
assign out_valid = (state_q == DRAIN_HOLD);
assign out_last = out_valid && (drain_q == n_q - 1);
always_comb begin : select_local_memory_access
// TODO: Implement select_local_memory_access using the supplied state and interface.
end
// One local port: each cycle is either one write or one registered read.
always_ff @(posedge clk) begin : single_port_memory
// TODO: Implement single_port_memory using the supplied state and interface.
end
always_ff @(posedge clk) begin : sort_and_drain
// TODO: Implement sort_and_drain using the supplied state and interface.
end
endmoduleReviewed example
Trace one case
Input
records in arrival order=[(key2,A),(key1,B),(key2,C),(key1,D)]Expected output
streamed order=[(1,B),(1,D),(2,A),(2,C)]Stable sorting retains B before D and A before C for equal keys while each payload stays attached to its record.
What to cover
Requirements
- Preserve each payload with its key and retain arrival order among equal keys.
- Use a single read-or-write memory operation per cycle and honor one-cycle read latency.
- Handle one record, duplicate keys, sorted input, and reverse-sorted input.
- Hold the output record and out_last stable until accepted, and finish within a bounded number of internal cycles.