Who decides what runs at once

Whenever two operations run in the same cycle, somebody decided they were allowed to. There are only two candidates for who. A compiler could have decided, before the program ran, by proving the two operations independent and placing them accordingly. Or hardware could decide while the program runs, by inspecting instructions as they arrive. Nearly every architecture word in this area is an answer to that question, and the answers split cleanly by when the deciding happens.

A second question gets mixed into the same conversation and should not be. How much data does one instruction move? That is width, and it is independent of scheduling: a machine can be wide and statically scheduled, wide and dynamically scheduled, or narrow and either. Two of the four names below answer the scheduling question and two answer the width question, which is why they never quite line up when taught as a sequence.

The table sorts them. Read the second column first, because it says which of the two questions a row is even answering, and only then read across to who decides. Of the two rows that answer the scheduling question, exactly one hands the work to a compiler.

A modern CPU core fetches several instructions per cycle, renames their registers so false dependencies disappear, and issues each one from a window as soon as its operands are ready, in whatever order that turns out to be. Retirement puts the program order back for anything the outside world can see. Issuing several per cycle is what superscalar names; issuing them in a different order than written is what out-of-order names, and the two travel together in practice.

The compiler still emits one linear sequence, and it still tries to order that sequence well for a particular chip. Ask clang for the same function twice with the instruction set pinned and only the tuning target changed, and you get the two listings below: the same thirteen instructions with the same operands, issued in a different order. Under -mtune=skylake each load is paired with its multiply. Under -mtune=znver3 the three loads are hoisted to the front.

On a machine with a reorder buffer that ordering is a hint. The window is free to rearrange it, and -mtune mostly shifts where the rearranging starts from. What the hardware buys with all that area is knowledge the compiler could not have had: whether a load hit in cache, which way a branch actually went, whether two pointers turned out to alias. When those answers change from run to run, only a decision made at run time can use them.

# -mtune=skylake
	movss	(%rdi), %xmm0
	movss	4(%rdi), %xmm1
	mulss	(%rsi), %xmm0
	xorps	%xmm2, %xmm2
	addss	%xmm0, %xmm2
	mulss	4(%rsi), %xmm1
	movss	8(%rdi), %xmm3

# -mtune=znver3, same -march, same source
	movss	(%rdi), %xmm0
	movss	4(%rdi), %xmm1
	movss	8(%rdi), %xmm3
	xorps	%xmm2, %xmm2
	mulss	(%rsi), %xmm0
	mulss	4(%rsi), %xmm1
	mulss	8(%rsi), %xmm3

Width is the other axis, and the baseline x86-64 instruction set already has it. Compile a saxpy loop with no tuning flags at all and the inner loop comes back holding mulps %xmm1, %xmm2, which multiplies four single-precision floats in one instruction, and movups, which moves sixteen bytes. One instruction, four lanes, one program counter for all of them. The model has a name older than any of the chips in this course: SIMD, single instruction multiple data.

Notice what SIMD does not tell you. It says how much data an instruction covers and nothing about who scheduled the instruction. Here the compiler chose the width, and the out-of-order core will still reorder the result. On a TPU the VPUThe vector unit for elementwise work, organized as (8, 128) lanes; the origin of the tiling lattice every layer above obeys.taught in /l/tpu → is SIMD too, at the (8, 128) shape the chip lesson works through, and there the compiler chooses the width and the schedule. Same width model, opposite answers on the other axis.

LBB0_6:
	movups	(%rsi,%r8), %xmm2
	movups	16(%rsi,%r8), %xmm3
	movups	(%rdi,%r8), %xmm4
	movups	16(%rdi,%r8), %xmm5
	mulps	%xmm1, %xmm2
	addps	%xmm4, %xmm2
	mulps	%xmm1, %xmm3
	addps	%xmm5, %xmm3
	movups	%xmm2, (%rdi,%r8)
	movups	%xmm3, 16(%rdi,%r8)
	addq	$32, %r8
	cmpq	%r8, %rdx
	jne	LBB0_6

This unit already introduced the GPU's answer to the width question, and the hazard that comes with it (/s/machine/gpu-chip). The vendor states both plainly: "Each SM creates, manages, schedules, and executes threads in groups of 32 parallel threads called warps32 GPU threads scheduled as one unit; the GPU hides latency by switching among resident warps rather than by pipelining a scratchpad.taught in /l/tpu →", and "A warp executes one common instruction at a time, so full efficiency is realized when all 32 threads of a warp agree on their execution path." When they disagree, "the warp executes each branch path taken, disabling threads that are not on that path". The etymology in the same section is worth carrying: the term warp comes from weaving.

That description is usually taken on faith. It does not have to be. Compile a kernel whose two arms write to different arrays, look at the SASS, and the masking is written down: every instruction of the else arm carries the predicate @!P0, the store included, and so does the @!P0 EXIT that retires those threads. A warp32 GPU threads scheduled as one unit; the GPU hides latency by switching among resident warps rather than by pipelining a scratchpad.taught in /l/tpu → holding both kinds of thread walks that entire block with the wrong lanes switched off, then walks the if arm. Both arms are in the instruction stream, one after the other, exactly as advertised.

