Amdahl’s Law: The Serial Part Sets the Ceiling

By Sergey Nosov

16 October 2026

Late in 1985, Alan Karp, a staff scientist at IBM, had just returned from a SIAM conference on parallel processing in Norfolk, Virginia. He had heard about systems with 1,000 and 4,000 processors there, and even a proposed one with 1,000,000. He wondered whether such machines were the best way to do general-purpose scientific computing, so he made an offer:

I will pay $100 to the first person to demonstrate a speed-up of at least 200 on a general purpose, MIMD computer used for scientific computing. This offer will be withdrawn at 11:59 PM on 31 December 1995.

A 2017 history of the Gordon Bell Prize, which Karp coauthored, records his answers to a reporter. Why the prize? “Because I don’t think anyone can do it.” And why only $100? “Because somebody might.”

Somebody did, against a law that seemed to rule it out. The idea behind Amdahl’s Law fits in one line: the serial part of a job decides how far parallel effort can take it. If even 1 percent of a job cannot run in parallel, no number of processors can make it run more than one hundred times as fast. Karp had asked for twice that.

At Sandia National Laboratories, John Gustafson, Gary Montry, and Robert Benner ran three full-scale applications, in wave mechanics, fluid dynamics, and structural analysis, on an nCUBE hypercube. It was a MIMD machine with 1,024 processors, each running its own instructions. Their 1988 paper reports it running 502 to 637 times as fast as one processor on problems of a fixed size. The team took home Karp’s prize and the first Gordon Bell Prize, offered by Bell, a pioneer of parallel computing, for the best speedup on a real application.

Sandia did not prove Amdahl wrong; it kept the serial part of its programs tiny. The team’s paper also reports a second set of speedups, 1,009 to 1,020, for problems that grew with the machine. Both sets are honest; they answer different questions.

This article works through the law’s arithmetic, finds and shrinks the serial part of a C# batch job, and measures what remains with a metric Karp later helped create. Then it covers the two ways the ceiling moves. It falls when workers get in one another’s way, and it rises when the problem grows with the machine but its serial part does not.

The Law

Time a job on one worker, and divide that time into two parts. The serial fraction, s, must run one step after another; the rest, 1 − s, can be split among workers, whether cores, threads, or machines. With N workers, the parallel part takes (1 − s)/N of the original time at best, and the serial part takes as long as ever. Speedup is the old time divided by the new one:

speedup(N) = 1 / (s + (1 − s) / N)

Now let N grow without limit. The second term shrinks toward zero, and the speedup approaches 1/s. The number of workers drops out of the answer. A job that is 5 percent serial can never run more than twenty times as fast, however many cores it gets.

Efficiency is the speedup divided by N: the share of the workers’ time that goes to useful work. For the same job, 95 percent parallel:

  N   speedup   efficiency
  1      1.00         100%
  2      1.90          95%
  4      3.48          87%
  8      5.93          74%
 16      9.14          57%
 32     12.55          39%
  ∞     20.00            —

Eight workers run the job 5.93 times as fast as one, but on average they sit idle 26 percent of the time, waiting for the serial part to finish. Efficiency falls to one-half at twenty-one workers; in general, it is one-half at N = 1 + 1/s. Past that point, most of the worker time you pay for goes to waiting.

Drawn as bars, the same job shows why. Each doubling of the workers halves the parallel part, and the serial part never moves:

Run time, as a share of one worker’s N 1 2 4 8 16 ∞ 100% 52.5% 28.8% 16.9% 10.9% 5% Serial: 5 percent, never shrinks Parallel: 95 percent, divided by N

Flip it around: if only half the work can run in parallel, the speedup can never exceed two, no matter how many cores you buy.

What Amdahl Argued

Gene Amdahl, then at IBM, made the argument in April 1967 at the AFIPS Spring Joint Computer Conference in Atlantic City. His paper, “Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities,” runs three pages and opens with a jab at the parallel enthusiasts of his day:

