Skip to question

Q023FreeSystemVerilog

Find a target-sum operand pair

Difficulty
Medium
Topic
RTL Datapaths
Language
SV
Interview prompt

Question

Design a bounded operand-bank unit that finds two distinct valid entries whose unsigned sum equals a target. Return the lexicographically earliest pair of indices. Assume static N >= 2 and W >= 1.

Upper-triangle operand-pair matrix showing two pairs that sum to nine and a priority encoder selecting indices zero and one.
Evaluate only pairs with the first index below the second, then apply deterministic lexicographic priority.
Candidate starting point

Implementation scaffold

module two_operand_match #(
  parameter int N = 8,
  parameter int W = 8,
  localparam int IDX_W = (N <= 1) ? 1 : $clog2(N)
) (
  input  logic             clk,
  input  logic             rst_n,
  input  logic             start,
  input  logic [N-1:0]     valid,
  input  logic [W-1:0]     value [N],
  input  logic [W:0]       target,
  output logic             busy,
  output logic             done,
  output logic             found,
  output logic [IDX_W-1:0] idx_a,
  output logic [IDX_W-1:0] idx_b
);
  logic [N-1:0] valid_q;
  logic [W-1:0] value_q [N];
  logic [W:0] target_q;
  logic match_next;
  logic [IDX_W-1:0] idx_a_next, idx_b_next;

  always_comb begin : select_first_pair
    // TODO: Implement select_first_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
W=4; valid values by index=[2,7,4,5]; target=9
Expected output
found=1; idx_a=0; idx_b=1

Pairs (0,1) and (2,3) both sum to nine in W+1 bits, so lexicographic priority selects the lower first index.

What to cover

Requirements

  1. Support a parameterized bank with at least two entries and return idx_a < idx_b.
  2. Add in W+1 bits so W-bit wraparound cannot create a false match.
  3. Capture the bank, valid bits, and target when start is sampled while idle. Register found and the indices on the following edge with a one-cycle done pulse; ignore new starts while busy and return zero indices for a miss.
  4. When several pairs match, choose the lowest idx_a and then the lowest idx_b.
Continue practicing
Q144 · Hardware AlgorithmsCount target-sum burstsMediumQ010 · Hardware AlgorithmsOptimize nonadjacent bank activationMediumQ168 · RTL DesignCount active lanes in a predicate maskEasy