Sequencer Arbitration

Sequencers · Module 11 · Page 11.2

The Engineering Problem

Module 10.4 covered arbitration policies — FIFO, weighted, strict, user — and the starvation trade-off, from the user's view: pick a mode, set priorities. Module 11.1 opened the sequencer and showed the arbitration queue lives inside uvm_sequencer_base. This chapter goes into the engine itself: how that queue is structured, how a grant is issued from it at each pull, and — crucially — how the engine filters which entries are even candidates. Without this, subtle behavior is inexplicable: why a running sequence never gets driven, how lock/grab and is_relevant actually participate, what start_item is really waiting on inside the queue.

The arbitration engine is a request queue and a selection loop. The queue (m_arb_sequence_q) holds request entries — each a sequence, its priority, and a kind (a normal item request, a lock request, or a grab request). At each grant (when the driver pulls), the engine runs selection: it filters out entries that are blocked (a lock held by another sequence excludes them) or not relevant (a sequence's is_relevant() returned 0), then applies the arbitration mode (Module 10.4) to the remaining candidates, picks one, and grants it — its wait_for_grant returns and it sends its item. So the modes are the selection rule; this is the queue and the filtered selection loop they run on. This chapter is the engine: the request queue, the grant cycle, the candidate filtering (locks, is_relevant), and why a non-relevant sequence is silently excluded.

How does the sequencer's arbitration engine work internally — the request queue of entries (sequence, priority, kind), the per-grant selection that filters out blocked and non-relevant entries before applying the mode, and how do lock/grab and is_relevant participate?

Motivation — why the engine is a filtered selection over a typed queue

The arbitration engine's structure follows from what it must do — choose, fairly and correctly, among heterogeneous, sometimes-ineligible requests:

• Requests are heterogeneous, so the queue is typed. A sequence might want a normal item, or to lock the sequencer, or to grab it. These are different requests, so each queue entry carries a kind (item / lock / grab) alongside the sequence and priority — the engine handles them differently.
• Some requests are ineligible right now, so selection filters first. A sequence blocked by another's lock can't be granted; a sequence that marked itself not relevant shouldn't be. So before applying the mode, the engine filters out ineligible entries — selection is over candidates, not the raw queue.
• The mode chooses among the eligible, so filtering precedes the policy. The arbitration mode (Module 10.4) is the selection rule, but it must run on the eligible set — applying FIFO or weighted to entries that can't be granted would be wrong. So the engine filters, then applies the mode.
• Exclusivity is a request too, so lock/grab go through the queue. Rather than a side mechanism, lock/grab are entries in the same queue with a lock/grab kind — so they're ordered by the same engine (a lock waits its arbitration turn, a grab jumps ahead), and once granted they update the lock state that filters future selections.
• Sequences need to signal eligibility, so is_relevant exists. A sequence may not always want to be granted (a reactive sequence waiting for a condition). is_relevant() lets it exclude itself from selection until ready — which the engine consults during filtering.

The motivation, in one line: the engine must choose among heterogeneous requests (item/lock/grab) of which some are ineligible (blocked by a lock, or self-excluded via is_relevant), so it's a typed request queue with a two-stage selection — filter to candidates, then apply the mode — which is why a non-relevant or blocked entry is simply not in the running.

Mental Model

Hold the arbitration engine as a dispatcher working a run-queue of tickets:

The engine is a dispatcher working a run-queue of tickets, where each ticket says who's asking, how important they are, and what they want — and the dispatcher first crosses off the tickets that can't be served right now, then picks among the rest. Each ticket (queue entry) carries three things: who (the sequence), how important (priority), and what kind of request — "serve me a job" (item request), "reserve the counter for me" (lock), or "reserve it for me right now, ahead of the line" (grab). When it's time to serve someone, the dispatcher doesn't just run the policy on the whole stack — it first crosses off the tickets that can't be served: anyone blocked because someone else holds a reservation (a lock), and anyone who marked their own ticket "not now" (is_relevant = 0). Then, among the remaining tickets, it applies the house rule (FIFO, weighted, strict — Module 10.4) to pick one and serve it. A reservation ticket (lock/grab) is served like any other — the grab jumping to the front, the lock waiting its turn — and once served it changes who's blocked for future rounds. The trap: a ticket whose owner left it marked "not now" forever is crossed off every single round — it's in the stack but never picked, so its owner waits indefinitely, wondering why they're never called.

So the engine is cross-off-then-pick: filter the queue to the eligible tickets (not blocked, relevant), then apply the policy. A ticket stuck "not now" (is_relevant = 0) is the one that's present but perpetually skipped — the engine never even considers it.

Visual Explanation — the request queue and the grant cycle

The defining picture is the queue of typed request entries and the engine that, at each grant, filters and selects from it.

The figure shows the engine as queue + filtered selection. The m_arb_sequence_q holds the request entries — each carrying the sequence, its priority, and a kind (item-request, lock, or grab). At each grant, the engine first filters: consulting the lock state (who currently holds exclusivity), it drops entries that are blocked (a sequence can't be granted while another holds a lock that excludes it) and entries whose is_relevant() returned 0 (self-excluded) — leaving the candidates, the eligible entries. Then it applies the mode (Module 10.4's FIFO/weighted/strict/user) to those candidates, picks one, and grants it — the granted sequence's wait_for_grant returns and it proceeds to send its item. Crucially, lock/grab entries flow through the same queue and engine: a grab entry is selected ahead (jumping the line), a lock entry waits its arbitration turn, and once a lock/grab entry is granted, it updates the lock state that filters future rounds. So the engine is a two-stage loop over a typed queue: filter to candidates (using lock state and is_relevant), then select via the mode. The architectural insight is that the mode (10.4) is only the second stage — the first stage, filtering, is what determines whether an entry is even in the running, which is why a blocked or non-relevant sequence is excluded before the mode ever sees it.

RTL / Simulation Perspective — the queue entry, wait_for_grant, and is_relevant

The engine's internals surface in a few APIs: the request entry's fields, wait_for_grant (what start_item waits on), and is_relevant/wait_for_relevant (self-exclusion). The code sketches them.

// ── THE QUEUE ENTRY (conceptual): what each m_arb_sequence_q element carries ──
//   class uvm_sequence_request:
//     uvm_sequence_base sequence_ptr;   // WHO is requesting
//     int               priority;        // HOW important (for the mode, 10.4)
//     seq_req_t         request;          // KIND: SEQ_TYPE_REQ / SEQ_TYPE_LOCK / SEQ_TYPE_GRAB
//   the engine's m_select_sequence() filters then applies the mode to pick an index
 
// ── wait_for_grant: what start_item blocks on (enqueue a request, wait to be granted) ──
//   inside start_item: the sequence enqueues a SEQ_TYPE_REQ entry and calls wait_for_grant(),
//   which BLOCKS until the engine's selection grants THIS sequence.
 
// ── is_relevant / wait_for_relevant: a sequence excludes itself from selection ──
class reactive_seq extends uvm_sequence #(bus_item);
  bit ready;                              // becomes 1 when this sequence should run
  // the engine calls is_relevant() during FILTERING; 0 ⇒ excluded from candidates
  virtual function bit is_relevant();
    return ready;                          // not relevant (skipped) until ready==1
  endfunction
  // pair it with wait_for_relevant so the engine knows WHEN to re-check (blocks until relevant)
  virtual task wait_for_relevant();
    wait (ready == 1);                     // block until relevant — then re-enter arbitration
  endtask
endclass
//   ✗ if is_relevant() is stuck 0 (ready never set), the engine filters this sequence out of
//     EVERY grant → it is never a candidate → never granted (the DebugLab)

The code names the internal pieces of the engine. The queue entry (uvm_sequence_request, conceptual): each m_arb_sequence_q element carries who (sequence_ptr), how important (priority — the input to the mode, Module 10.4), and what kind (request: SEQ_TYPE_REQ for a normal item, SEQ_TYPE_LOCK, or SEQ_TYPE_GRAB). The engine's selection (m_select_sequence) filters then applies the mode to these entries to pick an index. wait_for_grant is what start_item blocks on internally: the sequence enqueues a SEQ_TYPE_REQ entry and calls wait_for_grant(), which blocks until the engine grants this sequence — so the grant-wait of Module 9.3 is, internally, waiting on this queue selection. is_relevant/wait_for_relevant are the self-exclusion mechanism: the engine calls is_relevant() during filtering, and a 0 excludes the sequence from the candidates — so a reactive_seq that's is_relevant() = 0 until ready is skipped by arbitration until then. The paired wait_for_relevant() tells the engine when to re-check (it blocks until relevant), so the sequencer doesn't spin. The crucial warning (the comment): if is_relevant() is stuck 0 — ready never set — the engine filters the sequence out of every grant, so it's never a candidate and never granted (the DebugLab). The shape to carry: the queue holds typed, prioritized request entries, wait_for_grant is the block on the engine's selection, and is_relevant is the filter input a sequence controls.

Verification Perspective — the two-stage selection

The engine's selection is two stages — filter, then apply the mode — and conflating them is the source of confusing "it's running but never granted" behavior. Separating them is understanding the engine.

The two-stage structure is the key to reasoning about the engine. Stage 1 — filter: from all queue entries, the engine drops two kinds — entries blocked by a held lock (a sequence excluded because another holds exclusivity) and entries whose is_relevant() returned 0 (self-excluded) — producing the candidate set of eligible entries. Stage 2 — apply the mode: the engine runs the arbitration mode (Module 10.4) on the candidates to pick one and grant it. The critical property is that the mode only ever sees the candidates: an entry that fails the filter — blocked or not relevant — is not considered at all, regardless of its priority. This is why "it's running but never granted" is not an arbitration-mode problem: a sequence stuck not relevant is dropped in stage 1, so the mode (stage 2) never sees it — no priority, no mode, would help, because it's not a candidate. Separating the stages explains the whole class of confusing behavior: if a sequence never gets granted, ask first whether it's a candidate (passes the filter — relevant, not lock-blocked), and only then whether it's winning the mode. Filtering decides who's eligible; the mode decides who wins among the eligible. Module 10.4 was entirely about stage 2 (the modes); this chapter adds stage 1 (the filter), and the filter is where the non-obvious exclusions — locks and is_relevant — take effect before any policy runs.

Runtime / Execution Flow — a grant cycle from enqueue to send

At run time, one grant cycle runs from a sequence enqueuing its request to sending its item. Following it shows where wait_for_grant, filtering, and the mode each act.

The grant cycle ties the engine's pieces to the handshake you already know. Step 1, a sequence's start_item enqueues a request entry (SEQ_TYPE_REQ, with its sequence/priority) into m_arb_sequence_q and calls wait_for_grant, which blocks — this is the internal reality of the start_item grant-wait (Module 9.3): the sequence is in the queue, waiting to be selected. Step 2, when the driver pulls (get_next_item), the engine runs stage-1 filtering: it drops entries blocked by a held lock and entries with is_relevant() == 0, leaving the candidates. Step 3, it runs stage-2: applies the mode (Module 10.4) to the candidates, picks one, and grants it — the chosen sequence's wait_for_grant returns, releasing it. Step 4, that sequence sends its item (finish_item, Module 9.4) and its entry is removed from the queue; the cycle repeats at the next pull. So the engine view decomposes the familiar flow: wait_for_grant is the block (the sequence sits in the queue), filtering + mode is the selection (the engine choosing a candidate), and the grant is the release (wait_for_grant returns). The non-obvious failures map to steps 2–3: a sequence stuck non-relevant never passes step 2 (filtered), so its wait_for_grant from step 1 never returns — it sits in the queue forever, a candidate-of-none. The cycle makes concrete that every start_item is a trip through this engine, and a sequence that "never gets granted" is one whose entry is perpetually filtered out before the mode runs.

Waveform Perspective — a grant cycle with a filtered entry

The engine's two-stage selection is visible on a timeline: at each pull, some entries are candidates and some are filtered out, and the mode grants among the candidates — while a non-relevant entry waits, never selected.

The waveform shows filtering acting before the mode, every grant. Two sequences are enqueued: S, which is relevant, and R, whose is_relevant() returns 0 (it marked itself not now). At each pull (when the driver requests a grant), the engine filters first: S is a candidate, but R is dropped — R_filtered stays high across every grant, meaning R is excluded from the candidate set every single time. The mode then runs on the candidates and grants S (granted shows S at each pull), so S's items drive. R, by contrast, is never granted — R_grant stays 0 for the whole trace — because it's filtered out in stage 1, before the mode ever considers it, regardless of its priority. This is the visual proof of the chapter's core point: R's wait_for_grant never returns not because it loses the mode (Module 10.4's starvation, where it competes and loses), but because it's never a candidate — a different failure, in stage 1. The picture to carry: at each grant the queue is split into candidates and filtered-out entries, the mode acts only on the candidates, and an entry stuck not-relevant (or lock-blocked) sits perpetually on the filtered-out side — present in the queue, but never selected, which is exactly the silent-exclusion bug the DebugLab dissects.

DebugLab — the running sequence that was never granted

class reactive_seq:
  bit ready;                       // intended to gate when the sequence is relevant
  function bit is_relevant(); return ready; endfunction   // 0 until ready==1
  // ✗ but `ready` was NEVER set to 1 (the condition that should set it never fired)
 
inside the engine, every grant:
  filter stage: is_relevant() == 0 → DROP this sequence from the candidate set
  → it is never a candidate → the mode never sees it → never granted
  → its wait_for_grant (inside start_item) never returns → start_item blocks forever
 
NOTE: this is NOT starvation (losing the mode); it is EXCLUSION (failing the filter).
      priority/mode changes do nothing — it isn't a candidate at all.
 
fix — ensure is_relevant() returns 1 when the sequence should run, and pair with wait_for_relevant:
  function bit is_relevant(); return ready; endfunction
  task wait_for_relevant(); wait (ready == 1); endtask   // block until relevant (engine re-checks)
  // and make sure `ready` actually gets set (the gating condition must fire)

Common Mistakes

• Overriding is_relevant() with a gating flag that's never set. The sequence is filtered out of every grant — never a candidate, never granted; ensure the gate fires and pair with wait_for_relevant().
• Confusing exclusion with starvation. Exclusion (stage-1 filter: is_relevant/lock) and starvation (stage-2 mode: priority) are different — changing the mode won't fix an excluded sequence.
• Forgetting wait_for_relevant(). Without it, the engine can't efficiently know when to re-check a non-relevant sequence; the two methods are meant to be used together.
• Assuming priority affects a filtered entry. The mode (and priority) only act on candidates; a blocked or non-relevant entry is dropped before priority matters.
• Reimplementing arbitration instead of using the engine. The queue, filtering, and selection live in uvm_sequencer_base; override the mode (10.4) or is_relevant, not the whole engine.
• Treating lock/grab as outside the queue. They're entries in the same queue with a lock/grab kind, ordered by the same engine — not a separate mechanism.

Senior Design Review Notes

Interview Insights

Exercises

1. Describe an entry. State the three fields each arbitration queue entry carries and what each is used for in the engine.
2. Trace the two stages. For a queue with one lock-blocked entry, one non-relevant entry, and two relevant entries, describe which reach the mode and how a winner is chosen.
3. Diagnose the exclusion. A started sequence's start_item never returns while others run, and changing the mode does nothing. Name the likely cause and the fix.
4. Exclusion vs starvation. Explain how you'd tell whether a never-granted sequence is excluded (stage 1) or starved (stage 2), and why the fix differs.

Summary

• The arbitration engine is a request queue (m_arb_sequence_q) of entries — each a sequence + priority + kind (item request / lock / grab) — and a per-grant selection loop over it.
• Selection is two stages: filter (drop entries blocked by a held lock or with is_relevant() == 0) → apply the mode (Module 10.4) to the candidates and grant one. The mode only ever sees the candidates, so a filtered entry is excluded regardless of priority.
• lock/grab are entries in the same queue (lock/grab kind): a grab jumps ahead, a lock waits its turn, and once granted they update the lock state that filters future grants — exclusivity is a queue effect, not a side mechanism.
• wait_for_grant is what start_item blocks on internally (the sequence sits in the queue awaiting selection), and is_relevant/wait_for_relevant let a sequence self-exclude from candidacy until ready.
• The durable rule of thumb: understand arbitration as filter-then-select — a sequence is granted only if it's a candidate (relevant and not lock-blocked) and then wins the mode — so a never-granted sequence stuck is_relevant() == 0 is an exclusion (stage-1) failure no priority change fixes, distinct from starvation (stage-2); fix is_relevant/wait_for_relevant, not the mode.

Next — Request Management: the engine grants requests from the queue; the next chapter examines how those requests — and the responses that come back — are managed: the request/response queues, IDs, and the bookkeeping that pairs each request with its answer.