For over a decade prophets have voiced the contention that the organization of a single computer has reached its limits and that truly significant advances can be made only by interconnection of a multiplicity of computers in such a manner as to permit cooperative solution.

The paper has no formula: when the IEEE Solid-State Circuits Society reprinted it in 2007, its editors noted that “it has no equations and only a single figure.” The formula above is how later writers state the argument; Gustafson’s 1988 note, for one, gives it as what “Amdahl’s law says.”

Amdahl argued from statistics on real computing instead. He reported that “data management housekeeping” accounted for 40 percent of the instructions executed in production runs, and that this overhead appeared to be sequential. In a dedicated special-purpose setting, he judged, the share might be halved but was highly unlikely to fall to a third. “Overhead alone would then place an upper limit on throughput of five to seven times the sequential processing rate,” he wrote.

Treat a share of the instructions as a share of the time, and the formula gives the same ceilings. Halve 40 percent, and one-fifth of the time stays serial, which caps the speedup at five. Cut the share nearly to a third, and the ceiling nears seven. His conclusion was about where to spend effort:

A fairly obvious conclusion which can be drawn at this point is that the effort expended on achieving high parallel processing rates is wasted unless it is accompanied by achievements in sequential processing rates of very nearly the same magnitude.

He also weighed another design: two processors sharing one memory. Conflicts over the memory, he estimated, would leave the pair about 1.8 times as fast as one processor, not twice as fast. Interference between workers, the subject of a later section, was part of the argument from the start.

Spot the Serial Part

Here is the shape of a batch job in C#. It loads a configuration, checks each record, analyzes the valid ones in parallel, and then scores the results and adds them up:

static double Original(int[] records, int workers)
{
    // Serial: runs once.
    double config = LoadConfig();

    // Serial: checks every record
    // before the loop starts.
    int[] valid = records
        .Where(r => IsValid(r, config))
        .ToArray();

    // Parallel: the analysis.
    var results = new ConcurrentBag<double>();
    var options = new ParallelOptions
        { MaxDegreeOfParallelism = workers };
    Parallel.ForEach(valid, options, record =>
        results.Add(Analyze(record, config)));

    // Serial: scores and adds up
    // the results on one thread.
    return results.Sum(Score);
}

Only the middle runs in parallel. LoadConfig, the Where filter, and the final Sum, which also scores each result, all run on one thread. In the experiment below, these three steps take about 5 percent of a sequential run. Amdahl’s Law then caps sixteen workers at about 9.1 times and any number at about twenty.

What about the ConcurrentBag? Shared state is a classic hiding place for serial work, but the adds here almost never wait for one another. In the .NET 10 source, each thread adds to a queue of its own, created by its first add under a bag-wide lock. After that, the thread locks its queue only when the queue is nearly empty, nearly full, or being read. The real serial cost comes after the loop: enumerating the bag locks every queue and copies every item, and then the scoring runs on one thread.

Shrink the Serial Part

Adding workers shortens only the middle. To raise the ceiling, move work out of the serial steps. Validation looks at one record at a time, and so does scoring. Neither writes to shared state, so both can run inside the loop. The sum can be split too. Each partition keeps its own subtotal, and the subtotals are added at the end, the pattern Microsoft documents as a Parallel.ForEach loop with partition-local variables:

static double Reshaped(int[] records, int workers)
{
    // Serial: runs once.
    double config = LoadConfig();

    // Parallel: every partition
    // validates, analyzes, and
    // scores its records, keeping
    // a subtotal of its own.
    double total = 0;
    var gate = new object();
    var options = new ParallelOptions
        { MaxDegreeOfParallelism = workers };
    Parallel.ForEach(records, options,
        () => 0.0,
        (record, _, subtotal) =>
            IsValid(record, config)
                ? subtotal + Score(Analyze(record, config))
                : subtotal,
        subtotal => { lock (gate) total += subtotal; });

    // Serial: only the return.
    return total;
}

