Unit III — Parallel Algorithms & Design

Measuring Parallel Performance

Session 08 • 2311CSC501J — Parallel Processing

What You'll Learn

Speedup and efficiency — from raw timings
Amdahl's Law and the hard ceiling 1/f
Gustafson's Law and scaled speedup
Strong vs weak scaling & where speedup leaks

"5% serial ⇒ 20× maximum speedup — no matter how many cores you throw at it."

— Amdahl's Law, in one line

Speedup — The Headline Number

How many times faster is the parallel version than the best serial one?

              T(1)      time on 1 processor
   S(p)  =  --------  = ----------------------
              T(p)      time on p processors

T(1)	p	T(p)	Speedup	Verdict
100 s	4	25 s	4.0×	Perfect / linear
100 s	4	40 s	2.5×	Real life — overhead ate the rest
60 s	8	12 s	5.0×	Good, not perfect

Linear (perfect) speedup = p× on p cores — the dream, rarely achieved. Compare against the best serial baseline, not a crippled parallel program on one core.

Efficiency — Are Your Cores Pulling Their Weight?

5× on 8 cores sounds fine — but you paid for 8 and got 5. Efficiency catches the waste.

              S(p)        speedup
   E(p)  =  --------  = ----------------
                p       number of cores

Speedup	p	Efficiency	Reading
3.2×	4	80%	Solid — 20% lost to overhead
2.5×	4	63%	The missing 37% went to coordination
7.6×	8	95%	Excellent scaling

Add cores and speedup goes up while efficiency usually goes down. Falling efficiency is the early-warning light that overhead is starting to dominate — and the signal to stop buying hardware.

Amdahl's Law — Splitting the Work

f — the serial part

Inherently sequential: reading input, a lock, combining results, coordination. Adding cores does nothing for it.

(1 − f) — the parallel part

This part can be split across p cores — so it takes (1 − f)/p.

Normalize T(1) = 1 and run on p cores

   T(p)  =  f  +  (1 - f)/p        serial stays f; parallel shrinks

                     1
   S(p)  =  ---------------------    <- Amdahl's Law
              f  +  (1 - f)/p

The serial part refuses to shrink no matter how many cores you add. That single fact is the whole law.

Amdahl's Law — A Worked Example

A program is 80% parallel, so f = 0.20. What speedup on 4 cores? On infinite cores?

   S(4)  =  1 / (0.20 + 0.80/4)
         =  1 / (0.20 + 0.20)
         =  1 / 0.40
         =  2.5x

   S(inf) =  1 / 0.20  =  5x     (the ceiling)

4 cores already reach 2.5× of a 5× maximum.

Going 4 cores → ∞ only buys the gap from 2.5× to 5×.

Diminishing returns are built into the math.

The Ceiling: S_max = 1/f

Push p → ∞, the parallel term vanishes, and the serial fraction alone caps your speedup.

Serial fraction f	Parallel part	S_max = 1/f	Meaning
50%	50%	2×	Half-serial code caps at 2× — forever
25%	75%	4×
10%	90%	10×	The Session 01 teaser, proven
5%	95%	20×	95% parallel, yet capped at 20×
1%	99%	100×

Read the 5% row. A program that is 95% parallel — which sounds excellent — can never beat 20×, whether you give it 64 cores or a million. The last 5% is a brick wall.

Watch: Why Parallel Computing Has Limits

Linux Magazine — 5:44, play it in full. The clearest short explanation of the ceiling there is.

Same law, someone else’s words, straight after the table. If 1/f still felt like algebra a minute ago, this is where it turns into something you believe.

Worked Example: You Can't See f — So Calculate It

Nobody hands you f. But you can run the program twice and solve for it — and that turns Amdahl from an exam formula into a tool you can use on Monday.

You measure: T(1) = 100 s and T(4) = 40 s. Your manager asks whether to buy a 64-core machine.

Step 1 — the speedup you actually got
        S(4) = 100 / 40 = 2.5        (not 4 — so something is serial)

Step 2 — put it into Amdahl and solve for f
             1
        S = ---------------          ->    2.5 =        1
            f + (1-f)/p                            f + (1-f)/4

        1/2.5 = 0.4 = 0.75f + 0.25    ->   0.75f = 0.15   ->   f = 0.20

Step 3 — the ceiling, before spending a rupee
        S_max = 1/f = 1/0.20 = 5x, no matter what you buy.

