Unit III — Parallel Algorithms & Design

Load Balancing & Case Studies

Session 09 • 2311CSC501J — Parallel Processing

What You'll Learn

Static vs dynamic load balancing
Work stealing & chunk size
Embarrassingly parallel vs tightly coupled
Case studies: search, matmul, sort, primes

"A parallel program is only as fast as its slowest worker."

— The whole session, in one line

Balance the Cost, Not the Count

Real tasks have uneven cost: compress a 2 KB vs a 2 GB file; test if 7 is prime vs a 10-digit number. Splitting by count leaves some workers swamped and others idle.

4 workers, 8 uneven tasks. Numbers = cost (seconds).
Tasks:  [1] [1] [1] [1] [5] [5] [5] [5]

BAD split (2 tasks each, in order):
  W1: [1][1]  = 2s   ...idle 8s...
  W2: [1][1]  = 2s   ...idle 8s...
  W3: [5][5]  = 10s  <-- everyone waits
  W4: [5][5]  = 10s  <-- for these
  Wall-clock: 10s

GOOD split (balance the cost):
  W1: [5][1]  = 6s
  W2: [5][1]  = 6s
  W3: [5][1]  = 6s
  W4: [5][1]  = 6s
  Wall-clock: 6s   <-- 40% faster, same work

Same 8 tasks, same 4 workers, no new hardware — a smarter split is 40% faster. The idle time is pure waste. That's why this session exists.

Demo: Static vs Dynamic

Open examples/01-load-balancing.html. Eight uneven tasks, four workers, two strategies side by side.

Static

Pre-assign two tasks each, in order. One worker draws the big tasks — everyone else finishes early and sits idle.

Dynamic

Tasks sit in a shared queue; each worker grabs the next one the moment it's free. Nobody's idle. The queue self-corrects.

The point: dynamic wins by itself — nobody had to predict which tasks were expensive. The queue figured it out.

Two Strategies

	Static	Dynamic
Decided	Up front, once	On demand, as workers free up
Overhead	None	Queue access per task
Best for	Uniform, predictable tasks	Irregular, unpredictable tasks
Fails when	Estimates are wrong (locked in)	Tasks too small (overhead)

Static — decide up front

Divide all work before running, hand each worker its share. Zero coordination. Great when you can predict task cost.

Dynamic — decide as you go

All tasks in a shared queue; workers grab the next when free. Self-balancing. Price: coordination on every grab.

Work Stealing — the Best of Both

Give each worker its own queue (cheap — no shared contention). When a worker empties its own, it becomes a thief and grabs a task from a busy worker's queue.

W1: [t][t][t][t]   <- busy, working its own queue
W2: [t][t]
W3: (empty)  --steal-->  takes a task off W1's back
W4: (empty)  --steal-->  takes a task off W1's back

Low contention (usually your own queue)
  + self-correcting (idle workers steal)

This is how real schedulers work: Java ForkJoinPool, Go's goroutine scheduler, Rust Rayon, Intel TBB, Cilk. Remember the term — it's in every systems interview.

CTO framing: a dynamic work queue with workers pulling the next job is exactly an autoscaling job queue. Work stealing is how a good scheduler keeps no worker bored while another drowns — same idea across cores or across a server fleet.

Granularity: How Big Is a Task?

Fine-grained

Many tiny tasks. Great balance, but lots of queue overhead — you touch the queue constantly.

Coarse-grained

Few big tasks. Tiny overhead, but poor balance — one huge chunk and you're stuck again.

The answer is a chunk size in the middle. In OpenMP (Session 10) you'll set it directly:

schedule(static)          split iterations evenly, up front.   (uniform work)
schedule(dynamic, chunk)  grab `chunk` iterations at a time.    (irregular work)
schedule(guided)          big chunks early (cheap), shrinking
                          chunks near the end (fine balance).

guided is the clever compromise: big scoops while trays are full, smaller scoops as work runs low — so the finish line stays even.

Embarrassingly Parallel vs Tightly Coupled

Embarrassingly Parallel

Independent tasks, little/no communication. Split, run, collect.

Movie frames, prime testing, Monte Carlo, matrix multiply (each cell independent). Scale near-linearly, trivial to balance.

