Skip to question

Q123FreeSystemVerilog

Validate micro-operation dependencies

Difficulty
Medium
Topic
Hardware Algorithms
Language
SV
Interview prompt

Question

Build a bounded dependency validator for a programmable accelerator. Load directed edges u -> v, where u must issue before v, report whether the graph is acyclic, and emit the legal node order when it is. Accept node_count from 1 through 8 and edge_count from 0 through 16 with cfg_valid && cfg_ready. Node IDs run from 0 through node_count-1. Supply exactly edge_count distinct directed edges with both endpoints in that range; self-edges are legal inputs that form a cycle. Accept start only when start_ready is high. The result handshake precedes any order output; cyclic input produces no order beats.

Candidate starting point

Implementation scaffold

module dependency_validator (
  input  logic       clk,
  input  logic       rst_n,
  input  logic       cfg_valid,
  input  logic [3:0] node_count,
  input  logic [4:0] edge_count,
  input  logic       edge_valid,
  input  logic [2:0] edge_src,
  input  logic [2:0] edge_dst,
  input  logic       start,
  input  logic       order_ready,
  input  logic       result_ready,
  output logic       cfg_ready,
  output logic       edge_ready,
  output logic       start_ready,
  output logic       order_valid,
  output logic       order_last,
  output logic [2:0] order_node,
  output logic       result_valid,
  output logic       acyclic
);
  typedef enum logic [2:0] {
    S_CFG, S_EDGES, S_WAIT, S_SELECT, S_REMOVE, S_RESULT, S_DRAIN
  } state_t;

  state_t state_q;
  logic [7:0] adj_q [0:7];
  logic [4:0] indegree_q [0:7];
  logic [7:0] processed_q;
  logic [2:0] order_mem [0:7];
  logic [3:0] node_count_q, processed_count_q;
  logic [4:0] edge_target_q, edge_loaded_q;
  logic [2:0] active_node_q, dst_q, drain_q;
  logic acyclic_q;
  logic eligible_found;
  logic [2:0] eligible_node;

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

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

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

Trace one case

Input
nodes=4; edges = [0->2, 1->2, 2->3]
Expected output
acyclic=1; emitted order = [0, 1, 2, 3]

Nodes 0 and 1 are initially eligible, so the lower-index rule emits 0 first; node 2 becomes eligible only after both incoming edges retire.

What to cover

Requirements

  1. Support 1 to 8 nodes and 0 to 16 nonduplicate directed edges; a self-edge is a cycle.
  2. Accept the declared edge count before start, and allow a zero-edge graph to start immediately after configuration.
  3. Always choose the lowest-numbered eligible node and update every affected indegree exactly once.
  4. Buffer the complete order until acyclicity is known so a cyclic graph emits no order tokens.
  5. Hold the result and each order token stable under backpressure.
Continue practicing
Q631 · RTL DesignSelect the oldest ready micro-operationMediumPQ552 · Reference ModelsCompile, program, and verify a bounded pattern matcherHardPQ085 · RTL DesignSchedule bank commands with accepted-slot cooldownMedium