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 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.

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.

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.