How to Check Out-Of-Order Transactions

This article presents a general solution to the classic problem of checking out-of-order transactions. The main goal is to present the solution as a verification pattern that can be easily grasped and adapted to your verification project requirements (e.g. verification language, reference implementation language, design under test – DUT specifics etc.).

The article’s sections are:

• Intro
• Algorithm Implementation
• Optimized Search Implementation
• Further Study

Intro

The picture below depicts a standard verification environment for a DUT with one input and one output interface.

Beside the standard verification components (e.g. driver, monitor, scoreboard) I illustrated the reference, it’s connections to surrounding components(e.g. Monitor IN, comparator) and the context it is instantiated in (e.g. scoreboard). The reference can be implemented in SystemVerilog, e-Language, C/C++, SystemC, Matlab etc. Usually the Reference is accessed from the Scoreboard and it receives the same transactions as the DUT does in order to compute the expected DUT’s outputs as precise as possible, both time-wise and data-wise. While the reference can predict DUT’s output data quite easily, it is at least tricky, if not impossible, to keep it in sync with the DUT time-wise.

The timing difference between Reference and DUT determines the order of the transactions. Given that DUT’s implementation is by it’s nature timed, the timing difference is determined by the Reference implementation:

• Functional: the Reference always finishes processing before the DUT
• Loosely Timed / Approximately Timed (LT / AT): the order of transaction arrival at the comparator is not guaranteed
• Cycle Accurate: the Reference is in perfect sync with DUT and transactions are received by comparator at the same point in time.

The Functional and Cycle Accurate references create the conditions for in-order transaction checking, while the LT/AT references require checking of out-of-order transactions. The stream of transactions received by the comparator can be illustrated using UML sequence diagrams. The picture below highlights out-of-order transactions in case of an LT/AT Reference.

The Reference’s main role is to model DUT’s behavior and should not be contaminated with verification code, which means out-of-order transactions should be handled by the Comparator.

Algorithm Implementation

The Comparator will check out-of-order transactions if it treats them symmetrically, with no constraint on which output, Reference or DUT, arrives first. The solution requires two queues (of the same type) and a search-and-compare method. Let’s call the two queues ref_q for Reference transactions and dut_q for DUT transactions. The algorithm is shown in the picture below.

A SystemVerilog implementation of the comparator is:

// declare the implementation ports for incoming transactions
`uvm_analysis_imp_decl(_dut)
`uvm_analysis_imp_decl(_ref)

class comparator extends uvm_component;
  `uvm_component_utils(comparator)

  // implementation ports instances
  uvm_analysis_imp_dut#(my_trans, comparator)           dut_in_imp;
  uvm_analysis_imp_ref#(my_trans, comparator)           ref_in_imp;

  // queues holding the transactions from different sources
  my_trans dut_q[$];
  my_trans ref_q[$];

  function new(string name="comparator", uvm_component parent);
    super.new(name, parent);
    dut_in_imp    = new("dut_in_imp", this);
    ref_in_imp    = new("ref_in_imp", this);
  endfunction

  function void write_dut(my_trans dut_trans);
    search_and_compare(dut_trans, ref_q, dut_q);
  endfunction

  function void write_ref(my_trans ref_trans);
    search_and_compare(ref_trans, dut_q, ref_q);
  endfunction

  function void search_and_compare(my_trans a_trans, ref my_trans search_q[$], ref my_trans save_q[$]);
    int indexes[$];
    
    indexes = search_q.find_first_index(it) with (a_trans.match(it));
    if (indexes.size() == 0) begin
      save_q.push_back(a_trans);
      return;
    end
    // sample a_trans coverage
    search_q.delete(indexes[0]);
  endfunction

  // at the end of the test we need to check that the two queues are empty
  function void check_phase(uvm_phase phase);
    super.check_phase(phase);
    COMPARATOR_REF_Q_NOT_EMPTY_ERR : assert(ref_q.size() == 0) else
      `uvm_error("COMPARATOR_REF_Q_NOT_EMPTY_ERR", $sformatf("ref_q is not empty!!! It still contains %d transactions!", ref_q.size()))
    COMPARATOR_DUT_Q_NOT_EMPTY_ERR : assert(dut_q.size() == 0) else
      `uvm_error("COMPARATOR_DUT_Q_NOT_EMPTY_ERR", $sformatf("dut_q is not empty!!! It still contains %d transactions!", dut_q.size()))
  endfunction
endclass

Optimized Search Implementation

For transactions that contain a big payload you could further optimise the search performance and split it in two separate phases:

• shallow match: identifies transactions that partially match the searched transaction (e.g. does not compare payloads or lists of data, but only some of transaction’s fields)
• deep match: compares the rest of the fields that were not compared during the shallow match (e.g. data payload)

The picture below illustrates this implementation:

In this case search_and_compare() implementation looks like this:

function void search_and_compare(my_trans a_trans, ref my_trans search_q[$], ref my_trans save_q[$]);
  int indexes[$];
  int matching_index = -1;
  
  indexes = search_q.find_first_index(it) with (a_trans.shallow_match(it));
  if (indexes.size() == 0) begin
    save_q.push_back(a_trans);
    return;
  end
  foreach(indexes[i]) begin
    if (a_trans.deep_match(search_q[indexes[i]])) begin
      matching_index = i;
      break;
    end
  end
  // how you handle the case of partial match depends a lot on your context
  // you can trigger an error, warning or just save the transaction in the queue
  if (matching_index == -1) begin
    save_q.push_back(a_trans);
    `uvm_warning("COMPARATOR_INCOMPLETE_MATCH_WRN", $sformatf("Found %d transactions that partially match the searched transaction", indexes.size()))
  end
  // sample a_trans coverage
  search_q.delete(matching_index);
endfunction

That’s all! You can copy&paste the code snippets or download the complete file from AMIQ’s GITHub repository, as you prefer.

Further Study

The article covers the case of a DUT with only one output interface. In case of a DUT with more output interfaces you should multiply this algorithm for each interface that require out-of-order transaction checking.

The search can be further optimized, depending on the particular details of the transactions you need to check.

The current implementation does not check the order of transactions leaving the DUT and that should be achieved using a different approach (e.g. ABV, Formal, separate testbenches for components that decide transaction ordering).

The in-order scenario is a particular case of out-of-order: the timing difference is either 0 (i.e. Cycle Accurate) or the Reference out transactions always come before DUT transactions with a timing difference equal to 0, which means that the presented implementation can be used with in-order transaction checking.

For the sake of simplicity the processing time of a transaction is undefined (i.e. the output transaction can leave the DUT at any moment). If your DUT’s specification restricts the processing time to an interval you will need to enhance the algorithm to support transaction timeout. This is a possible subject for another article.

For further study you can also follow through Verification Academy’s Scoreboards related articles and presentations.