Ray Traversal Divergence in GLSL Compute Shaders

Ray traversal divergence in GLSL compute shaders occurs when threads within the same execution warp follow different execution paths or access scattered memory locations while traversing a bounding volume hierarchy (BVH). This article examines the architectural mechanics of ray traversal within Single Instruction, Multiple Threads (SIMT) architectures, detailing how execution serialization and non-coalesced memory accesses degrade GPU performance. It also outlines key hardware bottlenecks—including ALU underutilization, register pressure, and cache thrashing—alongside practical algorithmic strategies to mitigate these performance penalties.

The SIMT Execution Model and Divergence

GPUs execute compute shaders in lockstep groups of threads known as warps (NVIDIA, typically 32 threads) or wavefronts (AMD, typically 32 or 64 threads). Under the SIMT paradigm, every thread in a warp shares a single program counter and executes the same instruction simultaneously. When code paths diverge due to conditional branching, the hardware must serialize the divergent paths, masking out inactive threads during each branch until all execution paths reconverge.

In a pure software ray tracer running in a GLSL compute shader, each thread typically handles one ray, stepping through a hierarchical acceleration structure (such as a BVH) to find primitive intersections. Because scenes have varying geometric complexity and rays travel in different directions, threads within the same warp rarely follow identical traversal paths.

Mechanisms of Ray Traversal Divergence

Ray traversal introduces two primary forms of divergence:

  1. Branch (Control Flow) Divergence: Rays traversing simple regions of a scene might intersect a leaf node or exit the scene bounding box in just a few iterations. Other rays in the same warp might pierce dense geometry, requiring dozens or hundreds of BVH node traversals and primitive intersection tests. The warp cannot complete its execution until its longest-running thread finishes, leaving shorter-running threads idle.
  2. Memory Access Divergence: Neighboring threads that diverge in the BVH fetch node structures and triangle data from completely different regions of global memory. This destroys spatial and temporal locality, preventing memory coalescing and overwhelming the L1 and L2 caches.

Direct Performance Impacts

The consequences of traversal divergence on compute shader performance are severe and manifest across several hardware layers:

  • ALU Underutilization: The primary metric degraded by branch divergence is active thread occupancy. If only 1 out of 32 threads in a warp is actively traversing a deep tree while the remaining 31 are inactive, the effective vector computation efficiency for that warp drops to 3.125%. The GPU continues to expend clock cycles executing traversal instructions despite most lanes being masked out.
  • Memory Latency Amplification: When rays diverge, load requests for BVH node data become fragmented. Instead of serving 32 threads via a single 128-byte memory transaction, the memory controller must issue multiple independent transactions. This saturates the memory bus, dramatically increases memory latency, and causes instruction stalls as threads wait for traversal data.
  • Register Pressure and Limited Active Warps: Implementing complex BVH traversal and ray-primitive intersections in a compute shader requires significant local storage (e.g., traversal stacks, hit records, ray origins, directions). High register usage per thread limits the total number of warps that an execution unit (Streaming Multiprocessor or Compute Unit) can hold simultaneously. When warps stall due to divergent memory loads, the GPU cannot hide this latency because there are not enough alternative warps available to swap in.

Divergence by Ray Type

The severity of performance degradation depends heavily on ray coherence:

  • Primary and Shadow Rays: These rays typically exhibit high spatial coherence. Primary rays cast from a pinhole camera and hard shadow rays directed toward point light sources follow similar trajectories. As a result, warp threads traverse similar BVH branches, minimizing divergence penalties.
  • Secondary and Ambient Occlusion Rays: Diffuse reflections, glossy refractions, and path-traced bounces scatter rays in semi-random directions. Secondary rays exhibit extreme traversal divergence, causing SIMT efficiency to collapse if executed directly in compute shader loops without pre-processing.

Mitigation Techniques

To counteract traversal divergence in compute shaders, developers apply several algorithmic strategies:

  • Ray Sorting (Binning): Before executing traversal kernels, rays are sorted by origin and direction using spatial hashing or Morton codes. Grouping spatially coherent rays into the same warps substantially decreases branch divergence and improves memory coalescing.
  • Stream Compaction and Wavefront Path Tracing: Instead of running a megakernel where one thread computes an entire multi-bounce path, the rendering pipeline is split into distinct stages: ray generation, traversal, and shading. Between stages, stream compaction filters out terminated rays, repacking active rays into dense, coherent warps to maintain maximum ALU utilization.
  • Short-Stack and Packet Traversal: Reducing the traversal stack footprint directly lowers register usage, allowing higher occupancy that masks remaining latency. Additionally, traversing rays as small bounding packets can allow shared node fetches for coherent rays.
  • Hardware-Accelerated Ray Tracing: Where possible, standard GLSL compute software traversal should be replaced with or augmented by dedicated ray query extensions (GL_EXT_ray_query). These extensions leverage fixed-function RT Cores, which handle asynchronous BVH traversal and intersection testing in dedicated hardware blocks, entirely bypassing SIMT compute lane serialization.