# Partial Histograms, Then Merge

*Task 4 of 5 · [Histograms & Binning](https://gpu.rocks/learn/histograms-and-binning-dfb254f4.md) · GPU.js Learn*

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.

## Figures

- **one row per chunk, one column per bin, one reduction down each column**

## Goal

**Goal:** build the 16 × 32 grid of partial histograms in one kernel, then
merge it into 16 final counts in a second.

## Requirements

- `partials`: `output: [16, 32]`, thread `(x = bin, y = chunk)` counts chunk *y*'s codes that equal *x*
- Chunk *y* is contiguous: it starts at `this.thread.y * this.constants.chunkSize`
- `merge`: `output: [16]`, thread *x* sums `partial[c][this.thread.x]` over all `this.constants.chunks` chunks
- The merged counts sum to `16384`

## 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

```js
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:

```js
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 `atomicAdd`s 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.

## Starter code

```js
// Pass 1: one thread per (bin, chunk). Pass 2: merge each bin's column.
const gpu = new GPU({ mode });

const partials = gpu.createKernel(function (codes) {
  let count = 0;
  for (let i = 0; i < this.constants.chunkSize; i++) {
    // TODO: every chunk is reading chunk 0 right now. Chunk this.thread.y
    // starts at this.thread.y * this.constants.chunkSize.
    if (codes[i] === this.thread.x) count++;
  }
  return count;
}, {
  output: [16, 32],
  constants: { chunkSize: 512 },
});

const merge = gpu.createKernel(function (partial) {
  // TODO: add up all this.constants.chunks partial counts for THIS
  // thread's bin. The grid is indexed partial[chunk][bin].
  return partial[0][this.thread.x];
}, {
  output: [16],
  constants: { chunks: 32 },
});

const grid = await partials(codes);
const counts = await merge(grid);
console.log('counts:', counts);
```

---

Interactive version: https://gpu.rocks/learn/histograms-and-binning-dfb254f4/4

[Previous task](https://gpu.rocks/learn/histograms-and-binning-dfb254f4/3.md) · [Next task](https://gpu.rocks/learn/histograms-and-binning-dfb254f4/5.md)