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
