What "parallelizable" actually means

*worked out from first principles*

Last two chapters, we broke down why a CPU can't have 10,000 cores, and why a GPU crushes matrix math. This is the missing piece underneath both: when does throwing more cores at a problem actually help?

Because the honest answer is: usually, it doesn't.

Here's the belief almost everyone walks around with: "I have 10,000 cores, so any job gets 10,000 times faster." It's a comforting idea, and it's mostly wrong. More cores only help if the work can be cut into pieces that don't need each other. The second one piece needs another piece's answer first, all those extra cores go quiet.

↳ The enemy of parallelism has a name: dependency. If step B needs the output of step A before it can even start, there is nothing to parallelize. Step B simply has to wait. No chip, no budget, no number of cores fixes that. It's baked into the shape of the problem.

Three shapes of work

The right question is never "how many cores do I have?" It's: "Do the pieces of this work depend on each other?"

Let's look at the same hardware across three tasks that sit at completely different points on the dependency scale.

1. Matrix multiplication: perfectly parallel

Every cell of the output has its own formula and reads only the original inputs. The cell at row 1, column 1 does not care what the cell at row 5, column 2 is doing. There is no sharing of results, no order, and no waiting.

A GPU looks at this, sees that everything is independent, shatters the task into millions of pieces, and hands each to its own tiny core. They all run at once. The cores never have to talk to each other. Zero communication. This is the dream case: and it's exactly why AI, which is mostly matrix math, lives on GPUs.

2. Sorting: half parallel, then a wall

Take merge sort. The start is genuinely parallel. You have 10,000 numbers, you split them into four chunks, you hand each chunk to its own core, and all four sort their piece at the same time. Great, free speedup.

But then comes the merge. To fuse those four sorted chunks into one final sorted list, the cores have to compare elements across the chunks. This means they have to look at each other's data and coordinate. That final merge cannot be done by everyone at once. Cores slow down, they wait, they take turns. Sorting starts as a sprint and ends in a traffic jam: partly parallel, partly serial, and the serial tail caps how fast it can ever go.

3. Linked-list traversal: strictly serial, no escape

A linked list is a treasure hunt. Each block holds its own data plus the address of the next block, and nothing else. You do not know where item 2 lives until you have read item 1. You cannot reach item 5 without walking through 1, 2, 3, and 4 first. There is no shortcut, and no way to guess ahead.

Here, you can own 10,000 cores and exactly one of them will ever do work. The other 9,999 sit there swatting flies, because not one of them knows where to go next until the one working core tells them. Some problems are serial in their soul, and no hardware on earth can parallelize them.

↳ So the three shapes line up like this:

• Matrix math: fully independent, runs everywhere at once.
• Sorting: independent at first, then forced to coordinate.
• Linked list: every step chained to the one before it.

Same machine, three completely different ceilings. And the only thing that changed was how much the pieces depend on each other.

Cross-question: Is every algorithm parallelizable if you just try hard enough?

No. It's worth seeing why some problems are permanently serial:

1. Inherent serial nature: Take Fibonacci numbers (0, 1, 1, 2, 3, 5, 8). The rule is literally F(n) = F(n-1) + F(n-2). You cannot compute 8 until you already have 3 and 5. The definition itself forces an order. No clever scheduling escapes a problem that is defined in terms of its own previous answers.
2. Data dependency: If every step's input is the previous step's output, the steps form a chain by construction. Step 2 cannot begin until step 1 has handed it something. Parallelism here isn't just slow: it's impossible.
3. The baby rule: This is the most honest line in all of computer science: nine women cannot make a baby in one month. Some things take linear time because of physical or logical limits, and dividing the work among more workers does nothing. Adding people to a late project, or cores to a serial task, just adds coordination confusion.
4. Communication can cost more than the work: This is the trap. If you force a stubborn serial algorithm onto thousands of cores anyway, the cores spend more time shouting at each other (asking "did you finish? what's your answer? wait for me") than they would have spent just doing the math on one core. The coordination overhead grows faster than the speedup, and the whole thing gets slower than where you started. More cores actively made it worse.