Gustafson's Law: Scaled Speedup = N - (1 - p)*

Performance Engineering

Meaning

Gustafson's Law predicts the scaled speedup of a parallel system when the problem size increases proportionally with the number of processors. It shows that speedup can grow linearly with N, limited only by the serial fraction of the workload.

Primary Function

Performance modeling

Communicative Purpose

Estimate achievable speedup when scaling both resources and workload size in parallel computing.

Pattern

scaled_speedup = N - (1 - p) * (N - 1)

Core Structure

scaled_speedup = N - (1 - p) * (N - 1)

Função primária

Performance modeling

Propósito comunicativo

Estimate achievable speedup when scaling both resources and workload size in parallel computing.

Situações de gatilho

High-performance computing: estimating speedup when both processors and problem size increase; Cloud services: planning resource allocation for workloads that grow with user demand; Parallel algorithm design: evaluating scalability of a data‑processing pipeline

Contextos

High-performance computing, parallel algorithm design, cloud scalability analysis, distributed systems.

Padrão

scaled_speedup = N - (1 - p) * (N - 1)

Estrutura central

scaled_speedup = N - (1 - p) * (N - 1)

Slots de substituição

N: number of processors (int >0), p: parallelizable fraction (float between 0 and 1)

Colocados típicos

Amdahl's Law
speedup metrics
parallel efficiency
scalability plots

Substituições comuns

Equivalent form: scaled_speedup = p + N * (1 - p)

Erros comuns

Using the formula for fixed problem size (Amdahl's scenario), misinterpreting p as serial fraction, forgetting to subtract 1 from N.

Similar / contraste

Amdahl's Law: Speedup = 1 / ((1 - p) + p / N); assumes fixed workload size, unlike Gustafson's scaled problem size.

Interferências

Coming from Amdahl's Law intuition: may expect diminishing returns; Gustafson shows linear scaling when workload grows with resources.

Família do chunk

Gustafson's Law
Amdahl's Law
speedup
scalability analysis
parallel efficiency

Nuance

Valid when overhead is negligible and problem size scales perfectly with processor count; less accurate for workloads with non-linear scaling or significant communication costs.

Efeito pragmático

Provides optimistic upper bound for scaling, guiding decisions on resource investment for growing workloads.

Dica de memória

More workers, bigger job: Gustafson’s linear scaling.

Nota

Assumes the parallel portion scales perfectly and communication overhead is negligible; real systems may need to account for synchronization and data‑transfer costs.

Upgrade path

Incorporate overhead and non-ideal scaling: scaled_speedup = N - (1 - p)*(N - 1) - overhead(N)

Frequência: MediumFormulaicidade: Fully fixedTipo de construção: mathematical formula representing scaled speedup under Gustafson's LawPrioridade de aquisição: Active recallPrioridade de output: BothTag de espaçamento: Medium-term

Examples

# Example 1: Compute scaled speedup for given N and p N = 8 # number of processors p = 0.9 # parallelizable fraction scaled_speedup = N - (1 - p) * (N - 1) print(f"Scaled speedup (Gustafson's Law) = {scaled_speedup:.2f}")

# Example 2: Plot speedup vs. processor count for a fixed parallel fraction import matplotlib.pyplot as plt p = 0.85 processors = range(1, 33) speedups = [n - (1 - p) * (n - 1) for n in processors] plt.plot(processors, speedups, marker='o') plt.title('Gustafson\'s Law: Scaled Speedup') plt.xlabel('Number of Processors (N)') plt.ylabel('Scaled Speedup') plt.grid(True) plt.show()

# Example 3: Compare Gustafson's and Amdahl's speedup for the same parameters import math def gustafson(N, p): return N - (1 - p) * (N - 1) def amdahl(N, p): return 1 / ((1 - p) + p / N) N = 16 p = 0.92 print(f"Gustafson speedup: {gustafson(N, p):.2f}") print(f"Amdahl speedup: {amdahl(N, p):.2f}")