liveBook · Manning

Span

As explained in Grokking GPU Programming

Depth is the number of sequential steps in a parallel algorithm assuming unlimited processors; it is also called span.

Span is the number of sequential steps in a computation, assuming unlimited processors. Also called depth, it measures the length of the dependency chain—not the total number of operations. section 6.1

Keep span distinct from total work:

  • Work counts all operations across the threads. section 6.1
  • Span counts sequential rounds: operations that depend on earlier results cannot proceed until those results are ready. section 6.1

Grading exams

If 1,000 students each grade an exam simultaneously, the work is 1,000 exams, but the span is one exam’s worth of time. If each student must wait for the previous student’s result, the dependency chain increases the span. section 6.1

Scan and reduction

A sequential scan performs n−1 additions in n−1 steps because each running total depends on the previous one. A reduction tree performs the same n−1 additions in ⌈log₂(n)⌉ rounds, showing how parallel organization can reduce span without reducing work. section 6.1

How Grokking GPU Programming covers it

How deep it goes
Defines span as sequential steps with unlimited processors and illustrates it with scan and reduction examples.
Examples
Uses an exam-grading analogy, sequential scan, reduction tree, and parallel stencil computation.
What it assumes
Builds on informal exposure to work and depth through reduction trees while defining both measures formally.
What you can do after
Evaluate how dependency chains and parallel rounds affect an algorithm’s idealized execution time.
How it connects
Connects span to work, scan, reduction trees, and parallel algorithms.

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.