Task 4 of 5

Partial Histograms, Then Merge

Sixteen bins is sixteen threads. A GPU with thousands of cores just sat out that entire kernel — and each of those sixteen threads had to walk all 16,384 codes by itself. Few bins over lots of data is exactly where one-thread-per-bin runs out of parallelism.

So cut the data into chunks and give every (bin, chunk) pair its own thread. Thirty-two chunks of 512 codes turns 16 threads into 16 × 32 = 512, each scanning 512 codes instead of 16,384. What comes back is a grid of partial histograms: one row per chunk, one column per bin. A second pass then adds up each bin's column.

Mind the shape. output: [bins, chunks] is given width-first but indexed row-first, so the grid you get back is partial[chunk][bin] — swap those two and you read off the end of a row. Pass two sums a column of 32 numbers, which one loop handles comfortably; at 4,096 chunks you would ride the halving ladder from Reductions down instead, because that is the same reduction wearing a different hat.

Keep watching the total — but do not over-trust it here. If every chunk reads chunk 0's codes, the counts are entirely wrong and still sum to 16,384. The total catches lost and duplicated inputs; it cannot catch inputs you counted the wrong number of times each.

one row per chunk, one column per bin, one reduction down each column
Goal: build the 16 × 32 grid of partial histograms in one kernel, then merge it into 16 final counts in a second.

Requirements

Hint 1 — where does my chunk start?

Chunk y owns the 512 codes from y * 512 to y * 512 + 511, so its i-th code is at this.thread.y * this.constants.chunkSize + i. The starter is missing that offset, which is why every chunk currently reports chunk 0's histogram.

Hint 2 — the partials kernel
const code = codes[this.thread.y * this.constants.chunkSize + i];
if (code === this.thread.x) count++;
Hint 3 — the merge

One thread per bin, walking down that bin's column of the grid:

let total = 0;
for (let c = 0; c < this.constants.chunks; c++) {
  total += partial[c][this.thread.x];
}
return total;

Same idea elsewhere

This is what a production GPU histogram actually does, and the reason is the same one: parallelism. A CUDA kernel gives each block a private histogram in shared memory, so its atomicAdds stay on-chip and only conflict within the block, then spends one global atomicAdd per bin to merge. WGSL does it with a var<workgroup> array of atomics and a single merge at the end; CUB and rocPRIM's DeviceHistogram are this structure, tuned. Private partials plus a merge pass is the pattern — gpu.js just makes you write the merge as an honest reduction instead of hiding it behind an atomic.

All tasks in Histograms & Binning

  1. The Increment That Vanishes
  2. One Thread Per Bin
  3. Where Does 7.35 Go?
  4. Partial Histograms, Then Merge
  5. Payoff: An Image's Tone Histogram

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.