Task 2 of 6

The Butterfly: One Thread, One Output

Written as a recursion the split is elegant and useless: a GPU cannot recurse, and allocating a tree of half-length arrays would cost more than the arithmetic saves. Turn it inside out instead. Every level of that recursion is one pass over the whole array, and every pass is the same tiny operation repeated: take two elements a and b, and produce

a + w·b        and        a - w·b

Two in, two out, one twiddle factor w. Drawn on paper the crossing lines look like a butterfly, and the name stuck.

Here is where a half-remembered recursive formulation has to be let go. A thread does not own a pair and write two cells — it owns one output cell, exactly as everywhere else in this course, and it works out for itself which two inputs and which twiddle that cell needs. Nothing is ever swapped. Given the pass's half-block size half, thread i asks three questions:

// am I the lower member of my pair, or the upper?
const j = Math.floor(i / half) % 2;
// where the LOWER member of my pair sits
const base = i - j * half;
// my position inside the half-block
const r = i % half;

Then a is element base, b is element base + half, and w = e^(-iπ·r / half). Both members of a pair compute the same w and read the same two elements; they differ only in the sign between them. No communication, no barrier inside a pass — the same reason the halving ladder in Reductions needs none.

twelve butterflies, and which pair you belong to is a fact about your index

Goal: write one butterfly pass over the 8-point complex spectrum — the kernel takes (spectrum, half) and returns one number per output cell.

Requirements

Work out base and r from this.thread.x and half alone
Read both planes of both elements — a complex multiply needs all four numbers
Return a + w·b at the lower index and a - w·b at the upper one
It must be right for half = 1, 2 and 4

Hint 1 — which pair am I in?

At half = 2 the eight threads split 0,1 | 2,3 | 4,5 | 6,7 into blocks of four: threads 0, 1, 4, 5 have j = 0 and pair upward; threads 2, 3, 6, 7 have j = 1 and pair downward. Subtracting j * half lands both members of a pair on the same base.

Hint 2 — which twiddle?

r = i % half is your position inside the half-block, and it is all w depends on. At half = 1 every r is 0, so w = 1 and the first pass is pure addition and subtraction — which is why a sign mistake in the twiddle will not show up until half = 2.

Hint 3 — the ending

Compute the whole complex result, then return only the half this thread's plane asked for:

const tr = wr * br - wi * bi;
const ti = wr * bi + wi * br;
if (this.thread.y === 0) {
  if (j === 0) return ar + tr;
  return ar - tr;
}
if (j === 0) return ai + ti;
return ai - ti;

Same idea elsewhere

The butterfly is gather-shaped on every platform, for the reason Thinking in Parallel gives: a thread writes its own cell and nobody else's. CUDA's cuFFT keeps a whole radix-N butterfly in registers and exchanges through shared memory or __shfl_xor_sync; WGSL and Metal compute shaders do the same through workgroup memory plus a barrier. What none of them do is have one thread write two results.

All tasks in The FFT Butterfly

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