11.02 · Lecture
When Machines Make It Slower
Use the work law and the span law to bound the maximum speedup available from parallelism, so you can see the ceiling before you buy machines.
Parallelism has a hard ceiling set by total work and the critical path. The work law says processors cannot do less than the total work divided across them; the span law says dependencies still take their sequential time. Together they show when more pods, workers or executors cannot improve latency.
What this lesson answers
- why does adding machines make jobs slower
- how to estimate maximum parallel speedup
- when do more workers stop helping
Notes
Work and Span Laws — Work and span laws exist to bound parallel speedup before adding machines; without them, teams can overbuy cores or nodes for workloads whose serial dependency chain makes faster completion impossible.
Key Concepts: - Work law: runtime on processors is bounded by , where is total work on 1 processor. - Span law: runtime on processors is bounded by , where is the critical-path time with infinite processors. - Combined lower bound: .
References
Common questions
- What is the work law in parallel systems?
- The work law says a parallel run cannot be faster than dividing the total amount of work by the number of processors. It is an optimistic lower bound, because it ignores coordination, queues, locks and communication. If that bound is already too slow, adding orchestration will not save the design.
- What is the span law?
- The span law says a job cannot finish faster than its longest chain of dependent steps, even with unlimited processors. That chain is the critical path. Serial phases, locks, ordered migrations, single reduce stages and external calls all increase span and place a hard limit on latency improvement.
- How do I know whether more workers will help?
- Estimate total work and the critical path. More workers help while the divided work term dominates. Once the critical path dominates, extra workers mostly add scheduling, contention and cost. Traces, stage DAGs and task timelines are useful because they show whether time is spent in parallel work or unavoidable dependency chains.