Associative arrays and transaction IDs

Track outstanding reads by ID in an associative array, test for presence with exists, and use the entries left at the end to find responses that never came.

Lesson: 2.3
Time: 20 min
Runs on: Verilator
Check: 5 questions

The DUT returns a read response with ID 9, an ID the testbench never issued, because one bit flipped in the ID path. The scoreboard reads exp_data[9], which does not exist, and gets 0. The response data happens to be 0 as well, from memory that nobody had written, so the check passes. Nothing in the log mentions ID 9.

A response for an ID that was never issued

Reading a key that was never written returns the default value, which can look like a match.

Storage only for the keys you use

An associative array stores elements under keys of a type you choose, and it only holds the keys you have written. int exp_data [int]; maps an int key, here a transaction ID, to the expected data.

This suits sparse key spaces. A scoreboard that tags each read with a 32-bit number has 4 billion possible keys but perhaps 40 outstanding reads, and the array holds just those 40 entries.

Method	What it does
`m[k] = v;`	creates key `k`, or overwrites its value
`m.exists(k)`	1 if key `k` is present, 0 if not
`m.num()` or `m.size()`	number of keys present
`m.delete(k)`	removes key `k`
`m.delete()`	removes every key
`m.first(k)`, `m.next(k)`	step through the keys in order; return 0 when none is left
`foreach (m[k])`	visits every key present, in key order

Associative array methods for int m [int].

Reading a missing key

Reading a key that is not present does not create it and does not stop the simulation. It returns the element type's default value, 0 for an int, and the simulator may print a warning; Verilator 5.052 prints none.

So the value tells you nothing about presence. An ID whose expected data is 0 and an ID that was never issued both read as 0. Call exists first, every time, and treat a missing key as its own kind of failure.

Writing behaves differently from reading. An assignment to a missing key creates it, so a store that uses the wrong ID quietly creates a new entry. The end-of-test check then reports that entry as a read that never completed.

Read and compare

if (exp_data[rid] != rdata)
  $error("ID %0d mismatch", rid);

An unknown ID with data 0 passes, and the stale entry for a real ID is never removed.

Check presence, compare, remove

if (!exp_data.exists(rid))
  $error("unexpected response, ID %0d", rid);
else begin
  if (exp_data[rid] != rdata)
    $error("ID %0d mismatch", rid);
  exp_data.delete(rid);
end

Reports the unknown ID, and removes each entry once it has been answered.

The life of one transaction

Request
If exists(id) is already true, report a duplicate ID instead of overwriting the first expectation. Otherwise store the expected data under id.
Response
If the ID is absent, report an unexpected response. Otherwise compare the data and then delete the key, so that a second response with the same ID is caught.
End of test
Every request should have been answered, so num() must be 0. If it is not, list the leftover IDs with foreach: each one is a read that never completed.

The last step catches the quietest bug of all, a response that never arrives. A test that simply stops after its last request cannot see it, because nothing ever fails.

Several reads with the same ID

An AXI-style bus allows several reads with the same ID to be outstanding at once, answered in request order. A single value per key cannot hold them, so make the value a queue: int exp_q [int][$];.

This combines the previous lesson with this one. The key finds the ID, and the queue keeps the order within that ID. When a queue becomes empty, delete its key, so that num() still counts the IDs with work outstanding.

On a response, check exp_q.exists(rid) first, pop the front of exp_q[rid], and delete the key if that queue is now empty.

A sparse memory model

The same structure models a large memory cheaply. logic [31:0] mem [bit [31:0]]; covers a 4 GB address space, but it stores only the addresses the test has written.

Reading an address that was never written returns the element type's default value. For a logic element that is x, which flags a read of uninitialised memory, just as Module 1 recommends. With a two-state element, the same read returns a plausible 0.

A reference model built this way can also answer a question that a plain array cannot. mem.exists(addr) tells you whether the address was ever written, which is useful when a test must not read memory it never filled.

Choosing the key type

Use a key type that matches the data. Bus IDs and addresses suit an unsigned type such as int unsigned or bit [15:0], and names suit string. The standard visits integer keys in numerical order, using the key type to decide whether a value is negative.

Try it

Reading the missing key 9 returned 0 and left the count at 3. The checker then caught the unknown ID 9, the wrong data for ID 3, and the second response for ID 5, which had already been answered.

The final loop lists ID 1000, a read that never completed. Remove the return after the unexpected-response message and predict what changes.

RUNVerilator · simulator service

Edit the code, then run it

Expected: outstanding=3 missing key reads 0, outstanding still 3 ID 5: match ID 9: unexpected response ID 3: expected a3 got a4 ID 5: unexpected response never answered: ID 1000

Check yourself

Predict the outputPredict the exact output.

module tb;
  int m [int];
  string s;
  initial begin
    m[10] = 1;
    m[2] = 2;
    m[7] = 0;
    foreach (m[k]) s = {s, $sformatf("%0d,", k)};
    $display("%s n=%0d e7=%0d m4=%0d n=%0d", s, m.num(), m.exists(7), m[4], m.num());
  end
endmodule

ConceptHow do you tell an ID that was never issued from an ID whose expected data is 0?

Check whether exp_data[id] is xCompare exp_data.num() before and after reading exp_data[id]Call exp_data.exists(id)Compare exp_data[id] with 0

ConceptA test ends with exp_data.num() equal to 2. What does that tell you?

Nothing: num() reports how much storage the array reservedTwo responses arrived for IDs that were never issuedTwo responses had the wrong dataTwo issued reads never received a response

Read the waveformThe scoreboard stores a key per request and deletes it on the matching response. Which ID is still outstanding at the end of this trace?

Requests and responses by ID

arid and rid only count in cycles where their valid signal is 1.

ID 2ID 4, because it was requested firstID 9, because its response came before ID 4None: three requests and two responses balance out

Spot the bugEach option is the body of function automatic void on_request(int id, int data). It must store the expectation, but report a duplicate (by incrementing dups) when id is already outstanding, and keep the first expectation. Which option loses the first expectation?

if (exp_data.exists(id)) begin
  dups++;
  return;
end
exp_data[id] = data;

if (exp_data.exists(id)) dups++;
exp_data[id] = data;

int n_before;
if (exp_data.exists(id)) begin dups++; return; end
n_before = exp_data.num();
exp_data[id] = data;
if (exp_data.num() != n_before + 1) dups++;

if (!exp_data.exists(id)) exp_data[id] = data;
else dups++;

Remember

An associative array stores only the keys you write, so a huge ID space costs nothing until it is used.
Reading a missing key returns a default value; use exists to test presence.
Check for duplicates on request, check presence on response, and delete each key once it is answered.
Keys left at the end of the test are responses that never arrived; check that num() is 0.
Use a queue as the value when several requests can share one ID.

Practice

Outstanding request lookup Implement · Easy
Duplicate-ID protection Implement · Medium
Out-of-order response matcher Implement · Hard