Parallel Algorithms & Design

Complete revision notes. Everything in this unit, organised by topic — definitions, diagrams, formulas, comparison tables and worked examples. Revise from this alone and you have the whole unit.

Part A — Designing Parallel Algorithms

A1. Design, don't retrofit

A parallel algorithm is not a serial algorithm with pragmas added. Sprinkling #pragma omp parallel for over existing code usually produces either an incorrect program or a slower one, because the structure of the computation determines how much parallelism is available. Unit III is about deciding that structure deliberately, and about measuring whether the decision worked.

A2. Foster's PCAM methodology

Ian Foster's four-stage design methodology is the standard framework for designing a parallel algorithm.

   P + C  ---- EXPOSE parallelism ----   ignore the hardware,
                                          aim for ~10x more tasks
                                          than processors

   A + M  ---- MAKE IT PRACTICAL ----     group and place that work
                                          so it runs fast on real
                                          hardware

The governing principle is expand, then contract. First find the maximum possible parallelism without regard to the machine; only then coarsen it to fit the machine you actually have. Designing in that order rarely goes wrong; designing in the reverse order — starting from "I have 8 cores" — hides parallelism you will never recover.

A3. Decomposition techniques

Real systems mix several of these. Data decomposition is by far the most common and the most scalable, because the amount of data typically grows without limit while the number of distinct functional stages in a program does not.

A4. Granularity

Worked example — how big should a task be? 1,000,000 items, each requiring 1 µs of real work (so 1 second serially). Creating and scheduling one task costs 10 µs. There are 8 cores. The only decision is how many items go into one task.

   speedup
   8x |            ____________
      |          /             \
      |         /               \      <-- you fall off BOTH edges
      |        /                  \
   1x |_______/                     \____
      +-------------------------------------
       1      100   1,000   125,000  1,000,000
                                      items per task

Note the last row of the table carefully: exactly one task per core gives the best arithmetic but leaves no slack, so any variation in task cost immediately becomes idle time. In practice you want somewhat more tasks than cores — the standard rule of thumb is roughly 10× as many tasks as processors.

A5. Task dependency graphs and the critical path

A task dependency graph is a directed acyclic graph in which nodes are tasks and an edge from A to B means B cannot start until A finishes. It is the precise statement of what may run in parallel.

SUM 8 NUMBERS AS A TREE

   a  b   c  d   e  f   g  h
    \/     \/     \/     \/         level 1: 4 adds, all parallel
    ab     cd     ef     gh
      \    /        \    /
       \  /          \  /           level 2: 2 adds, both parallel
      abcd          efgh
          \         /
           \       /                level 3: 1 add
            abcdefgh

   Work (total adds)          = 7      -> time on 1 core
   Critical path (levels)     = 3      -> time on infinite cores
   Maximum possible speedup   = 7 / 3  = 2.33x

The ceiling was found before running anything. This is the graph-shaped form of Amdahl's Law — the "nine musicians cannot play a four-minute song in thirty seconds" idea from Unit I, made precise. A crucial corollary: speeding up a task that is not on the critical path changes nothing at all.

A6. Work, span and Brent's bound

                          Work        T1
   Parallelism  =  ----------  =  --------
                          Span      T-inf

   Lower bound (you can never beat):   T_p  >=  max( T1/p , T_inf )
   Upper bound (you are guaranteed):   T_p  <=  T1/p  +  T_inf    <- Brent's bound

   "Parallelism" is also the maximum number of processors that
   can ever be useful. Beyond it, extra processors do nothing.

Worked example — two numbers predict everything. A pipeline has work T₁ = 46 and span T∞ = 28. Parallelism = 46/28 = 1.64.

From two processors onwards the span is in charge and nothing else matters — processors 3 through 1,000 change precisely nothing. Two numbers, computed on paper in five minutes, told you that before a line of code was written. This is the most useful single technique in the unit.

Part B — Measuring Parallel Performance

B1. Speedup

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

Linear (perfect) speedup is p× on p cores. Always compare against the best serial algorithm, not against a crippled parallel program run on one core — that inflates the number dishonestly. Superlinear speedup (S > p) occasionally occurs, usually because the data now fits in the combined caches of p processors; it is a cache effect, not a violation of the bound.

B2. Efficiency

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

Speedup asks "how much faster?"; efficiency asks "did I get what I paid for?" As cores are added, speedup rises while efficiency almost always falls. Falling efficiency is the early warning that overhead is beginning to dominate — and the signal to stop buying hardware.

B3. Amdahl's Law

Let f be the fraction of the program that is inherently sequential — reading input, acquiring a lock, combining results, coordination — and (1 − f) the fraction that parallelises perfectly.

DERIVATION — normalise T(1) = 1 and run on p cores

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

                    1                         1
   S(p)  =  -----------------  =  ------------------------
                  T(p)              f  +  (1 - f)/p

As p -> infinity the parallel term vanishes:

                    1
   S_max  =  --------            <-- the ceiling
                    f

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

B4. The ceiling, and how to measure f

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

Worked example — you cannot see f, so calculate it. Nobody hands you f. Run the program twice and solve for it. Measured: T(1) = 100 s and T(4) = 40 s. Should you buy a 64-core machine?

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

Step 2 — substitute into Amdahl and solve for f
                 1                            1
        S = ---------------    ->    2.5 = -------------
            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.

