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

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
`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:

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
    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.


Comments

Taahir March 11th, 2016 06:33:29

Awesome, flow chart is what I do.

Keep posting. It will be really helpful.


    Stefan Birman March 15th, 2016 12:40:14

    Thank you.


Efrat Shneydor March 21st, 2016 09:05:03

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.

thanks,
Efrat

<'
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 {
            save_q.add(a_trans);
        } else {
            search_q.delete(match_index);
        };
    };
    
    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" );
    };
};
'>

    Stefan Birman March 21st, 2016 22:14:16

    Thank you Efrat for completing the article with the e-language solution.

    Regards,
    Stefan


mahendran devarajlu November 3rd, 2017 04:02:41

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


    Stefan Birman November 8th, 2017 14:52:05

    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!


Robert Ruidisch August 16th, 2018 14:54:08

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?


Stefan Birman August 21st, 2018 12:21:57

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 == atrans.data);
   endfunction
endclass

Taahir September 4th, 2019 18:41:54

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.


Mihai Voda October 3rd, 2019 18:45:45

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(…);”
return;


    Taahir October 30th, 2019 12:12:32

    Finally I undertsood Mihai Voda , thank you for the pin point describe.


Sharadha October 14th, 2019 21:25:10

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 Comment:

Your comment will be visible after approval.

(will not be published)

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