Now LoadConfig is the only large serial step. The lock in the last argument runs once per partition, not once per record, so here it costs almost nothing. Microsoft’s list of pitfalls for parallel loops gives the general rule: “avoid, or at least limit, access to shared state in a parallel loop as much as possible.”

Not every step splits this way. A sum, a count, a minimum, or a maximum can be combined from one number per part. A median cannot: the medians of the parts do not give the median of the whole. A floating-point sum may still differ from the sequential one in the last digits, because the subtotals group the additions differently.

A check that compares records with one another, such as a search for duplicates, cannot simply move into the loop either. Before moving a step, ask whether its work on one item depends on other items or their order, and whether it writes to anything the workers share.

Measure, Do Not Guess

Reading the code gives a first estimate of the serial fraction, not the final one. Locks, memory traffic, I/O, and the hardware itself add costs that the code does not show, and only a measurement catches them.

Karp’s offer defined speedup as the time on one processor “using the best sequential algorithm” divided by the time on N processors. His ground rules added, “It is not fair to cripple the sequential processor.” A parallel loop limited to one worker is not that baseline. The baseline is the fastest sequential version you have, with no parallel machinery: here, a plain loop.

In 1990, Karp and Horace Flatt, both at IBM’s scientific center in Palo Alto, published a way to turn measured speedups into a serial fraction. Solve Amdahl’s formula for s, using the speedup you measured on N workers:

e = (1/speedup − 1/N) / (1 − 1/N)

Karp and Flatt called e the experimentally determined serial fraction. If a job behaved exactly as Amdahl’s model assumes, e would come out the same at every N. If e grows as you add workers, something besides the serial code grows with them: contention, communication, or work that does not divide evenly. At small worker counts, e is noisy. For a job that scales like the 95 percent parallel one, a 1 percent timing error moves e by about 0.01 at two workers and about 0.001 at sixteen.

Apply it to Sandia’s fixed-size speedups: 637 on 1,024 processors gives an e of 0.0006, and 502 gives 0.0010. In Amdahl’s terms, the programs behaved as if 0.06 to 0.10 percent of their work were serial.

Here is the rest of the program, which measures both versions. It times the plain loop as the baseline, then each version at two, four, eight, and sixteen workers, keeping the best of five runs:

// batch.cs: an Amdahl experiment.
// To run it:
// dotnet run -c Release batch.cs
using System.Collections.Concurrent;
using System.Diagnostics;

var records = Enumerable.Range(1, 1_000).ToArray();
double t1 = BestTime(() => Sequential(records));
Measure("original", w => Original(records, w));
Measure("reshaped", w => Reshaped(records, w));

// Baseline: the same work in a
// plain loop, no parallel code.
static double Sequential(int[] records)
{
    double config = LoadConfig();
    double total = 0;
    foreach (int record in records)
        if (IsValid(record, config))
            total += Score(Analyze(record, config));
    return total;
}

// Speedup over the baseline,
// efficiency, and the Karp-Flatt
// serial fraction e.
void Measure(string name, Func<int, double> run)
{
    Console.WriteLine(name);
    Console.WriteLine("  N  speedup   eff      e");
    foreach (int n in new[] { 2, 4, 8, 16 })
    {
        double speedup = t1 / BestTime(() => run(n));
        double e = (1 / speedup - 1.0 / n) / (1 - 1.0 / n);
        Console.WriteLine(
            $"{n,3} {speedup,8:F2} {speedup / n,5:P0} {e,6:F3}");
    }
}

// Best of five runs, after a
// warm-up run.
static double BestTime(Func<double> run)
{
    run();
    double best = double.MaxValue;
    for (int i = 0; i < 5; i++)
    {
        var clock = Stopwatch.StartNew();
        run();
        best = Math.Min(best, clock.Elapsed.TotalMilliseconds);
    }
    return best;
}

// Stand-ins for real work. Each
// burns a fixed amount of CPU, so
// the serial steps take about 5
// percent of a sequential run.
static double LoadConfig() => Spin(8_000_000);
static bool IsValid(int record, double config) =>
    Spin(6_000) > 0;