Two timings and one equation turned Amdahl from an exam formula into a purchasing decision. The 64-core machine is not worth buying; reducing f is.

B5. Gustafson's Law

Amdahl carries a hidden assumption: the problem size stays fixed. In practice, given a bigger machine we do not 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)          f = serial fraction

   Example, f = 0.20:
      p = 16  ->  S = 16 - 0.20 x 15  =  16 - 3  =  13x
      p = 64  ->  S = 64 - 0.20 x 63  =  64 - 12.6 = 51.4x

   Amdahl with the same f caps at 5x forever.
   Gustafson keeps climbing — near-linear, no ceiling — because
   the parallel work grew to match the machine.

Amdahl vs Gustafson — both are right

They do not contradict each other; they answer different questions. Most large-scale real-world computing — weather, AI, simulation — lives in Gustafson's world, which is precisely why supercomputers keep getting bigger and keep being worth building.

B6. Strong vs weak scaling

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

B7. Where the missing speedup goes

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

Worked example — account for every missing second. A 120-second job is parallelised across 8 cores. You hoped for 15 s; you measured 28.6 s, a speedup of 4.2×.

Note the second row: the serial 12 seconds is now the largest single item — larger than all the actual parallel work combined. On one core it was 10% of the runtime and invisible; on eight cores it is 42% and dominant. Parallelising the code makes the serial part relatively bigger, not smaller.

Part C — Load Balancing

C1. Balance the cost, not the count

Real tasks have uneven cost: compressing a 2 KB file versus a 2 GB file; testing whether 7 is prime versus a ten-digit number. Splitting by count leaves some workers swamped and others idle. A parallel job finishes only when its slowest worker finishes, so idle time is pure waste.

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

BAD split — 2 tasks each, in order:      GOOD split — balance the cost:
  W1: [1][1]  = 2s   ...idle 8s...         W1: [5][1]  = 6s
  W2: [1][1]  = 2s   ...idle 8s...         W2: [5][1]  = 6s
  W3: [5][5]  = 10s  <-- everyone          W3: [5][1]  = 6s
  W4: [5][5]  = 10s      waits for these   W4: [5][1]  = 6s
  Wall-clock: 10s                          Wall-clock: 6s  -> 40% faster

Same eight tasks, same four workers, no new hardware — a smarter split is 40% faster.

C2. Static vs dynamic load balancing

Worked example — count the idle time. Eight tasks, four cores. Costs: 10, 2, 3, 12, 1, 8, 2, 4 seconds — total 42 s. Perfect balance would give 42 ÷ 4 = 10.5 s.

STATIC — two tasks each, handed out up front
   0    4    8    12   16
   |----|----|----|----|
C0 [ T1: 10    ][T5]........
C1 [T2][ T6: 8    ]........
C2 [T3][T7]................    <-- idle 11 s!
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

Same tasks, same cores, same total work — a 33% difference in wall-clock from scheduling policy alone. Note also that even dynamic scheduling cannot reach 10.5 s, because task T4 alone takes 12 s: no schedule can finish faster than its single longest task, which is the critical path of A5 reappearing.

C3. Work stealing

Dynamic scheduling fixes imbalance but needs a shared task queue — and at 64 cores that queue becomes the bottleneck, exactly as the shared bus did in Unit II. Work stealing gives every worker its own queue. A worker takes from its own queue with no contention; when its queue empties it becomes a thief and takes a task from a randomly chosen busy worker.

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 end                                    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, empties, 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.

Why two ends, and why that choice matters:

• A thread takes its own work from the near end — the most recently pushed task, whose data is still hot in its cache.
• A thief takes from the far end — the oldest task, which in a divide-and-conquer computation is usually the largest, so one steal buys a lot of work and steals are rare.
• Because the two ends are different, the owner and the thief rarely contend, so no lock is needed in the common case.

This is how real schedulers work: Java's ForkJoinPool, Go's goroutine scheduler, Rust's Rayon, Intel TBB and Cilk all use work stealing. Know the term — it is the answer to "how do you get dynamic balance without a central bottleneck?"

C4. Embarrassingly parallel vs tightly coupled

This single classification predicts how hard a parallel problem will be before you write a line of code.

C5. Case studies

PARALLEL MATRIX MULTIPLY — why it is the poster child

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)

Workers only READ A and B and WRITE their own cells -> no race at all.
Uniform cost -> static balancing is optimal.

THREE PARALLEL SORTS worth naming:
  Odd-even transposition — compare disjoint neighbour pairs; all
                           compares within a phase run at once
  Parallel merge sort    — 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 a GPU

C6. Choosing a strategy

Applied: matrix multiply is uniform and independent → static, easy. Prime counting is uneven but independent → dynamic. Sorting is tightly coupled → divide and conquer, mind the merge. Search is independent with luck-dependent finish → dynamic plus a stop signal.

Quick recall

Speedup          S(p) = T(1) / T(p)
Efficiency       E(p) = S(p) / p
Amdahl           S(p) = 1 / ( f + (1-f)/p )
Amdahl ceiling   S_max = 1 / f                 (as p -> infinity)
Gustafson        S(p) = p - f(p - 1)
Work / Span      parallelism = T1 / T_inf
Lower bound      T_p >= max( T1/p , T_inf )
Brent's bound    T_p <= T1/p + T_inf

f = serial fraction.  T1 = work.  T_inf = span = critical path.

Self-check

Answer each out loud before opening it.