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.

Worked Example: Count the Idle Time

Eight tasks, four cores. The tasks take 10, 2, 3, 12, 1, 8, 2, 4 seconds — total 42 s. Perfectly balanced would be 42 ÷ 4 = 10.5 s.

Static — hand out two tasks each, up front

0    4    8    12   16
|----|----|----|----|
C0 [ T1: 10    ][T5]........
C1 [T2][ T6: 8    ]........
C2 [T3][T7]................    <-- idle 11s!
C3 [ T4: 12       ][ T8: 4 ]

finish = 16 s

Dynamic — grab the next task when free

0    4    8    12   16
|----|----|----|----|
C0 [ T1: 10    ]....
C1 [T2][T5][T7][T8 ]..
C2 [T3][ T6: 8    ]..
C3 [ T4: 12       ]

finish = 12 s

Strategy	Finish	Speedup	Core-seconds wasted	Efficiency
Static	16 s	2.6×	22 s idle (34%)	66%
Dynamic	12 s	3.5×	6 s idle (12%)	88%
Perfect balance (impossible)	10.5 s	4.0×	0	100%

Same tasks. Same cores. Same total work. 33% difference in wall-clock — from nothing but when you decide who does what. Static decides at the start and is stuck with its guess; dynamic decides at the last possible moment, when it actually knows who's free.

Now the deeper point — why even dynamic can't reach 10.5. Task 4 alone takes 12 seconds. Nothing finishes before it does. So:

best possible = max( total_work / cores , longest_single_task )
              = max(     42 / 4        ,        12            )  =  12 s

That's Session 07's span, wearing a scheduler's uniform. Dynamic scheduling didn't get lucky — it hit the theoretical optimum. To go faster you cannot schedule better; you must split task 4 into smaller pieces.

The rule that follows: schedule the longest tasks first. Had static handed out T4 and T1 before the small ones, it would have finished in 12 too. That is the "longest processing time first" heuristic, and it is provably within 33% of optimal — not bad for one sort.

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.

Worked Example: Watch a Thread Steal

Dynamic scheduling fixes imbalance but needs a shared task queue — and at 64 cores that queue becomes the bottleneck (Session 04's bus, again). Work stealing gives every thread its own queue.

Each thread owns a DEQUE. It works from one end; thieves take the other.

  t=0   T0: [A B C D]      T1: [E F]      T2: [ ]      T3: [G]
              ^own                                         all busy

  t=1   T2 is EMPTY. It picks a victim at random -> T0.
        T2 steals from the FAR end of T0's deque:

        T0: [A B C]        T1: [E F]      T2: [D]      T3: [G]
                            no lock needed on T0's own end!

  t=2   T3 finishes G, empty, steals from T0 (far end again):

        T0: [A B]          T1: [E F]      T2: [D]      T3: [C]

  t=3   Every thread busy again. T0 was never interrupted.

Two ends, and the choice of which is which is the whole design:

A thread takes its own work from the near end — the most recently pushed task. That's the task whose data is still hot in its cache.
A thief takes from the far end — the oldest task, which is usually the biggest (it hasn't been broken down yet), and whose cache lines nobody wants anyway.
Because the two ends are different, no lock is needed in the common case. The owner and the thief don't touch the same memory.

	Static	Dynamic (shared queue)	Work stealing
Handles imbalance	No	Yes	Yes
Contention at 64 cores	None	Severe — one queue	Almost none
Cache locality	Excellent	Poor	Good — by design
Cost when perfectly balanced	Zero	Per-chunk overhead	Near zero — nobody steals

Why this matters beyond the exam: work stealing is what actually runs under #pragma omp task, Java's ForkJoinPool and parallel streams, Go's goroutine scheduler, Rust's Rayon, and Intel TBB. When you write list.parallelStream() in Java, this deque dance is what happens.

It won because it degrades gracefully: costs nothing when the load is balanced, fixes it when it isn't. You don't have to know which case you're in — and you usually don't.

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.

Quick Check: Pick the OpenMP Schedule

Everything in this session is one clause away in your lab code:

#pragma omp parallel for schedule(static)          equal chunks, decided up front
#pragma omp parallel for schedule(dynamic, 1)      grab one iteration when free
#pragma omp parallel for schedule(guided)          big chunks first, then smaller
#pragma omp parallel for schedule(runtime)         decided by OMP_SCHEDULE at run time

Which one, and why? Shout it out.

1. c[i] = a[i] * b[i], 10 million elements

static. Every iteration costs the same, so there is nothing to balance. Zero scheduling overhead and contiguous chunks give each core clean cache behaviour.

2. Test every number 2…1,000,000 for primality by trial division

dynamic (or guided). Checking 999,983 costs ~700× more than checking 3. Under static the thread holding the top quarter runs long after the others have finished — your Lab 4 result, explained.

3. Render the Mandelbrot set

dynamic, small chunk. A pixel outside the set escapes in 2 iterations; one inside runs the full 1,000. The expensive pixels are all clustered in the middle of the image — the worst possible case for static.

4. Process 1,000 files ranging from 1 KB to 2 GB

dynamic, chunk 1 — and sort largest-first if you can. With a 2,000,000× spread in task size, one unlucky assignment decides your entire runtime.

5. The trap: 100 million iterations, each identical and taking about 3 nanoseconds. Someone suggests schedule(dynamic, 1) "to be safe."

Disaster. Each dynamic hand-out costs perhaps 50 ns of atomic bookkeeping to schedule 3 ns of work — roughly 17× overhead, and every core hammering the same shared counter. static here is not just adequate, it is dramatically better. Dynamic scheduling is insurance, and insurance has a premium. Only buy it against a risk you actually have.

The one question to ask: do different iterations take noticeably different amounts of time? No → static. Yes → dynamic or guided. Don't know → use schedule(runtime) and try all three from the shell with OMP_SCHEDULE — no recompiling required.

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.