Cores	Predicted speedup	Runtime	Saved vs previous row
1	1.00×	100 s	—
4 (measured)	2.50×	40 s	60 s
16	4.00×	25 s	15 s
64	4.71×	21.2 s	3.8 s — for 4× the machine
∞	5.00×	20 s	1.2 s more, ever

Answer to your manager: don't buy the machine. 64 cores buys 3.8 seconds over 16. And every core in the universe buys 5 seconds over 16. You just made a purchasing decision from two stopwatch readings.

Do this instead. Go find those 20 seconds of serial work and halve them. Now f = 0.10, so S_max = 10× and the job runs in 10 seconds on hardware you already own — twice as fast as infinite cores could ever make the old version.

That is the whole strategic content of Amdahl's Law: shrinking f beats buying p. Always. And it's usually cheaper.

This has a name — the Karp–Flatt metric: e = (1/S − 1/p) / (1 − 1/p). Same arithmetic, one line. Check it: (0.4 − 0.25)/(1 − 0.25) = 0.15/0.75 = 0.20.

Its real power: compute e at p = 2, 4, 8, 16. If it stays flat, you have a genuine serial fraction. If it climbs as p grows, your problem isn't serial code — it's overhead (communication, synchronisation, imbalance) getting worse with scale. Two very different diagnoses, two very different fixes.

Watch the Curve Hit the Wall

Speedup vs cores (Amdahl, f = 0.10, ceiling = 10x)

 10x |                    . . . . . . . . . . .  ← S_max = 1/f wall
     |            . '
     |challenge  '
  6x |        .
     |      .
     |    .
  2x |  .
   1x|.
     +------------------------------------------
     1    4    8   16   32   64  128  256   cores
        the curve bends toward the ceiling and never crosses it

Open examples/01-amdahl-calculator.html and drag the sliders live. Push the cores toward infinity and watch the speedup curve flatten into its ceiling. Adding cores on the flat part is money on fire.

This single picture — the curve bending toward a wall it can't cross — is Amdahl's Law.

Gustafson's Law — The Optimist

Amdahl's hidden assumption: the problem stays fixed. But with a bigger machine we don't run the same job faster — we run a bigger job. Weather models use a finer grid; AI trains on more data.

   S(p)  =  p  -  f * (p - 1)       <- Gustafson (scaled speedup)

   Example: f = 0.20, p = 16
   S(16) =  16 - 0.20 * (16 - 1)
         =  16 - 0.20 * 15
         =  16 - 3  =  13x

Amdahl with the same f = 0.20 caps at 5× forever. Gustafson gives 13× on 16 cores and keeps climbing — near-linear, no ceiling, because the parallel work grew to match the machine.

Both Laws Are Right

They don't contradict — they answer different questions.

Amdahl asks…

"I have this problem. How much faster can I make it?"

Fixed problem → hard ceiling 1/f.

Gustafson asks…

"I have a bigger machine. How much bigger a problem can I solve in the same time?"

Growing problem → near-linear speedup.

Most big real-world computing — weather, AI, simulation — lives in Gustafson's world. That's exactly why supercomputers keep getting bigger and keep being worth it.

Strong vs Weak Scaling

	Strong scaling	Weak scaling
Problem size	Fixed	Grows with p
Question	Same job, more cores → faster?	Bigger job + more cores → same time?
Governed by	Amdahl's Law	Gustafson's Law
Ideal result	Time drops as 1/p	Time stays constant as p grows
Real example	Speed up one fixed image render	10× data on 10× GPUs, same wall-clock

Rule of thumb: "problem stays the same size" → strong scaling → Amdahl. "problem grows with the machine" → weak scaling → Gustafson.

Where the Missing Speedup Goes

Amdahl's f is the theoretical floor. Real machines do worse, because the clean formula ignores overhead:

Communication

Cores/nodes swap data. Grows with worker count — often the #1 killer at scale.

Synchronization

Locks and barriers. Every barrier makes the fastest core wait for the slowest.

Load imbalance

One core gets more work; the rest idle. The job runs at the speed of the slowest worker. (→ Session 09)

Parallel overhead

Spawning threads/processes, scheduling, splitting and merging data.

The job: find what can go parallel, shrink f, and keep overhead from eating the gains.

Worked Example: Where Did the Other 3.8× Go?

You parallelise a 120-second job across 8 cores. You hoped for 15 s. You measured 28.6 s — a speedup of 4.2×, not 8×. Let's account for every missing second.

