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:


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

Verification Environment

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.

UML transaction sequence Diagram

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.

Algorithm Implementation

A SystemVerilog implementation of the comparator is:

// declare the implementation ports for incoming transactions

class comparator extends uvm_component;

  // 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);, parent);
    dut_in_imp    = new("dut_in_imp", this);
    ref_in_imp    = new("ref_in_imp", this);

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

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

  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
    // sample a_trans coverage

  // at the end of the test we need to check that the two queues are empty
  function void check_phase(uvm_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()))

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:

Optimized Algorithm 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
  foreach(indexes[i]) begin
    if (a_trans.deep_match(search_q[indexes[i]])) begin
      matching_index = i;
  // 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
    `uvm_warning("COMPARATOR_INCOMPLETE_MATCH_WRN", $sformatf("Found %d transactions that partially match the searched transaction", indexes.size()))
  // sample a_trans coverage

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.


12 Responses

  1. hi, Stefan,

    Very nice and elegant solution.
    If it’s ok with you – I’d like to present to the Specman users among your readers, the e implementation of your algorithm.


    unit comparator {
        ref_data_in : in interface_port of tlm_analysis of my_trans 
          using prefix =ref_ is instance;
        dut_data_in : in interface_port of tlm_analysis of my_trans 
          using prefix =dut_ is instance;
        !ref_q : list of my_trans;
        !dut_q : list of my_trans;
        ref_write(trans: my_trans) is {
            search_and_compare(trans, FALSE); 
        dut_write(trans: my_trans) is {
            search_and_compare(trans, TRUE); 
        search_and_compare(a_trans : my_trans, is_dut:bool) is {
            var search_q := is_dut ? ref_q : dut_q;
            var save_q   := is_dut ? dut_q : ref_q;
            var match_index := search_q.first_index(a_trans.match(it));
            if match_index == UNDEF {
            } else {
        check() is also {
            check that ref_q is empty else
              dut_error("ref_q contains ", ref_q.size(), " transactions at end of test" );
            check that dut_q is empty else
              dut_error("ref_q contains ", dut_q.size(), " transactions at end of test" );
    1. Thank you Efrat for completing the article with the e-language solution.


  2. Are shallow_match and deep_match implemented in my trans? Can you please send the implementation for them?

    1. The two methods are defined in the transaction class.

      I cannot provide an implementation for your particular case, but it should not be a problem for you to implement it yourself: it’s just a method that returns the result of comparing(i.e. ==) the fields of a transaction.

      Good luck!

  3. I relate to the previous question about the match methods.
    An example implementation of the comparing method would be very much appreciated. What is the expected return value?

  4. The match methods’ return type is bit/boolean: ‘1’ if the match is successful and ‘0’ otherwise.
    There is no “universal” implementation that can be used for any transaction class.

    I present a simple implementation for an APB transaction which you should understand and apply to your particular transaction matching:

    class apb_trans;
       bit rnw;
       bit [15:0] address;
       bit [31:0] data;
       function bit match(apb_trans atrans);
          return (rnw == atrans.rnw && address == atrans.address && data ==;
  5. Hi Stefan,

    I quite do not understand the complete implementation of search and compare method.

    Since one save_q is used, how do we differentiate that dut transaction or the reference transaction.

    Could you please explain the method.

  6. If you look at how the “search_and_compare” function is called you will notice that when a write is incoming from the “dut_in_imp” you will call with “search_q” referenced to “ref_q” and the “save_q” referenced to “dut_q”. (vice versa when write is incoming from ref_in_imp)

    And you will see that in “search_and_compare” function, when a transaction is not found when comparing, it will be moved back in the queue in order to be able to search for it later, that’s why it is called “out of order checking”.

    e.g. in search_and_compare function:

    if (indexes.size() == 0) begin
    save_q.push_back(a_trans); // a_trans is pushed back to “dut_q” if function was called in “write_dut(…);”

  7. Questions 1) If two transactions from the same index_id/port_id are sent on one stream, in other words there is no unique_id to every transaction on a stream, then will the same scoreboard work? 2) I thought that if we follow the UVM guidelines both transaction and sequence id are generated automatically, we can identify any seq_item as a unique item. The method set_id_info(req) is doing this. Then, irrespective of in-order/OOO can we not compare any two transactions?

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Subscribe to our newsletter

Do you want to be up to date with our latest articles?