liveBook · Manning

Critical path

As explained in Grokking GPU Programming

The critical path is the longest chain of dependent steps that must execute sequentially in a computation.

A computation may contain many tasks that can run at once, but some steps depend on earlier ones. The critical path is the longest chain of steps that must run one after another. Adding helpers can speed up independent work, but it cannot shorten this chain. section 1.5

A sequential bottleneck

If 10% of a program must run sequentially, that portion limits the total speedup: even infinitely many cores cannot make the program more than 10× faster. The sequential work forms the bottleneck on the critical path. section 1.5

Table 1.1 Speedup with 10% sequential code. Amdahl’s Law assumes a fixed problem, so extra cores give diminishing returns and stall at 10×. Gustafson’s Law assumes the problem grows with the cores, so speedup keeps climbing.
Cores
Amdahl speedup
Gustafson speedup
2
1.8×
1.9×
4
3.1×
3.7×
8
4.7×
7.3×
∞
10× (hard ceiling)
keeps growing

Compare predicted speedups as core counts rise under Amdahl’s fixed-problem assumption and Gustafson’s growing-problem assumption. section 1.5

How Grokking GPU Programming covers it

How deep it goes
Defines the critical path and connects it to speedup ceilings, without detailing how to identify paths in code.
Examples
Uses a program with 10% sequential work and compares speedup predictions across core counts.
What you can do after
Evaluate whether parallelization is worthwhile by estimating its best possible speedup from the sequential fraction.
How it connects
Connects critical paths to Amdahl’s law, Gustafson’s law, and parallelization.

Also explained in

Compare how 2 books explain critical path →

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.