# Drive the Whole Network

*Task 4 of 5 · [Bitonic Sort](https://gpu.rocks/learn/bitonic-sort-84e0728e.md) · GPU.js Learn*

One pass is one kernel launch. The network is two plain JavaScript loops around
it — stages doubling outward, and within each stage strides halving down to 1. Here is the
thing worth noticing, though: those loops never look at the data. So don't interleave them
with it. Build the entire **schedule** first, as a list of
`[stage, stride]` pairs, and print it:

```js
const schedule = [];
for (let stage = 2; stage <= n; stage *= 2) {
  for (let stride = stage / 2; stride >= 1; stride /= 2) {
    schedule.push([stage, stride]);
  }
}
```

All 36 pairs for n = 256, complete, before a single value has been read. Then run them.
That is the property this whole module is about: every thread derives its partner and its
direction from its own index, so nothing waits on a comparison, no warp diverges, and
nobody has to be told anything. A quicksort cannot do this — you do not know its second
partition until you have done the first.

The bill comes due in comparisons. Bitonic sort does O(n log²n) of them where quicksort
does O(n log n): 36 passes × 128 pairs = 4,608 compare-exchanges for 256 values, against
roughly 2,000. More than twice the work — in 36 sequential steps, with everything inside a
step happening at once. That trade, a predictable structure bought with extra work, is the
most transferable idea in this course.

## Figures

- **six passes, twenty-four comparators, and not one of them depends on a value**

## Goal

**Goal:** build and print the whole 36-pass schedule before touching the
data, run it to sort 256 values, and log the smallest and largest of the result.

## Requirements

- `schedule` holds the `[stage, stride]` pairs: stages doubling from 2 up to and *including* `n`, strides halving from `stage / 2` down to 1
- Build it without reading `data` — the schedule is complete before the first kernel call
- `console.log` the pass count and the schedule itself (already wired up)
- `console.log` the smallest and largest values of the sorted result

## Hint 1 — the two loops

Outer loop doubles, inner loop halves, and both bounds are inclusive at the
far end: `stage <= n`, `stride >= 1`. The body is one
line — `schedule.push([stage, stride]);`

## Hint 2 — the last stage is the one that sorts

Stopping at `stage < n` costs exactly one merge, and that merge
is the one that turns a bitonic sequence into a sorted array. The result looks
plausible — it rises, then falls — and it is wrong.

## Hint 3 — the first few pairs

A correct schedule starts

```js
[[2,1], [4,2], [4,1], [8,4], [8,2], [8,1], [16,8], …]
```

— stride 2 *before* stride 1 inside stage 4, not after.

## Same idea elsewhere

A host-side loop issuing one kernel launch per pass is exactly how bitonic sort
ships in practice: CUDA samples launch `bitonicSortShared` once per (stage,
stride), WebGPU records one dispatch per pass into a command encoder, and Metal encodes one
compute pass each. The launches are the synchronisation — everything within a pass is
independent, and the boundary between passes is the only barrier anyone needs.

## Starter code

```js
// The schedule first, the data second. One kernel launch per pass.
const gpu = new GPU({ mode });
const n = 256;

const pass = gpu.createKernel(function (data, stage, stride) {
  const i = this.thread.x;
  const strideBit = Math.floor(i / stride) % 2;
  const dirBit = Math.floor(i / stage) % 2;

  let partner = i - stride;
  if (strideBit === 0) partner = i + stride;

  const me = data[i];
  const other = data[partner];
  if (strideBit === dirBit) return Math.min(me, other);
  return Math.max(me, other);
}, { output: [n] });

const schedule = [];
// TODO: fill `schedule` with every [stage, stride] pair — stages doubling
// 2 → n, and within each stage strides halving stage / 2 → 1.
// Notice that nothing in here can look at `data`. That is the point.

console.log('passes:', schedule.length);
console.log('schedule:', JSON.stringify(schedule));

// Float32Array from the start: gpu.js locks an argument's type on the first
// call, and every pass hands back a Float32Array.
let values = Float32Array.from(data);
for (let i = 0; i < schedule.length; i++) {
  values = await pass(values, schedule[i][0], schedule[i][1]);
}

console.log('smallest:', values[0]);
console.log('largest:', values[n - 1]);
```

---

Interactive version: https://gpu.rocks/learn/bitonic-sort-84e0728e/4

[Previous task](https://gpu.rocks/learn/bitonic-sort-84e0728e/3.md) · [Next task](https://gpu.rocks/learn/bitonic-sort-84e0728e/5.md)