Sequence Scheduling

Sequencers · Module 11 · Page 11.4

The Engineering Problem

The previous chapters covered the sequencer's mechanisms individually — arbitration (Modules 10.4, 11.2), locks/grabs (9.2, 10.3), relevance (11.2). But in a real testbench they run together, and what you actually observe — the order in which concurrent sequences' items reach the driver over time — is not any one mechanism; it's their composition. This emergent order is the schedule, and reasoning about it (Why did the interrupt wait? Why did these items interleave but not those?) requires seeing how arbitration, locks, and relevance interact over the run, not in isolation.

Sequence scheduling is the sequencer's emergent timeline, produced by three mechanisms composing. Arbitration picks among candidates per grant — shaping the mix by mode and priority (10.4). Locks/grabs create exclusivity windows — carving atomic blocks of one sequence's subtree into the interleaving (10.3). Relevance (is_relevant) gates which sequences are candidates at all — letting sequences schedule themselves in and out dynamically (11.2). The schedule is the interleaving these three weave together: an arbitrated mix, punctuated by lock windows, over a candidate set that changes as relevance changes. No single mechanism "is" the schedule — it emerges. This chapter is that emergence: how the three compose into a timeline, and the priority inversion that arises when they interact — a low-priority sequence's lock blocking a high-priority one.

How does the sequencer's schedule — the order concurrent sequences' items reach the driver over time — emerge from arbitration, locks/grabs, and relevance composing, and how does a low-priority sequence holding a lock cause priority inversion?

Motivation — why scheduling is emergent, not a single rule

The schedule must be understood as composition because each mechanism handles a different aspect of "what runs when," and they can only be reasoned about together:

• Arbitration decides the mix, but only among the eligible. The mode and priorities (Module 10.4) shape which sequence's item is favored per grant — but arbitration runs only on candidates (Module 11.2). So the mix it produces depends on who's a candidate, which is not arbitration's job.
• Locks decide atomicity, overriding the mix. A lock (Module 10.3) makes one sequence's subtree run uninterrupted — overriding the arbitrated mix for the lock's duration. So the schedule isn't a smooth arbitrated interleave; it's punctuated by atomic lock windows that suspend normal arbitration.
• Relevance decides candidacy, changing over time. is_relevant (Module 11.2) lets a sequence exclude itself until ready — so the candidate set arbitration chooses from changes over the run as sequences become relevant or not. The schedule's participants aren't fixed.
• The three interact, producing behavior none has alone. A lock held by a low-priority sequence blocks a high-priority one (priority inversion) — a behavior that arises only from locks and priority interacting. You can't predict it from arbitration or locks alone; it's emergent.
• So the schedule must be reasoned about as a whole. "Why did this run when it did?" has no single-mechanism answer — you trace candidacy (relevance), then exclusivity (locks), then the pick (arbitration), together, at each grant.

The motivation, in one line: "what runs when" is split across three mechanisms — arbitration (the pick), locks (atomicity, overriding the pick), relevance (candidacy, feeding the pick) — that interact and produce emergent behavior (like priority inversion), so the schedule is their composition over time, not any one rule.

Mental Model

Hold the schedule as the performance an orchestra actually plays, woven from three influences:

The schedule is the performance as actually played — woven from who's ready to play, who the conductor picks, and who's in an uninterrupted solo — so no single influence is "the music"; the music emerges from all three. Who's ready is relevance: a player with their instrument up is a candidate; one resting (is_relevant = 0) is not in the running, and players raise and lower their instruments over the piece. Who the conductor picks is arbitration: among the ready players, the conductor cues one per beat, favoring some (priority) by the chosen rule (FIFO/weighted/strict). An uninterrupted solo is a lock: when a player has a solo, the conductor steps back and lets only that player play until the solo ends — overriding the normal cueing. The performance you hear — the actual sequence of notes over time — is the weave of these: a cued mix among the ready players, punctuated by solos, with players entering and leaving readiness. And here's the catch that surprises: if a minor player takes a long solo (a low-priority sequence holds a lock), even the lead (a high-priority sequence) must wait for the solo to end — the solo overrides rank. The conductor can't cut in; the lead sits silent behind the minor player's solo. That is priority inversion, and it's audible only because solos and rank interact.

