Q038FreeDesign Verification

Verify a mirrored topology checker

Difficulty: Medium
Topic: Reference Models
Language: SV

Interview prompt

Question

Verify a bounded level-order tree checker that distinguishes value asymmetry, shape asymmetry, and malformed ancestry. Supply the oracle and completion monitor in the complete checker module. MAX_LATENCY is positive. At acceptance, node_count and node_valid are known; values of valid nodes are known, while invalid-node data is ignored. An empty tree is well formed and symmetric. Malformed input returns request_error=1 and symmetric=0; otherwise request_error=0. Inputs are interpreted at rising-edge samples before that edge's nonblocking updates; the harness drives them before the edge. Sample reset low before the first request. Reset, start, busy, and done are known at sampled edges; the topology fields follow the validity rules above. An accepted request is start && !busy. Its completion must be sampled 1 through MAX_LATENCY edges later, inclusive; a missing completion reports on the next edge. Completion is processed before a same-edge new acceptance. Adjacent high done samples are legal when they retire distinct previously accepted requests; a request cannot complete twice or complete on its own accepting edge. Busy-time starts do not change the pending prediction. Reset cancels pending ownership and age. The supplied diagnostic helper accumulates reports across resets.

Level-order binary tree showing matching mirror pairs and a malformed case with a valid child under an invalid parent. — Map each node to its mirror partner, then check ancestry validity separately from value symmetry.

Candidate starting point

Implementation scaffold

module mirrored_topology_checker #(parameter int MAX_LATENCY = 40) (
  input logic clk, rst_n, start,
  input logic [4:0] node_count,
  input logic [30:0] node_valid,
  input logic [7:0] node_value [31],
  input logic busy, done, request_error, symmetric
);
  bit pending = 0;
  int unsigned age = 0;
  bit expected_error;
  int unsigned errors = 0;

  // Supplied diagnostics; reports accumulate across sampled resets.
  function void report_error(string message);
    if (errors != '1) errors++;
    $error("%s", message);
  endfunction
  function int unsigned error_count(); return errors; endfunction
  initial begin
    if (MAX_LATENCY <= 0) $fatal(1, "MAX_LATENCY must be positive");
  end
  bit expected_symmetric;

  function automatic bit topology_valid(int unsigned count, bit [30:0] valid);
    // TODO: validate count, valid-bit bounds, and ancestry.
  endfunction
  // Called only after topology_valid succeeds; invalid-node values are ignored.
  function automatic bit topology_symmetric(
    int unsigned count, bit [30:0] valid, byte unsigned value[31]
  );
    // TODO: compare mirror presence and valid values within complete levels.
  endfunction
  task automatic predict_topology(
    input int unsigned count, input bit [30:0] valid,
    input byte unsigned value[31],
    output bit expected_error, output bit expected_symmetric
  );
    // TODO: produce the complete malformed/symmetry result.
  endtask
  task automatic check_sample();
    // TODO: snapshot prediction and check reset, completion ownership and deadline.
  endtask
  always @(posedge clk) check_sample();
endmodule

Reviewed example

Trace one case

Input

node_count=7; valid bits all set; level-order values=[1,2,2,3,4,4,3]

Expected output

well_formed=1; symmetric=1

Every nonroot node has a valid parent, and mirror pairs match in both presence and value at each level.

What to cover

Requirements

Use child indexes 2*i+1 and 2*i+2 below node_count, with no valid bits at indexes greater than or equal to node_count.
Require a valid root for a nonempty tree and a valid parent for every valid nonroot node.
Compare every same-level mirror pair for both presence and value without reading invalid-node data.
Return a fixed malformed-input result and require one bounded completion unless reset cancels it.

Continue practicing

Q251 · Reference ModelsVerify a decimal palindrome checkerMediumP Q1153 · Reference ModelsModel a recent-ID replay streamHardP

module mirrored_topology_checker #(parameter int MAX_LATENCY = 40) ( input logic clk, rst_n, start, input logic [4:0] node_count, input logic [30:0] node_valid, input logic [7:0] node_value [31], input logic busy, done, request_error, symmetric ); bit pending = 0; int unsigned age = 0; bit expected_error; int unsigned errors = 0; // Supplied diagnostics; reports accumulate across sampled resets. function void report_error(string message); if (errors != '1) errors++; $error("%s", message); endfunction function int unsigned error_count(); return errors; endfunction initial begin if (MAX_LATENCY <= 0) $fatal(1, "MAX_LATENCY must be positive"); end bit expected_symmetric; function automatic bit topology_valid(int unsigned count, bit [30:0] valid); // TODO: validate count, valid-bit bounds, and ancestry. endfunction // Called only after topology_valid succeeds; invalid-node values are ignored. function automatic bit topology_symmetric( int unsigned count, bit [30:0] valid, byte unsigned value[31] ); // TODO: compare mirror presence and valid values within complete levels. endfunction task automatic predict_topology( input int unsigned count, input bit [30:0] valid, input byte unsigned value[31], output bit expected_error, output bit expected_symmetric ); // TODO: produce the complete malformed/symmetry result. endtask task automatic check_sample(); // TODO: snapshot prediction and check reset, completion ownership and deadline. endtask always @(posedge clk) check_sample(); endmodule

Question

Implementation scaffold

Trace one case

Requirements

Related questions

Question

Implementation scaffold

Trace one case

Requirements

Related questions