liveBook · Manning

Parallelism

As explained in Grokking GPU Programming

Parallel computing is the execution of computational work simultaneously across multiple processing units.

Doubling a thousand numbers one at a time is straightforward, but each element can be doubled without waiting for the others. Parallelism puts multiple processing units to work at the same time on pieces of a problem. The key question is not just how many units are available, but which pieces can run independently. section 1.4 section 1.5

Doubling an array

A scalar loop doubles data[0], then data[1], and continues through data[999]: 1,000 element operations in sequence. A GPU-style approach assigns one thread to each element, so many elements can be processed at once. This is data parallelism: the same operation on different data. The contrast is simplified: CPUs can also process multiple values with SIMD, and a GPU schedules threads in groups rather than running all 1,000 literally at once. section 1.4 section 1.3

Figure 1.2 Parallel processing: every element at once. A GPU assigns one thread per element, doubling all 1,000 values in parallel; the hardware schedules those 1,000 threads onto its many CUDA cores.

Follow the assignments from GPU threads to array elements to see how the work is divided. section 1.4

A task is a piece of work, such as doubling one element or adding two numbers. If one task needs another’s result, there is a data dependency. That dependency limits what can run at once, but it does not always make the entire problem sequential. In a tournament-style sum, additions within a round can run in parallel, while each round waits for the preceding one. section 1.5

A common mistake is to assume that adding cores guarantees a proportional speedup. Sequential work sets a limit: if 10% of a fixed problem must run sequentially, even infinitely many cores cannot make the whole program more than 10 times faster. This is Amdahl’s Law. Gustafson’s Law considers a different situation, where the problem grows with the number of cores. section 1.5 section 1.10

Parallel work takes several forms:

  • Data parallelism applies the same operation to many values, as in array doubling. Task parallelism runs different operations concurrently, such as compressing one file while encrypting another. section 1.3
  • MPI coordinates work across machines; OpenMP distributes work across shared-memory CPU cores; SIMD applies one instruction to several values within a core. section 1.3
  • CPUs and GPUs can work together: the CPU runs the main program, while the GPU handles large parallel jobs. Independent, regular work suits the GPU; small or dependency-heavy jobs may favor the CPU. section 1.10

How Grokking GPU Programming covers it

How deep it goes
Defines parallelism and dependencies, works through array doubling and speedup limits, and defers performance techniques.
Examples
Uses array doubling, tournament-style summation, Fibonacci, and a program with 10% sequential work to illustrate parallel opportunities and limits.
What it assumes
Assumes familiarity with C loops and function calls, while introducing parallel programming without requiring a GPU.
What you can do after
Evaluate potential parallel work by identifying dependencies and recognizing how sequential portions limit speedup.
How it connects
Connects data and task parallelism to dependencies, SIMD, reduction, scan, and Amdahl’s and Gustafson’s laws.

Also explained in

Compare how 55 books explain parallelism →

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.