static double Analyze(int record, double config) =>
    Spin(400_000) + record;
static double Score(double result) =>
    Spin(7_000) + result;

static double Spin(int steps)
{
    double x = 1;
    for (int i = 0; i < steps; i++)
        x = Math.Sqrt(x + i);
    return x;
}

Save it as batch.cs in a folder of its own, add the two methods from above at the end, and run the command in the comment at the top. With the .NET 10 SDK or later, dotnet run accepts a single file like this, with no project file. Keep -c Release, because dotnet run builds the Debug configuration by default. On an AMD Ryzen 9 7950X desktop with sixteen cores and thirty-two hardware threads, one run printed this:

original
  N  speedup   eff      e
  2     1.91   95%  0.050
  4     3.42   86%  0.056
  8     5.85   73%  0.053
 16     8.49   53%  0.059
reshaped
  N  speedup   eff      e
  2     1.96   98%  0.022
  4     3.77   94%  0.020
  8     6.89   86%  0.023
 16    11.06   69%  0.030

The original version’s e stays between 0.05 and 0.06, close to the 5 percent its serial steps take. The reshaped version’s e runs from 0.020 to 0.030; through eight workers, it stays close to the 1.9 percent that LoadConfig alone takes. At sixteen workers, reshaping lifted the speedup from 8.49 to 11.06. Shrinking the serial part can beat adding workers. Counting only the serial steps, reshaping raised the ceiling from about twenty to about fifty without adding a core.

Both columns of e rise at sixteen workers, and a small part of the rise is the machine itself. A separate test on this machine ran sixteen copies of the same work at once, each pinned to its own core with nothing shared. Each took about 2 to 4 percent longer than one copy alone. The metric points at a problem; a profiler has to find it.

When More Workers Make It Slower

In Amdahl’s model, an extra worker can be wasted but never harmful: each one raises the speedup, however slightly. Real systems can break that rule. Suppose someone adds a progress counter to Spin, the loop that burns CPU time in each stand-in. It looks harmless:

static double Spin(int steps)
{
    double x = 1;
    for (int i = 0; i < steps; i++)
    {
        x = Math.Sqrt(x + i);
        // A step counter shared by
        // every worker.
        Interlocked.Increment(ref Stats.Steps);
    }
    return x;
}

static class Stats { public static long Steps; }

Replace Spin with this version, and put the class at the end of the file. One run printed this:

original
  N  speedup   eff      e
  2     0.92   46%  1.183
  4     0.88   22%  1.178
  8     0.66    8%  1.601
 16     0.45    3%  2.324
reshaped
  N  speedup   eff      e
  2     0.90   45%  1.224
  4     0.87   22%  1.196
  8     0.69    9%  1.512
 16     0.43    3%  2.388

Every speedup is below 1, so every e is above 1, a value no serial fraction can take. At sixteen workers, the parallel versions take more than twice as long as the plain loop.

Interlocked.Increment keeps the count right, but every worker now writes to one counter. To write it, a core must hold the only valid copy of the cache line that contains it, the small block of memory that caches move as a unit. That line passes from core to core again and again, and the cores wait for it instead of working.

The fix is the same move as the subtotals above: count in a local variable, and add the count to the shared total once per call. In one run, the sixteen-worker speedups came back to 8.58 for the original and 11.20 for the reshaped version.

Neil Gunther’s Universal Scalability Law describes this shape. It adds a second cost to Amdahl’s:

capacity(N) = N / D, where
D = 1 + σ(N − 1) + κN(N − 1)

Here σ (sigma) is contention, the serial fraction; with κ (kappa) at zero, the formula is Amdahl’s Law. Coherency, κ, is the cost of keeping the workers’ copies of shared data consistent. It is multiplied by N(N − 1), which grows with the number of pairs of workers, so any κ above zero puts a peak in the curve. The peak comes near N* workers:

N* = √((1 − σ) / κ)