On the sorting question, SIMT answers width the way SIMD does and then adds something SIMD has no equivalent for. Each of the 32 threads carries its own program counter, and a warp32 GPU threads scheduled as one unit; the GPU hides latency by switching among resident warps rather than by pipelining a scratchpad.taught in /l/tpu → scheduler picks which resident warp issues next. That second half is a scheduling decision made by hardware at run time, which is why SIMT lands in two rows of the table at once. One more thing to hold before you count branches in a kernel: when both arms are cheap enough, the compiler removes the divergence entirely by turning the branch into a select, and the same experiment run on a two-line body comes back with an FSEL and no predicate at all.

 FSETP.GT.AND P0, PT, R0, RZ, PT
 @!P0 LDC.64 R4, c[0x0][0x220]
 @!P0 FADD R9, -R0, -RZ
 @!P0 LEA R4, P1, R7, R4, 0x2
 @!P0 LEA.HI.X R5, R7, R5, R6, 0x2, P1
 @!P0 STG.E desc[UR4][R4.64], R9
 @!P0 EXIT

two_paths:
 LDC R1, c[0x0][0x28]
 S2R R7, SR_TID.X
 LDC.64 R2, c[0x0][0x210]
 ULDC.64 UR4, c[0x0][0x208]
 IMAD.WIDE R2, R7, 0x4, R2
 LDG.E R0, desc[UR4][R2.64]
 SHF.R.S32.HI R6, RZ, 0x1f, R7
 FSETP.GT.AND P0, PT, R0, RZ, PT
 @!P0 LDC.64 R4, c[0x0][0x220]
 @!P0 FADD R9, -R0, -RZ
 @!P0 LEA R4, P1, R7, R4, 0x2
 @!P0 LEA.HI.X R5, R7, R5, R6, 0x2, P1
 @!P0 STG.E desc[UR4][R4.64], R9
 @!P0 EXIT
 ULDC.64 UR6, c[0x0][0x218]
 FMUL R5, R0, R0
 LEA R2, P0, R7, UR6, 0x2
 LEA.HI.X R3, R7, UR7, R6, 0x2, P0
 STG.E desc[UR4][R2.64], R5
 EXIT

This unit has already put the two machines on opposite sides of this question and left it there (/s/machine/two-machines): the GPU is hardware-scheduled, the TPU is compiler-scheduled. The part worth arguing now is why the second bet pays on dense linear algebra specifically, because as a general architectural choice it has lost before.

Out-of-order execution earns its transistors by covering uncertainty. A cache miss whose latency nobody knows in advance, a branch whose direction depends on data, pointers that might or might not alias. A blocked matmul supplies none of that. Trip counts are compile-time constants, addresses are affine functions of the loop indices, the only branches are loop back-edges, and the memory is a software-managed scratchpad, so a load takes a number of cycles rather than a distribution of them. Every question the reorder buffer exists to answer at run time already has an answer at compile time.

The TPU team stated the trade in the first TPU paper: "The TPU's deterministic execution model is a better match to the 99th-percentile response-time requirement of our NN applications than are the time-varying optimizations of CPUs and GPUs (caches, out-of-order execution, multithreading, multiprocessing, prefetching, ...) that help average throughput more than guaranteed latency." The later training-chip paper lists what got deleted to pay for the multipliers, "dropping general-purpose features irrelevant for DNNs but critical for CPUs such as caches and branch predictors".

Delete the scheduler and something has to emit the schedule. The instruction format is where it goes: on TPUv2 and v3, "the 322-bit VLIW instruction can launch eight operations: two scalar, two vector ALU, vector load and store, and a pair of slots that queue data to and from the matrix multiply and transpose units". An instruction word with independent slots that all issue together is a VLIW, a very long instruction word, and filling the slots is the compiler's job. The same paper names which compiler: "TPUs use a VLIW architecture to express instruction-level parallelism to the many compute units of a TensorCore. XLAThe compiler: brilliant at fusing along dataflow edges, structurally unable to change your algorithm. That gap is why kernels exist.taught in /l/xla → uses standard VLIW compilation techniques including loop unrolling, instruction scheduling, and software pipelining to keep all compute units busy."

Hardware schedules what it can see. A compiler sees the whole loop nest.

A VLIW schedule is correct for the latencies it was built against. Change the depth of one unit by a cycle and the bundles are wrong, so the format is tied to a generation in a way an ISA is not supposed to be. Both vendors reached the same arrangement: publish a stable layer, keep the schedule-bearing layer private, and translate between them behind a closed door. The previous lesson walked the GPU half of that split; the MosaicThe MLIR dialect Pallas lowers to, and the last layer of the TPU stack you can read; only LLO below it is closed.taught in /l/mosaic → layer chapter (/l/mosaic) walks the TPU half. Set them beside each other and the shape is the same twice over.