워프 분기 없애기

A warp is 32 threads that execute the same instruction together. When their paths agree, the hardware runs at full speed.

If threads in a warp take different branches, that is divergence. The hardware runs each path serially, leaving some lanes idle and wasting cycles.

The simple version uses tid % (2*s) to pick active threads. Active and idle threads interleave inside every warp, so each warp diverges hard.

Even though half the threads do nothing, they still occupy the warp. The warp cannot finish until both the active and idle paths are handled.

The fix is to map active work to the lowest thread IDs instead of scattered ones. Compute an index from tid and the stride.

Now the busy threads are contiguous: tid 0,1,2,... all work, the rest all rest. Whole warps are either fully active or fully idle.

A warp where every lane is idle just retires with no work. There is no per-lane serialization, so the cost of divergence largely disappears.

The hidden villain was the modulo condition. It scattered active threads across each warp, which is exactly what creates divergence.

You did not change the math or the number of additions. You only remapped which thread does each add, and the warps thank you for it.

Across thousands of blocks and many steps, removing divergence is a real speedup, often a couple of times faster than the naive kernel.

This version reads neighbors that are interleaved in shared memory, which can cause bank conflicts. The next lesson fixes that too.

Think about what causes warp divergence in the naive reduction.

You killed divergence by giving work to the lowest thread IDs, so warps are all-active or all-idle. Same math, faster reduction. Next: bank conflicts. 🚀