If N* is below one, throughput is highest at one worker. Beyond the peak, Gunther writes in a 2008 paper, “the throughput becomes retrograde”: each added worker lowers it. The effect, he notes, “is commonly observed in applications that involve shared-writable data,” and a shared counter is exactly that. With it, each doubling of the workers makes both versions slower.

Gustafson’s Counterpoint

So how did Sandia pass 1,000 on 1,024 processors? In his note in Communications of the ACM, Gustafson argued that Amdahl’s formula holds the parallel work constant as processors are added, which is “virtually never the case.” In his words, “in practice, the problem size scales with the number of processors.” Given a bigger machine, users usually raise the grid resolution or the number of time steps to fit a desired run time. So it may be most realistic, he wrote, to assume “run time, not problem size, is constant.”

What matters is which part grows. As a first approximation, he reported, it is the parallel part that scales with the problem. The times for “vector start-up, program loading, serial bottlenecks, and I/O,” which make up s, do not grow with it. Measure s as a share of the run on the parallel machine. While that share stays fixed as N grows, the speedup over a serial run of the same, larger problem grows along a straight line. He called the result “an alternative to Amdahl’s law suggested by E. Barsis at Sandia”:

scaled speedup = s + (1 − s) × N
               = N − (N − 1) × s

That serial run can be hypothetical, as Sandia’s was: the larger problem never has to run on one processor. This s also differs from Amdahl’s: his is a share of the time on one worker, Gustafson’s a share of the time on N. Convert one into the other, and both formulas give the same speedup for the same run; they differ in what they ask. Amdahl’s asks how much faster a fixed job can finish; Gustafson’s asks how much more work fits in the same time.

High-performance computing calls the first strong scaling and the second weak scaling. The HPC Wiki defines strong scaling as adding processors “while the problem size remains constant.” In weak scaling, it says, “both the number of processors and the problem size are increased,” which gives “a constant workload per processor.” Sandia’s 502 to 637 was strong scaling; its 1,009 to 1,020 was weak.

The batch program shows where Gustafson’s first approximation holds and where it breaks. Give each worker its own 1,000 records, so that sixteen workers process 16,000, and time the plain loop on the same records. A variant of the program, keeping the best of three runs, printed the speedups:

  N  records  original  reshaped
  1    1,000      1.01      1.00
  2    2,000      1.91      1.99
  4    4,000      3.58      3.94
  8    8,000      6.36      7.75
 16   16,000     10.40     14.92

The reshaped version stays close to the straight line. Sixteen workers took 1.9 seconds for 16,000 records, against 1.8 seconds for one worker on 1,000. The original falls behind, because its validation and scoring are serial steps that grow with every record: the kind of serial work that approximation leaves out.

When one user waits for one answer, such as a page load or a report, the problem is fixed, and Amdahl sets the limit. When the goal is more work in the same time, such as a nightly job whose input grows with the business, Gustafson’s view applies. It holds only while the serial part stays fixed.

Beyond Processors

The arithmetic does not care what a worker is. Suppose a build pipeline spends 4 minutes compiling, 20 minutes running tests, and 6 minutes deploying. Split the tests across ten agents, and a run takes 12 minutes; across a hundred, 10.2 minutes. The 10 serial minutes cap the speedup at three. At ten agents, extra agents save at most 2 more minutes, while every minute cut from compiling or deploying comes off every run. Each agent’s own checkout and setup also acts like serial time: adding agents does not shrink it.

Teams have serial steps too. Fred Brooks put it plainly in The Mythical Man-Month in 1975: “The number of months of a project depends upon its sequential constraints.” He also counted the cost of coordination: “If each part of the task must be separately coordinated with each other part, the effort increases as n(n–1)/2.” That is the shape of the κ term in Gunther’s formula.

A queue in front of a single reviewer or a deployment window is a different shape again: a stream of work, not one job. My article on Little’s Law covers what waiting there costs. The entries on Amdahl’s and Gustafson’s laws in my Software Development Principles series carry the arithmetic into system design. They cover the critical path through a chain of service calls and the choice between latency and throughput.

Checklist

Further Reading