So the schedule is woven, not dictated: relevance sets who's ready, arbitration cues among them, locks carve solos that override cueing — and the timeline emerges. The surprising notes (a lead waiting behind a minor player's solo) come from the interaction, which is why you reason about all three together.

Visual Explanation — the schedule emerging from three mechanisms

The defining picture is three mechanisms feeding one timeline: relevance, arbitration, and locks composing to produce the schedule the driver sees.

The figure shows the composition that yields the schedule. Relevance (is_relevant) gates candidacy — it decides which sequences are even in the running, and because relevance changes over time, the candidate set is dynamic. Arbitration (mode/priority) picks among the candidates per grant — it shapes the mix (favoring some by priority under the chosen mode), but only over whoever relevance left as candidates. Locks/grabs override the pick — when a lock is held, normal arbitration is suspended and the lock holder's subtree runs exclusively, carving an atomic window into the stream. These three feed into the schedule — the emergent timeline — which the driver sees as its item stream. The crucial reading is that the schedule is downstream of all three: it's not produced by arbitration (which only picks among candidates), nor by locks (which only override sometimes), nor by relevance (which only gates) — it's the result of their composition at each grant over the run. So to predict or explain the schedule, you trace the composition: who's a candidate now (relevance), is a lock overriding (locks), who wins the pick (arbitration) — and the sequence of these decisions over time is the schedule. The diagram is the chapter's thesis in one picture: three mechanisms, one emergent timeline, and understanding scheduling means understanding the composition, not the parts.

RTL / Simulation Perspective — the three knobs that shape the schedule

The schedule is shaped by three sets of controls — one per mechanism — set across the sequencer and sequences. The code shows the knobs that, together, determine the timeline.

// ── (1) ARBITRATION: the mode + per-sequence priority shape the MIX ──
env.agent.sequencer.set_arbitration(UVM_SEQ_ARB_WEIGHTED);   // mode (Module 10.4)
fork
  bg.start (sqr, null, /*priority*/ 100);                    // low priority
  irq.start(sqr, null, /*priority*/ 500);                    // high priority
join
 
// ── (2) LOCKS/GRABS: carve ATOMIC WINDOWS into the interleaving (Module 10.3) ──
task atomic_seq::body();
  grab(m_sequencer);            // exclusivity window begins — suspends arbitration for others
  `uvm_do(a) `uvm_do(b)         // these run atomically, a solo in the schedule
  ungrab(m_sequencer);          // window ends — arbitration resumes
endtask
 
// ── (3) RELEVANCE: gate CANDIDACY dynamically (Module 11.2) ──
class reactive_seq extends uvm_sequence #(bus_item);
  bit ready;
  virtual function bit is_relevant(); return ready; endfunction   // not a candidate until ready
  virtual task wait_for_relevant(); wait (ready == 1); endtask     // enters the schedule when ready
endclass
 
// ── the SCHEDULE is what these three produce TOGETHER over the run ──
//   relevance gates candidates → arbitration picks the mix → a lock (if held) overrides
//   ⚠ EMERGENT HAZARD: a low-priority sequence holding a lock blocks a high-priority one
//      (priority inversion) — the lock overrides priority (the DebugLab)

The code shows the three knobs whose interaction is the schedule. Arbitration (control 1): set_arbitration(mode) on the sequencer plus per-sequence priority shape the mix — under WEIGHTED, irq (500) is favored over bg (100) among candidates (Module 10.4). Locks/grabs (control 2): grab/ungrab (or lock/unlock) carve an atomic window — while atomic_seq holds the grab, its a and b run as a solo, suspending arbitration for others (Module 10.3). Relevance (control 3): is_relevant/wait_for_relevant gate candidacy — reactive_seq is not a candidate until ready, so it enters the schedule dynamically (Module 11.2). The schedule (the final comment) is what these produce together: at each grant, relevance gates the candidates, arbitration picks the mix, and a lock (if held) overrides the pick. And the emergent hazard (the warning): because a lock overrides priority, a low-priority sequence holding a lock blocks even a high-priority one — priority inversion, a behavior no single knob produces (the DebugLab). The shape to carry: the schedule has three knobs — mode/priority (mix), locks (atomicity), relevance (candidacy) — and the timeline is their joint effect, including emergent interactions like priority inversion that you only see when you turn them together.

