GPU Threads vs CPU Threads: Warps and Wavefronts

Topic Overview

CPU Threads vs GPU Warps

A CPU thread is an independent execution context with its own program counter, registers, and stack. Context switching is expensive because the OS must save and restore the full register file. Modern CPUs run tens of threads across a handful of cores.

A GPU thread is much lighter. On NVIDIA hardware, 32 threads form a warp; on AMD, 64 threads form a wavefront. All threads in a warp execute the same instruction on different data. This is Single Instruction, Multiple Thread (SIMT) execution.

Divergence and Memory Patterns

The critical difference is divergence. If threads in the same warp take different branches, the hardware serializes them:

cCopy
Loading…

For example, a warp where 16 threads take branch A and 16 take branch B runs both paths sequentially, halving throughput. Memory access matters too: if thread i reads address base + i * 4, the warp issues one coalesced transaction. If each thread reads base + i * 1024, the warp may issue up to 32 separate transactions.

• Warp (NVIDIA): 32 threads in lockstep
• Wavefront (AMD): 64 threads, same idea
• SM: Streaming Multiprocessor that schedules warps

For This Exercise

You will implement a warp simulation that shows branch divergence in two serialized phases and compares coalesced vs scattered memory access. This task requires you to count transactions and explain why GPU threads are not scheduled like CPU threads. Every later GPU architecture exercise in this subtrack assumes you think at warp granularity, not individual thread granularity.

Your Task

A GPU runs threads in lockstep groups: warps of 32 on NVIDIA, wavefronts of 64 on AMD GCN. All lanes of a group share one instruction stream. When a branch diverges, the group runs both sides one after the other, masking off the lanes that didn't take each side. A loop runs as long as its slowest lane. Build a cost model that shows this: run a small kernel over N threads, split into groups of 32 or 64, and report cycles and lane utilization per group.

Input

# starts a comment.

cCopy
Loading…

• Expressions: VAR [OP K] [CMP R].
  • VAR is tid (the global thread id) or lane (tid mod width).
  • OP is %, / or &, with K > 0.
  • CMP is ==, !=, < or >=.
• COND needs a CMP, unless it uses & (non-zero means true).
• TRIPS is an expression without a CMP, or a non-negative constant.

Cost model

Group g holds threads g·width … g·width+width-1. Lanes past N are inactive from the start.

• work C: costs C cycles if any lane is active, and adds C useful lane-cycles per active lane.
• if: the then-mask is (active ∧ cond) and the else-mask is (active ∧ ¬cond). Each side runs only if its mask is non-empty, one after the other, so a uniform branch pays for one side and a divergent branch pays for both. An if reached with at least one active lane counts as a branch execution, and it is divergent if both masks are non-empty.
• loop: costs C × max(TRIPS over active lanes), and adds TRIPS × C useful lane-cycles per active lane.
• Utilization: useful lane-cycles / (cycles × width), as a percentage rounded half up to one decimal (100.0% when cycles = 0).
• Timing: groups run one after another, and each costs its cycle count, whatever its width.

Output

cCopy
Loading…

• Headers: 64-wide runs say wavefront(s). Plurals: lane(s), branch(es).
• Total utilization is the sum of useful lane-cycles over the sum of cycles × width.
• Errors:
  • line N: threads 1-1024
  • line N: work CYCLES (1-1000000)
  • line N: bad condition, line N: loop TRIPS CYCLES
  • line N: else without if, line N: end without if
  • line N: unknown statement X
  • program has errors (for run after any error)
  • run: N unclosed if
  • run: width must be 32 or 64

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Model the execution mask explicitly: a boolean per lane, narrowed at each branch and restored after it.
2. Charge the cycles per group, not per thread. Diverged lanes cost time even though they do nothing useful.

Hidden tests cover a branch that is uniform for warps but divergent for wavefronts, per-lane loop trip counts, nested branches with lane and &, a partially filled group, and statement errors.