speedups

Speedup is a performance metric used to quantify how much faster a task runs under an improved method or with more resources compared to a baseline. It is commonly used in computing, where the baseline is often a sequential implementation and the improved method may use parallel processing, optimized algorithms, or faster hardware.

The speedup factor S is defined as S = T1 / Tp, where T1 is the execution time with the baseline method (typically on a single processor) and Tp is the execution time with p processing units or under the improved method. If Tp equals T1, the speedup is 1; if Tp is smaller, the speedup is greater than 1. In parallel contexts, speedup often reflects how effectively additional processors reduce total time.

Speedups arise from several sources. Algorithmic speedups come from faster or more efficient algorithms. Architectural speedups come from faster hardware or specialized accelerators. Parallel speedups come from distributing work across multiple cores or machines. In performance analysis, strong scaling measures how the speedup changes for a fixed problem size as more resources are added, while weak scaling measures speedup as the problem size grows with the resources.

Limitations and theoretical bounds are common considerations. Amdahl's Law provides an upper bound on speedup based on the parallelizable fraction of a task: S(p) ≤ 1 / ((1 − f) + f/p). Overheads from synchronization, communication, and memory bandwidth can significantly reduce achievable speedups. Practical evaluation typically pairs speedup with efficiency, defined as S(p)/p, to reflect resource utilization.