SIMT Execution and Divergence Simulation

Topic Overview

SIMD: Explicit Vectors on the CPU

SIMD (Single Instruction, Multiple Data) is a processor feature where one instruction operates on a vector of data simultaneously. SSE, AVX, and NEON are SIMD instruction sets. The programmer or compiler explicitly chooses vector width and uses blend/mask instructions to handle per-lane differences.

For example, an AVX-256 add operates on eight 32-bit floats in one instruction. The programmer controls which lanes are active.

SIMT: Scalar Code, Hardware Masking

SIMT (Single Instruction, Multiple Thread) is how NVIDIA GPUs execute. One instruction broadcasts to many execution units, but you write scalar thread code. Each thread has its own registers and can branch independently. The hardware masks off inactive threads.

Consider a warp of 32 threads where thread_id % 4 == 0 takes one path and the rest take another:

cCopy
Loading…

In pure SIMD, a skilled programmer might use blend instructions to handle both paths in one pass. In SIMT, divergence always serializes. AMD wavefronts of 64 threads follow the same rules.

• SIMD: programmer controls masks explicitly
• SIMT: hardware masks per branch path
• Practical rule: keep warps on uniform control flow in inner loops

For This Exercise

You will simulate SIMT execution with boolean execution masks, show two-phase divergence for an if/else, and model early-exit loops where inactive threads stay masked until all threads finish. This task requires you to print masks per phase and calculate the divergence penalty. Understanding SIMT vs SIMD explains why GPU kernels punish data-dependent branches that CPU vector code can sometimes absorb.

Your Task

Simulate how a GPU warp executes a divergent program under SIMT. Every lane has its own register r, but the warp has a single instruction stream and an active mask:

• an if splits the mask and runs the then-side, then the else-side;
• a while keeps looping as long as any lane still wants to, with finished lanes masked off;
• both reconverge at their end.

Print every executed statement with the mask it ran under, then each lane's final r.

Input

# starts a comment.

cCopy
Loading…

Operands are tid, r or an integer. Statements are echoed with single spaces between their tokens.

Rules

• Masks print as [...]: one character per lane, lane 0 first, 1 for active and . for inactive.
• Assignment: every active lane computes the new r from its own values. If any active lane divides or takes % by zero, print the statement, then error: division by zero in an active lane, and stop the run.
• if: print [mask] if … -> then [T] else [E], with (diverged) when both are non-empty.
  • Run the then-body with T if T is non-empty.
  • Then, if there is an else and E is non-empty, print [E] else and run the else-body with E.
  • Finally print [mask] end if (reconverged).
• while: repeatedly compute M = mask ∧ condition and print [mask] while … -> [M]. Stop when M is empty. Otherwise run the body with M.
  • After the loop, print [mask] end while (reconverged after K iteration(s)).
  • More than 20 iterations print error: loop ran more than 20 iterations and stop the run.
• Limits: more than 10000 executed statements print step limit reached.
• End of run: r: v0 v1 ….

Output

cCopy
Loading…

Errors (a program with errors can't run until clear: program has errors):

• line N: width 1-32
• line N: bad assignment, line N: bad condition
• line N: else without if, line N: end without if/while
• line N: cannot parse "TEXT"
• run: missing end

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Inactive lanes must not change: every write is predicated by the mask.
2. Handle reconvergence structurally. The mask after end is exactly the mask before the if or while, as with a hardware reconvergence stack.

Hidden tests cover a loop whose lanes exit at different iterations, a uniform branch (empty else-mask), nested divergence, division by zero in an active lane, a runaway loop, and parse errors.