Q133FreeSystemVerilog
Merge two sorted ready/valid streams
Interview prompt
Question
Merge two nonempty finite streams of nondecreasing 16-bit values into one ordered ready/valid stream. Preserve duplicates and choose stream A first when both head values are equal.
Candidate starting point
Implementation scaffold
module sorted_stream_merger (
input logic clk,
input logic rst_n,
input logic a_valid,
input logic [15:0] a_data,
input logic a_last,
output logic a_ready,
input logic b_valid,
input logic [15:0] b_data,
input logic b_last,
output logic b_ready,
output logic out_valid,
output logic [15:0] out_data,
output logic out_last,
input logic out_ready
);
logic a_head_valid, b_head_valid;
logic [15:0] a_head_data, b_head_data;
logic a_head_last, b_head_last;
logic a_eof_seen, b_eof_seen;
logic choose_a;
assign a_ready = !a_head_valid && !a_eof_seen;
assign b_ready = !b_head_valid && !b_eof_seen;
always_comb begin : select_head
// TODO: Implement select_head using the supplied state and interface.
end
always_ff @(posedge clk) begin : capture_and_retire_heads
// TODO: Implement capture_and_retire_heads using the supplied state and interface.
end
endmodule
Reviewed example
Trace one case
Input
stream A=[1,3,3]; stream B=[2,3]Expected output
accepted output=[1(A),2(B),3(A),3(A),3(B)]; last=1 only on final BEqual heads select A one beat at a time, preserving both duplicates and consuming exactly one stream per output handshake.
What to cover
Requirements
- Buffer only the current head of each input stream.
- Require at least one accepted item on each input; this data-plus-last interface does not encode an empty frame.
- Retire exactly one buffered input head for each accepted output and never discard both heads on a tie. Input handshakes may prefetch those heads on earlier edges.
- Hold output valid, data, and last stable while the consumer stalls.
- Assert out_last only on the final item after both input streams have ended.
