The Scheduler and Dispatcher
One SIMT core
runs one block of four threads. A GPU runs a launch: "here is a kernel, run it as 6
blocks of 4" — or six thousand blocks, on hardware the programmer has never seen. The circuit
that turns one into the other is the dispatcher, and it is almost insultingly
small: a counter, a bitmask, and a handshake. Yet this little machine carries the deepest promise
in GPU computing — transparent scalability. The same kernel binary saturates a
chip with two cores or two hundred, because software describes work (blocks) and the
dispatcher, at runtime, matches work to whatever hardware exists. Where the
warp
scheduler juggles warps within a core cycle by cycle, the dispatcher deals
blocks between cores — the outer loop of the whole GPU.
The dispatcher's whole job
A launch hands the dispatcher three numbers: the kernel's start address, the total number of
blocks, and the block size. From then on it runs a loop you could explain to a shift manager at a
delivery depot:
- keep a next-block counter — the number of the next parcel of work not yet
handed out;
- keep a free-core bitmask — one bit per core, busy or free;
- whenever a core is free and blocks remain: assign — latch the block number
into the core's
%blockIdx, pulse its start signal, mark it busy, bump the
counter;
- whenever a core raises done (its block's threads all hit
RET):
mark it free again and count the finished block;
- when finished blocks — not merely handed-out blocks — equal the total,
raise kernel-complete.
That is the scalability contract, and it really is about fifty lines of RTL:
logic [7:0] next_block, done_blocks;
logic [NUM_CORES-1:0] core_busy; // the free-core bitmask
wire [NUM_CORES-1:0] free = ~core_busy;
wire [NUM_CORES-1:0] grant = free & (~free + 1); // lowest free core, one-hot
always_ff @(posedge clk) begin
if (!rst_n) begin
next_block <= '0; done_blocks <= '0; core_busy <= '0;
end else begin
for (int i = 0; i < NUM_CORES; i++) begin
if (core_done[i]) begin // a block finished: recycle the core
core_busy[i] <= 1'b0;
done_blocks <= done_blocks + 1;
end
if (grant[i] && next_block < total_blocks) begin
core_busy[i] <= 1'b1;
core_block_idx[i] <= next_block; // %blockIdx LATCHED into the core
core_start[i] <= 1'b1;
next_block <= next_block + 1;
end
end
end
end
assign kernel_done = (done_blocks == total_blocks);
The one flourish is the arbitration line. free & (~free + 1) is
the classic lowest-set-bit trick — x \,\&\, (-x) in two's
complement — which isolates the lowest 1 in the mask as a one-hot grant. If cores 1 and 3 are
free (free = 1010), the grant is 0010: core 1 wins, deterministically,
with zero sequential logic. A priority arbiter in one line of arithmetic.
- a launch = kernel address + block count + block size; the dispatcher owns
the loop over blocks;
- state: a next-block counter, a free-core bitmask, a
done-block counter;
- assignment latches
%blockIdx into the chosen core at grant
time;
- more blocks than cores ⇒ cores are recycled — the same silicon runs 6
blocks or 6 million;
- kernel-complete fires when done = total, not when
dispatched = total.
Why block-level dispatch works at all
Notice what the dispatcher doesn't have: any channel for core 0 to talk to core 1. It
can get away with this because the programming model's blocks are independent by
contract — a kernel is only well-formed if its blocks can run in any order, on any
cores, simultaneously or one after another, without communicating. Our vector-add blocks each own
their private slice of the arrays; nothing block 3 does can matter to block 4. That contract is
what the dispatcher's dumbness is buying: because it may place blocks anywhere, anytime,
the same launch saturates any number of cores — scheduling stays a local, per-core affair, and
scaling the GPU means literally pasting in more core columns and widening a bitmask. The
programmer promises independence; the hardware pays out scalability. It is the single best trade
in parallel computing.
The timeline, drawn
Here is the exact schedule the simulator below produces — six 78-cycle blocks dealt onto two
cores, reading left to right:
Three blocks per core, zero idle gaps after launch: the moment a core reports done, the
dispatcher's grant logic hands it the next block. The one-cycle stagger between the rows — core 1
forever finishing one cycle after core 0 — is the fingerprint of "one grant per cycle" from the
launch, rippling politely down the whole kernel.
The dispatcher in the simulator
Let's wire it up: two of last lesson's cores (memory still ideal — the realistic memory
controller is next lesson's job), one dispatcher, and a 24-element vector add launched as 6
blocks of 4. We set a[i] = 10(i{+}1) and
b[i] = i{+}1, so a correct run must produce
c[i] = 11(i{+}1) — the elevens times table, our self-check:
// ── The dispatcher: 6 blocks of 4 threads, fed to 2 SIMT cores as they free up. ──
// Vector add over 24 elements: a@0, b@24, c@48. Ideal memory still (the controller comes next lesson).
const PROG = [0x50de, 0x300f, 0x9100, 0x9218, 0x9330, 0x3410, 0x7440, 0x3520, 0x7550, 0x3645, 0x3730, 0x8076, 0xf000];
type Fsm = "FETCH" | "DECODE" | "REQUEST" | "WAIT" | "EXECUTE" | "UPDATE" | "IDLE" | "DONE";
const STEP: Record<string, Fsm> = {
FETCH: "DECODE", DECODE: "REQUEST", REQUEST: "WAIT", WAIT: "EXECUTE", EXECUTE: "UPDATE", UPDATE: "FETCH",
};
interface Lane { regs: number[]; addr: number; data: number }
interface Core { st: Fsm; pc: number; ir: number; blockIdx: number; lanes: Lane[] }
interface Machine { cores: Core[]; nextBlock: number; doneBlocks: number; mem: number[] }
const idleCore = (): Core => ({ st: "IDLE", pc: 0, ir: 0, blockIdx: -1, lanes: [] });
function startCore(blockIdx: number): Core { // %blockIdx LATCHED here, at assignment
const lanes: Lane[] = [];
for (let t = 0; t < 4; t++) {
const regs = new Array(16).fill(0);
regs[13] = blockIdx; regs[14] = 4; regs[15] = t;
lanes.push({ regs, addr: 0, data: 0 });
}
return { st: "FETCH", pc: 0, ir: 0, blockIdx, lanes };
}
// One core's combinational step (mem is the machine's shared memory, already cloned).
function coreNext(s: Core, mem: number[]): Core {
if (s.st === "IDLE" || s.st === "DONE") return s;
const n: Core = { ...s, st: STEP[s.st], lanes: s.lanes.map((l) => ({ ...l, regs: [...l.regs] })) };
const w = s.ir, op = w >> 12, rd = (w >> 8) & 15, rs = (w >> 4) & 15, rt = w & 15, imm = w & 255;
if (s.st === "FETCH") n.ir = PROG[s.pc];
if (s.st === "REQUEST" && (op === 7 || op === 8)) n.lanes.forEach((l) => { l.addr = l.regs[rs]; });
if (s.st === "WAIT") {
if (op === 7) n.lanes.forEach((l) => { l.data = mem[l.addr]; });
if (op === 8) n.lanes.forEach((l) => { mem[l.addr] = l.regs[rt]; });
}
if (s.st === "EXECUTE") n.lanes.forEach((l) => {
const a = l.regs[rs], b = l.regs[rt];
l.data = op === 3 ? a + b : op === 4 ? a - b : op === 5 ? a * b : op === 6 ? Math.floor(a / b) : op === 9 ? imm : l.data;
});
if (s.st === "UPDATE") {
if ((op >= 3 && op <= 7) || op === 9) n.lanes.forEach((l) => { if (rd < 13) l.regs[rd] = l.data; });
if (op === 15) n.st = "DONE"; // RET: raise the done signal
n.pc = s.pc + 1;
}
return n;
}
const NUM_BLOCKS = 6;
const log: string[] = [];
// The whole machine's settle-then-snap: cores step, then the dispatcher reacts.
function machineNext(m: Machine, cycle: number): Machine {
const mem = [...m.mem];
const cores = m.cores.map((c) => coreNext(c, mem));
let nextBlock = m.nextBlock, doneBlocks = m.doneBlocks;
// 1) Collect DONE signals: free the core, count the block.
m.cores.forEach((c, i) => {
if (c.st === "DONE") {
doneBlocks++;
cores[i] = idleCore();
log.push(`cycle ${String(cycle).padStart(3)}: core ${i} done with block ${c.blockIdx} (${doneBlocks}/${NUM_BLOCKS} blocks complete)`);
}
});
// 2) Assign at most one block per cycle to the lowest-numbered free core.
const free = cores.findIndex((c) => c.st === "IDLE");
if (nextBlock < NUM_BLOCKS && free >= 0) {
cores[free] = startCore(nextBlock);
log.push(`cycle ${String(cycle).padStart(3)}: block ${nextBlock} -> core ${free} (%blockIdx latched = ${nextBlock})`);
nextBlock++;
}
return { cores, nextBlock, doneBlocks, mem };
}
// ── Launch: 24 elements, a[i] = 10·(i+1), b[i] = i+1, so c[i] must be 11·(i+1). ──
const mem: number[] = new Array(72).fill(0);
for (let i = 0; i < 24; i++) { mem[i] = 10 * (i + 1); mem[24 + i] = i + 1; }
let m: Machine = { cores: [idleCore(), idleCore()], nextBlock: 0, doneBlocks: 0, mem };
let cycle = 0;
while (m.doneBlocks < NUM_BLOCKS) { m = machineNext(m, cycle); cycle++; }
log.forEach((l) => console.log(l));
console.log(`\nkernel complete at cycle ${cycle}`);
console.log(`c = [${m.mem.slice(48).join(", ")}]`);
const ok = m.mem.slice(48).every((x, i) => x === 11 * (i + 1));
console.log(`all 24 elements correct: ${ok}`);
Look at the rhythm of the log: assign, assign, then a long silence while both cores grind, then
done/assign pairs at cycles 79–80 and 158–159 as the cores get recycled, and finally the last two
done signals at 237 and 238 — out of lockstep, one cycle apart, exactly as the timeline
predicted. Nobody synchronised the cores; nobody needed to. Block independence means the
dispatcher can treat "core finishes" events whenever they happen to arrive — and the elevens
times table comes out perfect anyway. A single core would have needed six rounds of 78 cycles;
two cores did it in 239 — and the only thing that changed was the width of a bitmask.
NVIDIA calls its dispatcher the GigaThread Engine, and the depot it manages is
preposterous: launches of hundreds of thousands of blocks, dealt onto a hundred-plus SMs, with
several kernels' launches interleaved at once from independent queues (streams). It also handles
what our toy politely ignores: a real block must wait for a core with enough free registers
and shared memory to house it — assignment is a bin-packing decision, not just a free bit.
But the contract is identical, and so is the payoff. When a kernel written for a bus-powered
laptop GPU with 10 SMs lands unmodified on a 132-SM monster and runs thirteen times faster, no
recompile, that is not the compiler's doing — it is block-level dispatch quietly matching the
same work-list to a wider machine. The dumbest circuit in this course is the one that makes GPUs
a stable programming target across a 100× hardware range.
A tempting wiring shortcut: skip the per-core %blockIdx register and just wire every
core's R13 to the dispatcher's "current block" counter — it holds the right value at assignment
time, after all. This is a race dressed up as a simplification. The counter is
live: one cycle after granting core 0 block 4, the dispatcher grants core 1 block 5 and
the counter moves on. Core 0 is still only in FETCH — by the time its lanes read R13 to compute
i, they would see 5, or 6, or whatever the counter holds that cycle.
The result is silent corruption: threads compute a neighbouring block's indices, some
elements get written twice, others never — and the bug shifts with timing, the classic signature
of a race. The rule is general and worth engraving: when a producer's value is consumed
later, the consumer must capture its own copy at the handshake. Assignment is the
handshake; the latch in the core is the capture.