Where the time went	Seconds	Why it exists	Fix
Useful parallel work	13.5	108 s of work ÷ 8 cores	— this is the point
Serial section (f = 10%)	12.0	Reading input, writing the final file	Overlap I/O, or parallelise the read
Communication	1.8	Cores exchanging partial results	Bigger tasks, fewer exchanges
Load imbalance	0.9	One core got a heavier chunk; 7 waited	Dynamic scheduling → Session 09
Thread + sync overhead	0.4	Fork, join, barriers	Fewer parallel regions
Total	28.6	Speedup 120 / 28.6 = 4.2×

Read the second row. The serial 12 seconds is now the largest single item — bigger than all the actual parallel work put together. On one core it was 10% of the runtime and invisible. On eight cores it is 42% of the runtime and it owns your program.

That's the cruel arithmetic of Amdahl: parallelising the parallel part makes the serial part more important, not less. The better you optimise, the more the leftovers dominate.

So where do you spend your next week? Not on communication (1.8 s), not on the scheduler (0.4 s). On the 12 seconds of serial I/O. Halve it and you go from 4.2× to 5.4× — more than doubling all the other optimisations combined.

This is Session 07's critical-path lesson in another costume: find the biggest number, fix that, re-measure. Engineering intuition about which line "looks slow" is almost always wrong. Build this table instead.

Notice something about rows 3 and 4: communication and imbalance grow with core count, while the serial part stays fixed. Run this on 64 cores and communication — not f — may well become the top line. That is exactly what a rising Karp–Flatt e would have told you.

Amdahl Is a Capacity-Planning Law

"Added servers, barely faster?" You hit a serial bottleneck — a single database, one lock, one queue everything funnels through. That bottleneck is the f.
Doubling the web tier does nothing if every request still waits on one primary DB.
Capacity planning = estimating f, then deciding: buy more machines (helps only if f is small) or reduce f (shard the DB, remove the lock, split the queue).

"We added machines and it barely got faster" is not a mystery. It's Amdahl presenting the bill.

The high-leverage fix is almost always shrinking the serial part, not throwing hardware at a serial bottleneck.

Quick Check: Which Law Is Talking?

One question decides it every time: is the problem size fixed, or does it grow with the machine?

1. "Our nightly ETL takes 6 hours. Make it faster."

Amdahl / strong scaling. Same data, want less time. There is a ceiling and you should find it before buying anything.

2. "We got 10× the GPUs, so we'll train a 10× bigger model in the same 3 months."

Gustafson / weak scaling. The deadline is fixed and the problem grows. This is why AI labs keep buying hardware and keep getting value.

3. "Render this one 4K frame faster."

Amdahl. One fixed frame. But render a thousand frames and each becomes an independent job — the same work, re-framed, becomes embarrassingly parallel. How you frame the problem chooses your law.

4. Weather: "same 6 a.m. forecast deadline, but on a finer grid."

Gustafson. Nobody wants yesterday's forecast sooner — they want a better forecast by the same deadline. This is why supercomputers keep being worth their price.

5. The one people argue about: "We tripled the servers. Page load is still 800 ms — but we now handle 3× the traffic. Did it work?"

It worked perfectly — at something nobody asked for. Adding servers is a throughput (Gustafson-shaped) intervention; "page load is slow" is a latency (Amdahl-shaped) complaint. Session 01's toll booth, three months and a large invoice later. Before you scale anything, be sure which number you are trying to move.

The sentence worth memorising: Amdahl tells you how much faster you can finish; Gustafson tells you how much more you can attempt. Both are true. Choosing which one you're being asked about — that's the actual skill.

Recap & What's Next

Key Takeaways

Speedup S = T(1)/T(p); efficiency E = S/p. Perfect = p× and 100%.
Amdahl: S = 1/(f + (1−f)/p), ceiling S_max = 1/f. 5% serial ⇒ 20×, forever.
Gustafson: S = p − f(p−1). Grow the problem with the machine → near-linear.
Amdahl = strong scaling (fixed problem); Gustafson = weak scaling (growing problem).
Real speedup also leaks to communication, sync, and load imbalance.

Homework

Estimate the serial fraction f of a system you use and state its Amdahl ceiling.
Reproduce the f-vs-S_max table from memory (1/f in your head).
Come ready: "if one worker gets stuck with 90% of the work, what did the perfect-speedup calculation forget?"

Next session: Load Balancing & Case Studies

What your clean speedup formula forgets — and real parallel algorithms.