Skip to question

Q078FreeSystemVerilog

Report the top-K opcode frequencies

Difficulty
Medium
Topic
Streaming Algorithms
Language
SV
Interview prompt

Question

Count the opcode IDs in a completed packet frame and emit up to K distinct opcodes in descending frequency order, breaking equal counts by lower opcode ID. Supply a nonempty frame of at most 64 opcodes and assert in_last only on its final accepted input. Capture k from 1 through 4 with the first accepted opcode; later changes to k do not affect that frame.

Top-K opcode ranking with an exact sampled table showing a result held through two stalled edges.
Counts rank descending, with lower opcode IDs first on a tie. Opcode 3 stays unchanged at T2, T3 and its accepting edge T4; the final result is accepted at T5.
Candidate starting point

Implementation scaffold

module top_k_opcode_reporter (
  input  logic       clk,
  input  logic       rst_n,
  input  logic       in_valid,
  input  logic       in_last,
  input  logic [3:0] opcode,
  input  logic [2:0] k,
  input  logic       out_ready,
  output logic       in_ready,
  output logic       out_valid,
  output logic       out_last,
  output logic [3:0] out_opcode,
  output logic [6:0] out_count
);
  typedef enum logic [1:0] {S_CLEAR, S_INPUT, S_SELECT, S_OUTPUT} state_t;
  state_t state_q;

  logic [6:0] histogram_q [0:15];
  logic [3:0] clear_q;
  logic [6:0] frame_count_q;
  logic [2:0] k_q, rank_q, output_length_q, output_index_q;
  logic [15:0] selected_q;
  logic [3:0] result_opcode_q [0:3];
  logic [6:0] result_count_q [0:3];

  logic candidate_found;
  logic [3:0] candidate_opcode;
  logic [6:0] candidate_count;

  always_comb begin : select_next_opcode
    // TODO: Implement select_next_opcode using the supplied state and interface.
  end

  assign in_ready   = (state_q == S_INPUT);
  assign out_valid  = (state_q == S_OUTPUT);
  assign out_opcode = result_opcode_q[output_index_q];
  assign out_count  = result_count_q[output_index_q];
  assign out_last   = (state_q == S_OUTPUT) &&
                      (output_index_q + 1'b1 == output_length_q);

  always_ff @(posedge clk) begin : clear_count_select_and_drain
    // TODO: Implement clear_count_select_and_drain using the supplied state and interface.
  end
endmodule
Reviewed example

Trace one case

Input
accepted opcodes = [3, 1, 3, 2, 1, 3]; K=2
Expected output
ranked outputs = [(opcode=3,count=3), (opcode=1,count=2)]

Opcode 3 has the highest frequency and opcode 1 is the next distinct frequency winner.

What to cover

Requirements

  1. Support opcode IDs 0 to 15, frame lengths from 1 to 64, and K from 1 to 4 captured with the first item.
  2. Clear or invalidate all 16 histogram bins between frames.
  3. Do not select an opcode twice and never emit an absent opcode.
  4. If fewer than K distinct opcodes appear, emit only those present.
  5. Begin ranking only after the frame is complete and hold each output token stable while stalled.
Continue practicing
Q145 · Data StructuresTrack top-K frequencies in a sliding windowMediumQ266 · Memory SystemsReturn the top K densest pagesMediumPQ214 · Data StructuresMaintain the top-K most frequent stream valuesMediumP