Speedup

Speedup is a measure of performance improvement obtained when a system, algorithm, or process is enhanced relative to a baseline. It is commonly defined as S = T1 / Tp, where T1 is the execution time of the reference (baseline) version and Tp is the execution time of the improved version. A higher speedup indicates greater performance gain. Speedup can apply to hardware upgrades, software optimizations, or changes in problem size or workload.

In parallel computing, speedup describes how the execution time changes when a task is distributed across multiple processing elements. If a task on p processors yields Tp and the baseline time is T1, the speedup is S(p) = T1 / Tp. Ideal, linear speedup occurs when S(p) equals p, but real systems often fall short due to overhead, synchronization, and non-parallelizable work.

Amdahl's law provides a bound on achievable speedup given a non-parallelizable portion of a task. If a fraction f of the task can be parallelized, the maximum speedup with p processors is S(p) = 1 / ((1 - f) + f/p). As p grows, the speedup approaches 1/(1 - f), highlighting how the serial portion limits improvement regardless of additional processors.

Gustafson's law offers an alternative perspective, arguing that with larger problem sizes, the parallel portion can dominate and scalable speedup can improve roughly linearly with p under certain conditions. Practical speedups are influenced by factors such as memory bandwidth, communication overhead, load balancing, and algorithmic changes.

Applications of speedup analysis include performance engineering, benchmarking, and guiding decisions about hardware upgrades or parallelization strategies.