Queues and ordering

A queue grows and shrinks at both ends

A queue is an ordered list whose length changes as you add and remove elements. You declare it with a dollar sign in the brackets, as in int exp_q [$];, and it starts empty.

Its methods work at either end. push_back adds at the end and pop_front removes from the front, so using that pair gives first-in, first-out order, or FIFO. Using push_back with pop_back gives last-in, first-out order instead, like a stack.

You never call new for a queue. Indexing works as it does for arrays, and foreach visits the elements from front to back. A range gives a new queue: q[1:$] holds every element except the first.

Guard every pop

Popping an empty queue does not stop the simulation. It returns the element type's default value, 0 for an int, and the simulator may print a warning. Icarus Verilog prints one, but Verilator 5.052 stays silent.

In a scoreboard, an empty queue at the moment a response arrives is itself a failure: the DUT sent a response that nobody asked for. Check size() first, and report that case by name instead of comparing against a made-up 0.

exp = exp_q.pop_front();      // 0 if empty
if (rdata != exp)
  $error("expected %0h got %0h", exp, rdata);

if (exp_q.size() == 0)
  $error("unexpected response %0h", rdata);
else begin
  exp = exp_q.pop_front();
  if (rdata != exp)
    $error("expected %0h got %0h", exp, rdata);
end

Order is part of the protocol

A single FIFO of expectations is correct for a bus that returns every response in request order. For that bus, popping the front and comparing is the whole check, and it also catches responses that come back out of order.

An AXI-style bus makes a weaker promise. Responses that share an ID return in request order, but responses with different IDs may overtake each other. The checker must allow the second kind of reordering while still catching the first.

In the opening story, the bus returned B before A. A and B have different IDs, so that order is legal, yet the single queue compared B with A and failed. Had two reads with ID 1 come back swapped, the same check would have failed for a good reason.

Sorting the responses before comparing them looks like a fix, but it hides real bugs. If two reads with the same ID come back swapped, a sorted comparison still passes.

One queue per ID

The structure that matches the rule is one FIFO per ID. With 4-bit IDs, int exp_q [16][$]; declares a fixed array of 16 queues, and exp_q[3] is the queue for ID 3.

A request with ID arid pushes its expected data onto exp_q[arid]. A response with ID rid checks exp_q[rid].size(), then pops the front of that queue only. Responses for other IDs never touch it, so they may arrive in any order.

Replay the opening story with this structure. The request for ID 1 pushes A onto exp_q[1], and the request for ID 2 pushes B onto exp_q[2]. Response B pops exp_q[2] and matches, then response A pops exp_q[1] and matches.

At the end of the test, every queue must be empty. A leftover entry is a read that never got its response. When IDs are too wide for a fixed array, the next lesson replaces the outer array with an associative array.

Queues never block

Queue methods act immediately. pop_front never waits for an element to arrive, so a loop that polls an empty queue at the same simulation time can hang the run. Producer and consumer processes need a mailbox, which Module 3 covers.

A bounded queue sets a highest index: int q [$:15] holds at most 16 elements. A push beyond that limit is dropped, with a warning in Icarus and silently in Verilator 5.052, so a bounded queue does not slow down the sender.

Try it

The single queue compares the ID 2 response with the oldest expectation, which belongs to ID 1, and reports a false mismatch. The per-ID queues match each response with its own ID, and the second ID 1 response is reported as unexpected.

Add a second request for ID 1 with data 'ha3, then make the ID 1 responses arrive as a3 before a1. Predict which line reports the error.

Check yourself

module tb;
  int q [$];
  initial begin
    q.push_back(1);
    q.push_back(2);
    q.push_front(3);
    void'(q.pop_back());
    q.push_back(4);
    $display("%0d %0d %0d", q[0], q[$], q.size());
  end
endmodule

int e;
if (exp_q[rid].size() == 0) return 0;
e = exp_q[rid][0];
exp_q[rid].delete(0);
return e == rdata;

return exp_q[rid].pop_front() == rdata;

if (exp_q[rid].size() == 0) return 0;
return exp_q[rid].pop_front() == rdata;

if (exp_q[rid].size() != 0) return exp_q[rid].pop_front() == rdata;
return 0;

Practice

• First FIFO mismatch Implement · Easy
• Bounded queue operations Implement · Medium