Parallelism

Warp Execution and Divergence

Warp Execution and Divergence

A warp is 32 threads that the GPU schedules and executes as a single unit. Understanding warp behavior is essential for reasoning about performance.

SIMT: Single Instruction, Multiple Threads

Every SM executes instructions in warp granularity using the SIMT (Single Instruction, Multiple Thread) model:

  • ▸All 32 threads in a warp execute the same instruction in the same clock cycle
  • ▸Each thread has its own registers and produces different results (different data)
  • ▸A block of 256 threads is divided into 8 warps (warps 0–7, threads 0–31, 32–63, …)

Warp Divergence

When threads in a warp take different branches, hardware uses predication — both paths execute sequentially with inactive threads masked off:

c
// 50% efficiency: half the warp is idle in each branch
if (threadIdx.x < 16) {
    doA();   // threads 0-15 active, 16-31 idle
} else {
    doB();   // threads 16-31 active, 0-15 idle
}

Each additional divergent path multiplies the cycles consumed. A branch taken by all or no threads in a warp has zero divergence cost.

Minimizing Divergence

Warp-aligned conditions (no divergence cost):

c
// Safe: condition is uniform for all 32 threads in a warp
if (blockIdx.x * blockDim.x < n) { ... }

Bounds guard as early return (only the last partial warp diverges):

c
int i = blockIdx.x * blockDim.x + threadIdx.x;
if (i >= n) return;  // minimal divergence: only the last block's last warp

Zero-Overhead Context Switching

When a warp stalls on a global memory load (~800 cycles), the scheduler immediately switches to another ready warp — zero overhead because all warp state lives in the register file (no save/restore). This is how GPUs hide memory latency through massive thread parallelism.

A stall of 800 cycles is hidden completely if there are enough other active warps to fill the time. This is the motivation for high occupancy.

Warp-Level Primitives (CUDA 9+)

Threads exchange values within a warp without shared memory using shuffle instructions:

| Primitive | Effect | |---|---| | __shfl_sync(mask, val, srcLane) | All threads receive value from srcLane | | __shfl_down_sync(mask, val, delta) | Thread i receives value from thread i+delta | | __shfl_up_sync(mask, val, delta) | Thread i receives value from thread i-delta | | __shfl_xor_sync(mask, val, laneMask) | Butterfly exchange by XOR of lane IDs | | __ballot_sync(mask, pred) | 32-bit mask: bit i set if thread i's pred is true | | __any_sync(mask, pred) | True if any thread in warp satisfies pred | | __all_sync(mask, pred) | True if all threads satisfy pred |

The first argument (mask) specifies participating threads. Use 0xffffffff for full-warp participation.

Warp Reduce in 5 Instructions

A full 32-way reduction using shuffles — no shared memory, no __syncthreads():

c
float warpReduceSum(float val) {
    val += __shfl_down_sync(0xffffffff, val, 16);
    val += __shfl_down_sync(0xffffffff, val,  8);
    val += __shfl_down_sync(0xffffffff, val,  4);
    val += __shfl_down_sync(0xffffffff, val,  2);
    val += __shfl_down_sync(0xffffffff, val,  1);
    return val;  // lane 0 holds the total
}

// CODE EXAMPLE

example.cu
// Full block reduction using warp shuffles + shared memory
// No __syncthreads() inside the warp reduce phase

__device__ float warpReduceSum(float val) {
    val += __shfl_down_sync(0xffffffff, val, 16);
    val += __shfl_down_sync(0xffffffff, val,  8);
    val += __shfl_down_sync(0xffffffff, val,  4);
    val += __shfl_down_sync(0xffffffff, val,  2);
    val += __shfl_down_sync(0xffffffff, val,  1);
    return val;
}

__global__ void blockSum(const float *in, float *out, int n) {
    __shared__ float warpSums[32];  // max 32 warps per block

    int gid    = blockIdx.x * blockDim.x + threadIdx.x;
    int lane   = threadIdx.x % 32;   // lane within warp
    int warpId = threadIdx.x / 32;   // which warp in block

    float val = (gid < n) ? in[gid] : 0.f;

    // Phase 1: reduce within each warp (no shared memory needed)
    val = warpReduceSum(val);

    // Phase 2: lane 0 of each warp writes partial sum to shared memory
    if (lane == 0) warpSums[warpId] = val;
    __syncthreads();

    // Phase 3: first warp reduces all warp sums
    if (warpId == 0) {
        int numWarps = (blockDim.x + 31) / 32;
        val = (lane < numWarps) ? warpSums[lane] : 0.f;
        val = warpReduceSum(val);
        if (lane == 0) atomicAdd(out, val);
    }
}

// TRY IT

GPU execution
main.cu
loading editor…