Verification Perspective — three scheduling patterns

The three mechanisms produce recognizable scheduling patterns. Knowing the patterns — and which mechanism dominates each — is how you read a schedule and design one.

The three patterns are how the mechanisms show up in a schedule. Fair mix (arbitration-dominated): under WEIGHTED or RANDOM, arbitration produces an interleaved stream where every candidate gets turns — items from concurrent sequences alternate, favored by priority but not monopolized (no starvation). This is the default texture of a multi-sequence schedule. Atomic windows (lock-dominated): a lock/grab carves an uninterrupted block of one sequence's items into the stream — a solo where the interleaving pauses and only the lock holder's items appear, then resumes. This is how atomic operations (read-modify-write) appear in the schedule. Dynamic candidacy (relevance-dominated): as sequences' is_relevant changes, they enter and leave the schedule — a reactive sequence appears in the mix when it becomes relevant and vanishes when it's not — so the participant set shifts over time. Real schedules combine all three: a fair mix (arbitration), punctuated by atomic windows (locks), over a shifting candidate set (relevance). The verification value is reading a schedule: an interleaved region is arbitration; an uninterrupted block is a lock; a sequence appearing/disappearing is relevance. And designing one: choose the mode for the mix, locks for the atomic parts, relevance for the dynamic parts. The patterns are the vocabulary for talking about schedules — and recognizing which mechanism produced a given stretch of the timeline is the core scheduling skill.

Runtime / Execution Flow — the composition at each grant

At run time, the three mechanisms compose at each grant in a fixed order: relevance gates, locks override, arbitration picks. Following that order shows how the timeline is built grant by grant.

