Skip to question
SystemVerilogDesignVerificationFirmwareArchitectureASIC Interview Questions→
/Interview questions/Merge two sorted ready/valid streams

Q133·Free·SystemVerilog

Merge two sorted ready/valid streams

Difficulty
Hard
Topic
Streaming RTL
Language
SV
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 B

Equal heads select A one beat at a time, preserving both duplicates and consuming exactly one stream per output handshake.

What to cover

Requirements

  1. Buffer only the current head of each input stream.
  2. Require at least one accepted item on each input; this data-plus-last interface does not encode an empty frame.
  3. 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.
  4. Hold output valid, data, and last stable while the consumer stalls.
  5. Assert out_last only on the final item after both input streams have ended.
Exact question handoffPractice Q133

Solve it in the question bank, keep your progress, and reveal the reviewed solution when your access allows.

Open in question bank →
Solution accessEach time you open this Solution, one Practice Credit is used; it is not permanently unlocked. Premium Solution content also uses one credit per opening.
Continue learning

RTL Clock Boundaries and Flow

Review reset, clock boundaries, arbitration, ready-valid flow, FIFOs, and backpressure.

  • Streaming RTL
  • Ready/valid
  • Merge
  • Backpressure
RTL Clock Boundaries and Flow →
Continue practicing

Related questions

Q020 · RTL DesignAbsorb ready/valid backpressure with a skid bufferHard→Q328 · RTL DesignTwo-entry elastic ready-valid bufferHardP→Q134 · RTL DesignRoute a shared read bus without internal tri-statesMedium→Q226 · RTL DesignImplement a synchronous FIFO with exact boundary behaviorMediumP→Q402 · Protocols and InterfacesResolve Read and Write Requests on a Shared PortMediumP→
ASIC.FYI · Learn silicon end to end.info@asic.fyi