liveBook · Manning

Three-step recipe

As explained in Grokking GPU Programming

The three-step recipe is a shared-memory workflow of loading data, collaborating on it within a block, and writing results back.

When threads can reuse data, shared memory can keep it close while they work. The three-step recipe organizes that work: load data from global memory, collaborate on it inside a block, then write results back. section 11.14 section 11.0

The steps stay the same; the collaboration changes with the task:

  • Load: threads cooperatively bring data into shared memory. section 11.5
  • Collaborate: threads work on the data inside the block, using synchronization where one thread needs another’s writes. section 11.14
  • Write back: store the results in global memory. section 11.5

For a reduction, threads load values, combine them in a stride-halving tree, and write the block’s total. Use shared memory when data is reused—or when it helps coalesce accesses; otherwise, synchronization overhead may bring no benefit. section 11.5 section 11.14

Figure 11.4 The 3-Step Recipe applied to a parallel prefix sum. Step 2 runs in two phases: an up-sweep that combines values toward a single total, then a down-sweep that redistributes partial sums until every slot holds its own prefix, with a __syncthreads() barrier after each round. Time flows downward, and each solid arrow is one thread’s work during that round; the curve marks the time when each thread executes the __syncthreads() statement, the empty space below the curve depicts the time that thread waits for all threads to complete, and the horizontal line marks the time when the last thread executes __syncthreads(), after which all threads proceed together. Between the two phases, the seed step (one thread overwriting sdata[7], the total, with the identity 0, behind its own barrier) is omitted from the diagram for simplicity. Unlike reduction, Step 3 writes the whole array back to global memory.

See the recipe applied to a prefix sum: the threads perform an up-sweep and down-sweep, with barriers between rounds. section 11.5

How Grokking GPU Programming covers it

How deep it goes
Explains the three stages through reductions, scans, histograms, and tiled multiplication, including synchronization needs.
Examples
Uses a stride-halving reduction, Blelloch scan, shared-atomic histogram, and tiled matrix multiplication as examples.
What you can do after
Apply the recipe to structure shared-memory algorithms around cooperative loading, block-level work, and write-back.
How it connects
Connects shared memory with parallel reduction, parallel scan, histograms, and tiled matrix multiplication.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking GPU Programming. The section links point to the parts of the book it draws on.