Amdahl's Law

The Day IBM Learned the Hard Way

In 1964, IBM was building OS/360 — the most ambitious software project the world had ever seen. It was behind schedule. So management did the obvious thing: they hired more programmers. The project got further behind schedule.

Fred Brooks was there. He was the project manager, and he watched in real time as the act of adding people to a late project made it later. A decade later, he wrote The Mythical Man-Month, one of the most important books in the history of software engineering, and in it he crystallized the experience into what we now call Brooks's Law:1

This sounds paradoxical. More hands should mean less work per person, right? If one person can dig a ditch in six hours, surely two people can dig it in three? And sometimes they can. Ditch-digging is what computer scientists call embarrassingly parallel — you can split it into independent chunks and hand each chunk to a different person with minimal coordination.

But most interesting work isn't ditch-digging. Most interesting work has dependencies. You can't write Chapter 5 until you know how Chapter 4 ends. You can't test the payment module until the database schema is finalized. You can't frost the cake until it's baked. And every new person you add to a project needs to be brought up to speed, needs to coordinate with the existing team, needs to sit in meetings that now take longer because there are more opinions in the room.

Brooks understood this intuitively. But a computer architect named Gene Amdahl had already given it a precise mathematical formulation three years earlier, in a paper so elegant that it still makes computer scientists nod slowly when they encounter it for the first time.2

The Formula That Sets the Speed Limit

Here's Amdahl's insight, stripped to its essence: every task has some portion that must be done sequentially — one step after another, no shortcuts, no parallelism — and some portion that can be split up. The sequential part sets an absolute speed limit that no amount of parallel effort can break.

S

Speedup — how many times faster the task completes

s

Serial fraction — the portion of work that cannot be parallelized (0 to 1)

N

Number of processors (or people, or cores, or servers)

Let's make this concrete. Suppose you're cooking Thanksgiving dinner. Some tasks parallelize beautifully: one person can chop vegetables while another prepares the turkey while a third makes the pie crust. But some tasks are stubbornly serial: the turkey takes four hours in the oven no matter how many cooks you have. If that serial oven-time represents 30% of the total work, then Amdahl's Law says your maximum possible speedup is 1/0.3 ≈ 3.3×. You will never get dinner done more than 3.3 times faster, even if you hire the entire graduating class of the Culinary Institute of America.

And here's the kicker: as you throw more and more processors at the problem, the returns diminish catastrophically. Going from 1 to 2 processors gives you a lovely boost. Going from 2 to 4 gives you a smaller one. Going from 100 to 200 gives you almost nothing. The curve flattens out, approaching an asymptote like a car pressing the accelerator into the floor and watching the speedometer stubbornly refuse to budge past a certain number.3

Think about what this means. If just 5% of your task is serial — a tiny sliver! — your theoretical maximum speedup with infinite processors is 1/0.05 = 20×. Not infinity. Not a thousand. Twenty. And if 25% of your task is serial, you're capped at 4×, no matter how many billions you spend on hardware.

This is, when you think about it, a profoundly pessimistic result. It says that there's a hard mathematical wall between you and perfect parallelism, and that wall is set by the slimmest, most irreducible fraction of your work that simply must be done in sequence.

Brooks's Law, or the Meeting Problem

Gene Amdahl was thinking about computer chips. But the same mathematics applies — with even more devastating force — to people.

Here's why people are worse than processors: processors don't need to talk to each other. (Well, they do, but that's a different lecture.) When you add a person to a team, you don't just add their labor. You add a communication channel between them and every other team member. The number of pairwise communication channels in a team of N people is:

Two people have 1 communication channel. Five people have 10. Ten people have 45. Twenty people have 190. It grows quadratically, which means it grows much faster than the team does linearly.4

Every one of those channels represents meetings, emails, Slack messages, "quick syncs," misunderstandings, and the time spent explaining to the new hire why the database schema looks like that. Brooks observed that in practice, the communication overhead doesn't just slow down the marginal productivity of each new person — past a certain point, it makes the total team less productive than a smaller team would have been.

The Optimist's Rebuttal

If Amdahl's Law were the whole story, the entire field of parallel computing would be a depressing exercise in futility. And yet — we do build systems with thousands of processors, and they do accomplish things that a single processor never could. What gives?

In 1988, John Gustafson looked at the same formula and had a different thought.6 Amdahl assumed you were trying to solve a fixed-size problem faster. But what if you weren't? What if, when you got more processors, you didn't try to do the same thing faster — you tried to do a bigger thing in the same amount of time?

This is Gustafson's Law, and it changes the mood entirely. If you double your processors and double the size of your problem, the serial portion stays roughly the same (it's usually something like "read the input" or "initialize the system"), but the parallel portion doubles. The serial fraction shrinks as a proportion of the whole.

MapReduce, the programming model that powered early Google, is a beautiful example.7 You take a massive dataset — every page on the internet, say — and you split it into chunks. Each chunk gets processed independently (the "Map" step, beautifully parallel). Then the results get combined (the "Reduce" step, more serial). As the dataset grows, the Map step dominates, and the serial Reduce step becomes a smaller and smaller fraction of the total work.

GPUs work the same way. A modern graphics card has thousands of simple cores, each doing the same calculation on a different pixel. Rendering a single pixel isn't much faster on a GPU than a CPU. But rendering eight million pixels in parallel — that's where the magic happens. The serial fraction (setting up the render pipeline, loading shaders) is tiny compared to the massively parallel pixel work.

The Universal Lesson

Amdahl's Law isn't really about computers. It's about the structure of work itself. And it shows up everywhere once you know to look for it.

Military operations. Napoleon could move armies faster by splitting them into corps that marched on parallel roads. But the battle itself required coordination — the serial fraction — and adding more corps beyond a certain point just created confusion. As the saying goes, no plan survives first contact with the enemy; the planning is serial, the execution tries to be parallel, and the friction in between is where wars are lost.

Startups. The best early-stage companies have teams of 3-7 people who move with astonishing speed. Then they raise money, hire to 30, and suddenly everything slows down. "Where did our velocity go?" asks the CEO, staring at a Jira board full of blocked tickets. It went into the N(N−1)/2 communication channels, is where. Jeff Bezos had it right with his two-pizza rule: if a team can't be fed by two pizzas, it's too big.8

Education. You can't learn calculus before algebra, or algebra before arithmetic. Knowledge has serial dependencies. A student who tries to parallelize their learning by taking all the prerequisite courses simultaneously ends up understanding none of them. The serial path through a curriculum is the bottleneck, and no amount of "study hacking" can route around it.

Cooking dinner (yes, again, because it's the perfect metaphor). An experienced home cook intuitively understands Amdahl's Law. They start the slow thing first — the roast, the stock, the bread dough — and parallelize around it. They don't try to speed up the oven. They design the entire meal so the serial bottleneck is occupied at all times, and the parallel work fills in around it. That's not just good cooking. That's optimal scheduling.

The universal lesson of Amdahl's Law is this: before you add resources, identify your bottleneck. If your constraint is serial — if it's the one thing that simply can't be divided — then adding more workers, more servers, more money, more cooks will not help. It might make things worse, because every new resource comes with coordination costs.

The right question is never "How do I get more?" It's "What's the part that can't be split up, and can I make that part smaller?"

Gene Amdahl showed us a formula. Fred Brooks showed us the human version. And the lesson is the same one that every experienced project manager, chef, general, and teacher eventually learns: you cannot escape the serial fraction. You can only understand it, measure it, and design around it.

Or, as I like to put it: before you hire your tenth engineer, make sure the nine you have aren't waiting on the same code review.