The jobs you love — they just shard.

Tightly Coupled

Tasks communicate constantly — each step needs the neighbors.

Physics on a grid, most sorting. Communication becomes the bottleneck; balancing must account for the chatter.

Where you earn your salary.

This one classification predicts how hard a parallel problem will be — before you write a line.

Case Study: Parallel Search

Serial: scan a big array/space for a target, element by element.
Parallel: split across workers; each searches its slice at once. First to find flips a shared found flag — everyone stops. This is speculation.

Tricky: the stop signal (check the flag or you keep searching after the answer's found) and luck — if the target's at the start of W1's slice, W1 wins instantly while others search their whole slice.

Speedup: a failed search (target absent) scans everything → near-linear, embarrassingly parallel. A successful one depends on where the target sits — on average still a big win.

Case Study: Parallel Matrix Multiply

The poster child of parallel computing — Lab 1 (OpenMP) and Lab 3 (CUDA). Each output cell is a dot product:

C[i][j] = A[i][0]*B[0][j] + A[i][1]*B[1][j] + ... + A[i][n-1]*B[n-1][j]

for i in 0..n:
    for j in 0..n:                 <-- every C[i][j] is INDEPENDENT
        C[i][j] = dot(row i of A, col j of B)

Every output cell is independent → embarrassingly parallel. Give each worker a band of rows. Workers only read A and B and write their own cells — no race. Uniform cost → static balancing is perfect.

Tricky: not correctness — memory. Reading B column-by-column is cache-unfriendly (Session 05). Real code uses blocking/tiling. Run examples/02-parallel-matmul.html to watch the result fill in parallel.

Case Study: Parallel Sorting

Sorting is tightly coupled — every element may move relative to every other — so it's harder than matmul. Three approaches:

Odd-even transposition

Compare disjoint neighbor pairs per phase — all compares in a phase run at once.

Parallel merge sort

Divide & conquer: sort halves in parallel, then merge. The merge is the serial-ish part.

Bitonic sort

A regular sorting network; more compares, but maps perfectly onto GPUs. Know the name.

Lab 2 (MPI): master scatters chunks → each process sorts locally → gather → final merge. Speedup is good but sub-linear — the merge is your Amdahl serial fraction.

Case Study: Parallel Prime Generation

Find all primes up to N. Split the range across workers — each tests its own numbers. Independent → embarrassingly parallel. So far, easy. But…

The twist: the work is not uniform. Big numbers cost more to test. Give W1 the range [2, N/4] and W4 the range [3N/4, N], and W4 gets all the expensive numbers while W1 sits idle. Classic load imbalance!

The fix — this whole session: use dynamic scheduling (small chunks from a queue) or interleave (worker w takes w, w+P, w+2P…). Either way each worker gets a mix — balance the cost, not the count. This is Lab 4.

The cleanest proof of why load balancing matters: naive static = terrible, dynamic = great.

Choosing a Strategy

Ask…	If YES	If NO
All tasks cost the same?	Static	Dynamic
Tasks independent?	Embarrassingly parallel	Tightly coupled — mind comms
Tasks tiny?	Coarse chunks	Fine chunks are fine
Cost unpredictable?	Dynamic + work stealing	Static is simplest

Matrix multiply → uniform + independent → static, easy.

Primes → uneven + independent → dynamic, balance it.

Sorting → tightly coupled → divide & conquer, mind the merge.

Search → independent, luck-dependent finish → stop signal.

Unit III Wrap-Up & What's Next

Session	The one thing to remember
07 Design	Foster's PCAM: Partition → Communicate → Agglomerate → Map. The critical path sets the floor.
08 Measure	Speedup S=T(1)/T(p); Efficiency=S/p; Amdahl caps you at 1/f; Gustafson scales the problem.
09 Balance	Static vs dynamic vs work stealing; embarrassingly parallel vs tightly coupled; 4 case studies.

The through-line: design the decomposition (S07), measure whether it paid off (S08), and balance the load so it actually does (S09). You can now reason about any parallel algorithm — before writing a line of it.

Next session: OpenMP in Depth (Lab 1: Matrix Multiplication)

We start writing real shared-memory code — and you'll set schedule(static/dynamic/guided) with your own hands.