Hillis-Steele Inclusive Scan in GLSL Shared Memory

This article explains how to implement the Hillis-Steele inclusive parallel prefix sum (scan) algorithm within a GLSL compute shader workgroup. It covers the core algorithmic logic, the role of workgroup shared memory, proper barrier synchronization to prevent data races, and provides a complete, ready-to-use GLSL implementation.

Algorithmic Concept

The Hillis-Steele algorithm computes an inclusive prefix sum across an array of \(N\) elements in \(O(\log_2 N)\) steps. In an inclusive scan, each output element at index \(i\) is the sum of all input elements from index \(0\) through \(i\).

In each iteration step \(d\) (where the offset is \(2^d\) for \(d = 0, 1, 2, \dots\)), every thread at index \(i \ge 2^d\) adds the value stored at index \(i - 2^d\) to its current value. Threads with an index \(i < 2^d\) keep their current values unchanged.

GLSL Implementation

Below is a complete GLSL compute shader demonstrating the Hillis-Steele inclusive scan across a 1D workgroup of 256 invocations.

#version 450 core

layout(local_size_x = 256, local_size_y = 1, local_size_z = 1) in;

// Buffers for input and output
layout(std430, binding = 0) readonly buffer InputBuffer {
    float in_data[];
};

layout(std430, binding = 1) writeonly buffer OutputBuffer {
    float out_data[];
};

// Workgroup shared memory
shared float shared_data[gl_WorkGroupSize.x];

void main() {
    uint tid = gl_LocalInvocationID.x;
    uint gid = gl_GlobalInvocationID.x;

    // 1. Load input into shared memory
    shared_data[tid] = in_data[gid];
    barrier();

    // 2. Hillis-Steele Inclusive Scan
    for (uint offset = 1; offset < gl_WorkGroupSize.x; offset <<= 1) {
        float temp = 0.0;
        
        // Read neighbor value if within bounds
        if (tid >= offset) {
            temp = shared_data[tid - offset];
        }
        
        // Synchronize to ensure all threads have read their needed value
        barrier();
        
        // Accumulate and update shared memory
        shared_data[tid] += temp;
        
        // Synchronize to ensure all writes complete before the next iteration
        barrier();
    }

    // 3. Write result to global memory
    out_data[gid] = shared_data[tid];
}

Key Implementation Details

1. Shared Memory Allocation: The shared float shared_data[...] array provides low-latency memory accessible by all invocations within the same workgroup.
2. Double Synchronization Requirement: An in-place implementation requires two barrier() calls per iteration to avoid read-after-write hazards:
   • The first barrier() ensures all threads have read the source value into the local register variable temp before any thread overwrites its entry in shared_data.
   • The second barrier() ensures all updates to shared_data are finalized before the next iteration begins with a doubled offset.
3. Loop Execution: The loop variable offset begins at 1 and doubles each iteration (offset <<= 1) until it equals or exceeds the workgroup size. For a workgroup size of 256, the loop executes exactly \(\log_2(256) = 8\) times.

Characteristics and Trade-offs

The Hillis-Steele scan performs \(O(N \log N)\) total addition operations, which is work-inefficient compared to the Blelloch scan's \(O(N)\) operations. However, because it requires fewer total synchronization steps and exhibits lower control-flow divergence on GPU hardware, it is often faster for small arrays that fit entirely within a single workgroup.