Measuring Real Speedup Against Amdahl's Ceiling

Every earlier lesson in this track measured a real improvement from parallelism. This one measures the point where more threads stop helping — and shows that even the theoretical ceiling for how much they should help is itself an optimistic upper bound.

A program with a fixed serial cost and a scalable parallel cost

// amdahl.c
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

int main(int argc, char** argv) {
    int nthreads = atoi(argv[1]);
    omp_set_num_threads(nthreads);

    long n = 800000000L;
    double serial_result = 0;
    double t0 = omp_get_wtime();

    // Fixed serial setup: always runs on one thread, regardless of nthreads
    for (long i = 0; i < 200000000L; i++) {
        serial_result += 1.0 / (1.0 + (i % 13));
    }
    double t_serial = omp_get_wtime();

    // Parallel portion: this part actually scales with thread count
    double parallel_result = 0;
    #pragma omp parallel for reduction(+:parallel_result)
    for (long i = 0; i < n; i++) {
        parallel_result += 1.0 / (1.0 + (i % 997));
    }
    double t1 = omp_get_wtime();

    printf("threads=%2d  serial_part=%.3fs  parallel_part=%.3fs  total=%.3fs\n",
           nthreads, t_serial - t0, t1 - t_serial, t1 - t0);
    return 0;
}

gcc -fopenmp -O2 -o amdahl amdahl.c
./amdahl 1

threads= 1  serial_part=0.411s  parallel_part=1.726s  total=2.136s

Measuring speedup as thread count scales

./amdahl 2
./amdahl 4
./amdahl 8
./amdahl 12
./amdahl 24

threads= 2  serial_part=0.434s  parallel_part=1.177s  total=1.611s
threads= 4  serial_part=0.367s  parallel_part=0.726s  total=1.092s
threads= 8  serial_part=0.334s  parallel_part=0.485s  total=0.819s
threads=12  serial_part=0.332s  parallel_part=0.411s  total=0.742s
threads=24  serial_part=0.322s  parallel_part=0.459s  total=0.781s

The serial part stays essentially flat (0.33-0.43s) at every thread count, exactly as it should — nothing about it can parallelize. The parallel part keeps shrinking as threads increase, but the serial part’s fixed cost matters more and more as it does.

Speedup climbs from 1.00x to 2.88x as threads go from 1 to 12 — a 12x increase in threads bought only a 2.88x increase in speed. Going further, to 24 threads, made it worse (2.73x), not better.

Where the Amdahl-predicted column comes from

The serial fraction at 1 thread is 0.411 / 2.136 ≈ 19% — plugging that into Amdahl’s formula, speedup(N) = 1 / ((1-p) + p/N) with p ≈ 0.81, gives the predicted column above. As N grows without bound, that formula approaches 1 / 0.19 ≈ 5.2x — a hard ceiling this program can never exceed no matter how many threads it’s given, because roughly a fifth of its total work is permanently stuck running on one thread.

Notice that measured speedup falls short of the Amdahl prediction at every single thread count — 2.88x measured versus 3.85x predicted at 12 threads, for instance. Amdahl’s formula only accounts for the serial-vs-parallel split; it assumes the parallel portion scales with zero overhead. Real thread creation, the reduction clause’s combining step, and cache effects between cores are all real costs the idealized formula doesn’t model — so measured results are reliably worse than the prediction, never better.

Why 24 threads made things worse, which Amdahl’s formula can’t explain at all

Amdahl’s Law has no concept of a physical core count — it models N as an abstract number of available processors. This machine has 12 real cores; 24 threads is 2x oversubscription, which the earlier oversubscription lesson already showed carries a real, measured penalty. Amdahl’s ceiling (~5.2x) and this machine’s hardware limit (12 real cores) are two separate limits, and this program’s speedup curve bends because of the hardware limit well before Amdahl’s theoretical ceiling would have mattered on its own.

Practice

That closes the track. The thread through all eight lessons: parallelism only does what you explicitly divide, protect, or combine — and even done correctly, how much it can help is bounded by both a program’s own serial fraction and the real hardware underneath it, neither of which more threads alone can fix.