Speedup and Its Limits

Part of: Computer Systems & Networks

Measuring the Benefit of Parallelism The whole point of parallel computing is to finish sooner. We measure that benefit as speedup : If a task takes 60 seconds on one processor and 20 seconds when split across processors, the speedup is 3. A speedup of 1 means no improvement; a speedup of 4 means four times faster. Why Speedup Has a Ceiling You cannot always cut time perfectly, because some parts of a program must run in order. You cannot frost a cake before baking it. The portion of work that can be parallelized determines the maximum gain. This idea is captured by Amdahl's Law . If a fraction p of the work can be parallelized across n processors and the rest (1 - p) must stay sequential, then: Optional enrichment: the AP CSP exam only expects speedup = sequential / parallel and the qualitative idea that the sequential part limits gains. The Amdahl's Law formula below goes beyond the exam and is here to sharpen your intuition, not to memorize. The Sequential Part Dominates Notice what happens as n grows very large: p / n shrinks toward zero, so speedup approaches 1 / (1 - p). With 10% sequential work, the speedup can never exceed 10, no matter how many processors you add. The sequ

Challenge: Amdahl's Law Speedup