Parallel Reduction (WebGPU workgroup-shared-memory tree reduction)

Math essence

Initialise a length-N array of doubles (sin+cos+noise+spikes). Apply a binary tree reduction op ∈ {sum, max, mean}; intermediate levels L[0..k] saved. Render row r with horizontal bars whose heights equal the L[r] elements (normalised per-level). Repeating with a fresh seed each step animates the level rows.

Parameters

Reference

First 60 lines of reference.py. Full source: library_external/anadol_webgpu/parallelReduction/reference.py

"""parallelReduction — WebGPU parallel reduction primitive.

The WebGPU 'parallel reduction' pattern reduces an array of N elements
to a single scalar (or per-workgroup vector) using a tree-of-sums in
workgroup-shared memory.  This is the same primitive used in
histograms, image moments, mean/max/sum statistics, and the first
phase of a softmax / dot-product kernel.

Reference implementation in WGSL (illustrative):

    const WS = 256u;
    var<workgroup> sh : array<f32, WS>;
    @compute @workgroup_size(WS)
    fn reduce_sum(
        @builtin(global_invocation_id) gid : vec3u,
        @builtin(local_invocation_id)  lid : vec3u,
        @builtin(workgroup_id)         wid : vec3u,
    ) {
        let i = gid.x;
        let n = arrayLength(&data);
        sh[lid.x] = select(0.0, data[i], i < n);
        workgroupBarrier();
        var stride = WS / 2u;
        loop {
            if (stride == 0u) { break; }
            if (lid.x < stride) {
                sh[lid.x] = sh[lid.x] + sh[lid.x + stride];
            }
            workgroupBarrier();
            stride /= 2u;
        }
        if (lid.x == 0u) { result[wid.x] = sh[0]; }
    }

A second dispatch then sums the per-workgroup partials.

Here we reduce a synthesised array of N floats and render the
workgroup-block partials as a 1D bar chart so the spatial structure
of the reduction (root-of-tree semantics) is directly visible.

Reference:
- https://www.mysimulator.uk/content/articles/webgpu-compute.html
  (parallel reduction using shared memory in WGSL)
- https://webgpufundamentals.org/webgpu/lessons/webgpu-compute-shaders.html
"""
from __future__ import annotations

from typing import ClassVar

import numpy as np


class ParallelReduction:
    """Workgroup-tree parallel reduction visualised as a 1D bar chart.

    Parameters
    ----------
    dim : int
        Square canvas side length (px).
    array_size : int