How subgroupBallotFindMSB Finds the Highest Set Bit

This article explains how the GLSL function subgroupBallotFindMSB determines the most significant set bit within a subgroup ballot mask. It covers the structure of the four-component ballot vector, the hierarchical search order from the most significant word down to the least, the underlying bit-scanning instructions used by GPU hardware, and the arithmetic required to resolve the final invocation index.

Ballot Mask Representation

In GLSL subgroup operations, a ballot result is stored as a uvec4, representing a 128-bit bitmask where each bit corresponds to an invocation (lane) within the subgroup:

  • value.x covers invocation indices 0 through 31.
  • value.y covers invocation indices 32 through 63.
  • value.z covers invocation indices 64 through 95.
  • value.w covers invocation indices 96 through 127.

When an invocation evaluates subgroupBallotFindMSB(uvec4 value), it searches for the highest-indexed active invocation whose corresponding bit is set to 1.

High-to-Low Vector Traversal

Because the function searches for the most significant bit across the entire 128-bit vector, evaluation proceeds in descending order of significance across the vector components: w, z, y, and x.

The GPU logically evaluates the vector components as follows:

  1. Inspect value.w. If value.w != 0, the highest set bit resides in the range [96, 127].
  2. If value.w == 0, inspect value.z. If value.z != 0, the highest set bit resides in the range [64, 95].
  3. If value.z == 0, inspect value.y. If value.y != 0, the highest set bit resides in the range [32, 63].
  4. If value.y == 0, inspect value.x. If value.x != 0, the highest set bit resides in the range [0, 31].

Intra-Word Bit Scanning

Once the highest non-zero 32-bit unsigned integer is identified, the hardware calculates the position of the most significant set bit within that specific word.

Modern GPUs implement this operation directly at the ISA (Instruction Set Architecture) level using dedicated integer ALU instructions:

  • Count Leading Zeros (CLZ): Many architectures count the number of zero bits preceding the first 1 starting from bit 31. The intra-word MSB index is computed as 31 - CLZ(word).
  • Find First Bit / Bit Scan Reverse (BSR): Architectures such as AMD (via V_FFBH_U32) or NVIDIA (via FLO - Find Leading One) expose single-cycle instructions that return the zero-based index of the most significant 1 directly.

Global Index Computation

After finding the local bit position within the relevant 32-bit component, the global index is resolved by adding an offset corresponding to that component's position within the uvec4:

\[\text{Global MSB} = (\text{Component Index} \times 32) + \text{Local MSB}\]

Where:

  • w has a component index of 3 (offset +96).
  • z has a component index of 2 (offset +64).
  • y has a component index of 1 (offset +32).
  • x has a component index of 0 (offset +0).

For example, if value.w is zero and value.z contains 0x00000400 (bit 10 is set), the component index is 2. The final result is (2 * 32) + 10 = 74.

Undefined Behavior on Zero Masks

If every component in value is zero (uvec4(0)), no set bit exists. According to the GLSL specification, passing a ballot mask with no set bits to subgroupBallotFindMSB produces an undefined result. Applications typically guard this call with subgroupBallotBitCount(value) > 0 or check if value != uvec4(0) before querying the MSB.