subgroupBallotExclusiveBitCount in GLSL Explained

subgroupBallotExclusiveBitCount is a GLSL subgroup intrinsic that calculates the number of set bits in a ballot mask for all active invocations with an index strictly lower than the current invocation. This operation functions as an exclusive prefix sum (or scan) over a subgroup, making it a critical primitive for compacting sparse data, allocating dynamic local indices, and eliminating atomic contention when writing to global memory.

The Input Ballot Structure

In GLSL, a subgroup ballot is represented as a uvec4, accommodating up to 128 subgroup invocations across four 32-bit unsigned integers. Each bit corresponds directly to an invocation index (gl_SubgroupInvocationID). For instance, bit 0 of the first vector component corresponds to invocation 0, bit 31 corresponds to invocation 31, and bit 0 of the second component corresponds to invocation 32.

The Computation Process

The function evaluates the prefix count by isolating and counting only the bits that precede the calling invocation's lane ID:

  1. Generating the Exclusive Lane Mask: The GPU generates a 128-bit mask where every bit position strictly less than gl_SubgroupInvocationID is set to 1, and all bit positions greater than or equal to gl_SubgroupInvocationID are set to 0. Hardware architectures frequently maintain this mask in special registers (such as %lanemask_lt in NVIDIA PTX).

  2. Bitwise Masking: The hardware applies a bitwise AND operation between the input uvec4 ballot and the generated exclusive lane mask. This zeros out the bit representing the calling invocation itself as well as all bits belonging to higher-ranked lanes.

  3. Population Count: A population count (popcount) operation is executed on the masked components. The number of remaining 1 bits across all relevant 32-bit words is summed:

    \[\text{ExclusiveBitCount} = \sum \text{popcount}(\text{ballot} \ \& \ \text{mask}_{<\text{lane}})\]

Because all bits at or above the current lane are removed prior to counting, the returned value strictly represents the number of preceding set bits.

Hardware-Level Implementation

On modern graphics architectures, this sequence rarely requires manual loop iteration or multi-word software branches. AMD (RDNA/GCN) and NVIDIA architectures feature dedicated bit-manipulation hardware:

  • Lane Masks: Hardware exposes precomputed masks indicating which lanes are less than the current thread ID without needing ALU-generated shifts.
  • Vector Popcounts: The bitwise AND and subsequent population count are performed using dedicated instructions (such as V_BCNT_U32_B32 on AMD or POPC on NVIDIA), computing the result in very few cycles.

Typical Use Case: Stream Compaction

If a subgroup needs to write filtered elements to a contiguous output array, each invocation performs a ballot on its condition. By calling subgroupBallotExclusiveBitCount, every passing lane computes its exact, collision-free offset within the shared output buffer without invoking costly atomic operations.