The per-grant composition is the engine of the schedule, and its fixed order is what makes the timeline predictable (given the inputs). Step 1 — relevance gates: only sequences with is_relevant() == 1 (and not blocked by another's lock) are candidates (Module 11.2's filter). This feeds the decision — it sets who's even considered. Step 2 — lock overrides: if a lock/grab is held, the holder's subtree is selected directly, suspending normal arbitration (Module 10.3) — the lock short-circuits the pick. Step 3 — arbitration picks: if no lock is held, arbitration applies the mode and priorities to the candidates and picks one (Module 10.4). Step 4 — the item reaches the driver, and the cycle repeats at the next grant. The schedule is the sequence of these composed decisions over time: at each grant, relevance narrows, a lock may override, arbitration picks. This fixed order explains the emergent behaviors: priority inversion arises at step 2 — a lock held by a low-priority sequence overrides the step-3 arbitration, so a high-priority candidate never reaches step 3 while the lock is held (it's blocked at step 1 or overridden at step 2). Dynamic participation arises because step 1 re-evaluates relevance every grant, so the candidate set shifts. The key runtime insight is that the schedule is not computed once — it's re-composed at every grant from the current relevance, lock, and arbitration state, so it responds to changes (a lock taken, a sequence becoming relevant) as they happen. Trace this composition grant by grant and you can explain any schedule.

Waveform Perspective — a schedule with all three mechanisms

The emergent schedule is best seen on a timeline showing all three mechanisms at once: an arbitrated interleave, a lock window, and a sequence entering as it becomes relevant.

The waveform shows the schedule as a woven timeline, with each stretch readable by its mechanism. Early (cycles 0–2), granted alternates A, B, A — an arbitrated interleave, the mix of two candidates (arbitration). Then (cycles 3–5), A grabs the sequencer (lock high), and granted shows only A — A's items run atomically, a solo with no B, because the lock overrides the arbitrated mix (locks). After the ungrab (cycle 6+), a third sequence C has become relevant (C_relevant rose at cycle 6), so granted now includes C among A and B — C joined the schedule dynamically because its relevance changed (relevance). So the one timeline contains all three patterns: an interleave (arbitration), a lock window (locks), and a new participant (relevance) — and you read it by attributing each stretch to its mechanism. The picture is the chapter's synthesis: the schedule is not arbitration or locks or relevance — it's the weave, and any real timeline is a composition of interleaves, solos, and shifting participants. The skill the waveform builds is reading the weave: see an alternating stretch and think arbitration; see an uninterrupted block and think lock; see a sequence appear and think relevance became true — and that decomposition is how you explain (and the DebugLab, predict the hazards of) any sequencer schedule.

DebugLab — the interrupt that waited behind a low-priority lock

bg_seq (priority 100):  grab(sqr);  ...long atomic operation...  ungrab(sqr);   // holds a LOCK
irq_seq (priority 500): wants the sequencer immediately (highest priority)
 
per grant, while bg_seq holds the lock:
  step 1 (relevance/filter): irq is filtered out as LOCK-BLOCKED (bg holds exclusivity)
  step 2 (lock override): bg's subtree is selected — arbitration is SUSPENDED
  step 3 (arbitration): never reached for irq → irq's priority is IRRELEVANT while locked
 
→ irq (priority 500) WAITS behind bg (priority 100) for the lock's whole duration
  = PRIORITY INVERSION: a low-priority lock holder blocks a high-priority sequence
  (the delay is intermittent — only when bg happens to hold the lock when irq becomes ready)
 
fix — minimize the inversion window (locks override priority, so keep them short / placed well):
  (a) keep the locked region SHORT — grab → minimal atomic items → ungrab promptly
  (b) don't hold a long lock in a low-priority sequence that a critical sequence must preempt
  (c) if the atomic operation can tolerate it, use finer-grained locks (shorter windows)
  (d) reconsider whether the operation truly needs a lock, or whether the critical path can avoid it

Common Mistakes

• Assuming priority alone governs the schedule. A lock overrides priority, so a low-priority lock holder blocks higher-priority sequences (inversion); reason about locks and priority together.
• Holding long locks in low-priority sequences. The lock's duration is the inversion window for any critical sequence waiting; keep locked regions short.
• Reading a schedule by one mechanism. An interleave is arbitration, a block is a lock, an appearing sequence is relevance — attribute each stretch to its mechanism, not all to arbitration.
• Forgetting relevance changes the candidate set. Sequences enter/leave the schedule as is_relevant changes; the participant set isn't fixed over the run.
• Expecting a single-mechanism explanation for emergent behavior. Priority inversion (and similar) arise from interaction; trace the per-grant composition (relevance → lock → arbitration).
• Ignoring timing/seed dependence. Random arbitration and timing make the schedule seed-dependent; a given seed reproduces it, but the schedule varies across seeds.

Senior Design Review Notes

Interview Insights

Exercises

1. Read the schedule. Given a timeline with an alternating region, an uninterrupted block, and a sequence appearing partway through, attribute each stretch to its mechanism.
2. Trace the composition. For one grant with a held lock, describe what happens to a high-priority candidate at each step (relevance/filter, lock, arbitration).
3. Diagnose the inversion. A high-priority sequence is intermittently delayed though its priority is correct. Name the cause, why mode/priority changes don't fix it, and the remedy.
4. Design a schedule. For "fair traffic mix with occasional atomic register accesses, plus an error sequence that runs only when a flag is set," name which mechanism handles each part.

Summary

• Sequence scheduling is the emergent interleaving of concurrent sequences' items over time — produced by three mechanisms composing, not by any one alone.
• The three are arbitration (picks the mix among candidates by mode/priority, Module 10.4), locks/grabs (carve atomic windows that override the pick, Module 10.3), and relevance (is_relevant gates candidacy, shifting over time, Module 11.2).
• At each grant they compose in order: relevance gates the candidates → a held lock overrides the pick → arbitration picks among the candidates — and the sequence of these decisions over the run is the schedule.
• Read a schedule by mechanism: an interleave is arbitration, an uninterrupted block is a lock, a sequence appearing/disappearing is relevance — and design one by choosing the mode (mix), locks (atomicity), and relevance (dynamics).
• The durable rule of thumb: reason about the schedule as the composition of arbitration, locks, and relevance — because emergent hazards like priority inversion (a low-priority lock holder blocking a high-priority sequence, unfixable by priority/mode since locks override arbitration) only appear when the mechanisms interact — so keep lock windows short and off critical paths, and trace the per-grant composition to explain any timeline.

Next — Debugging Sequencers: the architecture, arbitration, request management, and scheduling can all go wrong in subtle ways; the final chapter of the module collects the techniques for debugging sequencers — tracing grants and locks, diagnosing hangs and stalls, and the tools that make the sequencer's internal state visible.