Unit III — Parallel Algorithms & Design

Designing Parallel Algorithms

Session 07 • 2311CSC501J — Parallel Processing

What You'll Learn

Foster's PCAM design methodology
Data vs functional vs recursive decomposition
Granularity: fine vs coarse tasks
Task graphs & the critical path (the ceiling)

"Parallelism is a design decision, not a finishing touch. Decide where the work splits before you write a line."

— The whole session in one line

Design for It — Don't Retrofit

The classic mistake: write the whole program sequentially, then try to "sprinkle threads on top" at the end. It almost always produces a slow, buggy mess — cores fighting over data, work unevenly split, half the machine idle.

A good architect plans the plumbing and load-bearing walls first. In a parallel program, three things are load-bearing — decide them early:

Where work splits

Into what independent pieces?

What data moves

Which piece needs which other's result?

What depends on what

What's stuck in sequence, forever?

Those three decisions are exactly Foster's PCAM — a four-step method to design a parallel algorithm for any problem.

Foster's PCAM Methodology

Stage	Name	The question it answers
P	Partition	Break the problem into the smallest independent tasks
C	Communication	Which tasks need data from which other tasks?
A	Agglomeration	Group tasks to cut communication & overhead
M	Mapping	Which processor/core runs each group?

P + C — Expose parallelism

Think small, think independent. Ignore the hardware for now. Aim for 10× more tasks than processors.

A + M — Make it practical

Group and place that work so it runs fast on real hardware.

Expand, then contract. Design in that order and you rarely go wrong.

PCAM in Action: A Weather Grid

A 1000×1000 grid of temperatures. Each step, every cell updates from its 4 neighbors. At the end we want the average. How do we parallelize it?

Partition → one task per cell = a million tiny tasks (domain decomposition — same rule, different cells).

Communication → each cell needs its N/S/E/W neighbors (local, cheap). The final average sums all cells (global, costly).

Agglomeration → group cells into 100×100 tiles. Neighbor chatter becomes memory reads; only tile edges still talk.

Mapping → give each core an equal band of tiles; keep neighboring tiles on nearby cores (network locality — Session 04).

P & C expose the parallelism; A & M make it practical. Same four steps decompose a monolith into microservices.

Three Ways to Split a Problem

Data / Domain

Same operation, different data slices.

Sum an array • resize 1000 images. Most common; scales beautifully. GPUs live here.

Functional / Task

Different operations, often a pipeline.

Video: decode → filter → encode. Limited by how many distinct stages exist.

Recursive

Divide & conquer — same-shaped sub-problems.

Quicksort, merge sort, tree reduction. Naturally spawns independent sub-tasks.

Also worth naming: Exploratory (search a space; first to find a solution stops the rest) and Speculative (start work you might need; discard the waste). Real systems mix all of these.

Granularity: How Big Is a Task?

Fine-grained

Many small tasks.

+ Great load balance

– High overhead (scheduling & comms)

Too fine → you parallelize yourself slower.

Coarse-grained

Few big tasks.

+ Low overhead

– Load imbalance risk (idle cores)

Too coarse → 7 cores wait for the 8th.

Think computation-to-communication ratio: you want the useful work to dwarf the coordination tax. The art is landing in the middle — big enough that overhead is negligible, small enough that work spreads evenly.

Worked Example: How Big Should a Task Be?

1,000,000 items. Each takes 1 µs of real work — so 1 second serially. Creating and scheduling a task costs 10 µs. You have 8 cores. The only decision: how many items go in one task?

Items per task	Tasks	Total overhead	Wall-clock on 8 cores	Speedup
1 (too fine)	1,000,000	10 s	1.375 s	0.7× — slower than serial
100	10,000	0.10 s	0.138 s	7.3×
1,000 (the sweet spot)	1,000	0.01 s	0.126 s	7.9×
125,000	8 (one each)	0.00008 s	0.125 s	8.0× — but see below
1,000,000 (too coarse)	1	0.00001 s	1.0 s	1.0× — seven cores idle

speedup
   8x |            ____________
      |          /             \
      |         /               \        <-- fall off BOTH edges
      |        /                  \
   1x |_______/                     \____
      +-------------------------------------
       1      100   1,000   125,000   1,000,000     items per task
       ^                                     ^
    overhead eats it              no parallelism left

Row 1 is the classic beginner disaster: "I made it maximally parallel — one task per item!" — and the program is now slower than the serial version it replaced. The parallelism was real. The bookkeeping cost ten times more than the work.

Row 4 is the trap that looks like the answer. Exactly 8 tasks for 8 cores gets the best number on paper — and has zero slack. If one task happens to be twice as slow (a bigger image, a colder cache, a busy core), seven cores sit idle waiting for it and your 8× becomes 4×. There is no work left to rebalance with.

The rule of thumb professionals actually use: aim for roughly 10× as many tasks as cores, and make each task at least ~100× the scheduling overhead. That's enough tasks for the runtime to smooth out imbalance, and each is big enough that the bookkeeping disappears.

Granularity is the one PCAM decision you tune by measuring, not reasoning. The curve above is real — find its top for your own problem.

Dependencies & Task Graphs

Every task = a node. Arrow A→B means B needs A's result (B can't start until A finishes). No cycles allowed → a Directed Acyclic Graph (DAG).

Sum 8 numbers as a reduction tree

  a   b   c   d   e   f   g   h     <- 8 inputs (level 0)
   \ /     \ /     \ /     \ /
   ab      cd      ef      gh       <- 4 adds, all independent (run at once)
     \    /          \    /
     abcd            efgh           <- 2 adds, independent
        \            /
          abcdefgh                  <- 1 final add = the answer

Tasks with no arrow between them are independent — they can run in parallel. The four bottom adds have no dependency on each other, so 4 cores do them at once. The graph literally shows you your parallelism.

The Critical Path Is Your Ceiling

No matter how many processors you have, you can never finish faster than the critical path.

The critical path is the longest chain of dependent tasks from start to finish. In the 8-number tree:

7

adds in sequence (1 core)

3

levels = critical path (∞ cores)

2.3×

best possible speedup (7/3)

We found the ceiling before running anything. This is the graph-shaped preview of Amdahl's Law — the "nine musicians, thirty seconds" of Session 01, made precise. Speeding up a task off the critical path changes nothing.

Worked Example: Find the Critical Path

A CI pipeline. Eight stages, real dependencies, times in minutes.

                          B: compile mod1 (10)
                        /                      \
  A: fetch src (2) ---- C: compile mod2  (4) ---- E: link (3)
                        \                      /            |
                          D: compile mod3  (6)              |
                                                            |
                                          +-----------------+-----------------+
                                          |                                   |
                                    F: unit tests (8)          G: integration tests (12)
                                          |                                   |
                                          +-----------------+-----------------+
                                                            |
                                                     H: package (1)

Total work (T₁)

Add every box:
2+10+4+6+3+8+12+1

46 min

What one machine takes.

Critical path (T∞)

Longest chain:
A → B → E → G → H
2+10+3+12+1

28 min

What infinite machines take.

Maximum speedup = 46 / 28 = 1.64×. That's it. Not 8×, not 100×. This pipeline can never finish faster than 28 minutes no matter how many machines you rent, because those five stages must happen one after another.

Machines	Finish time	Why
1	46 min	Everything in sequence
2	30 min	Some compiles and tests overlap
3	28 min	All three compiles run at once — the ceiling is reached
100	28 min	97 machines idle. Zero benefit.

Now the lesson that saves careers. Suppose you spend a week optimising C: compile mod2 from 4 minutes down to 1. New pipeline time?

Still 28 minutes. Exactly zero improvement.

C is not on the critical path. Time spent optimising anything off the critical path is completely wasted — and it is the single most common way engineering effort is thrown away.

Do this instead: attack G, the 12-minute integration tests — the biggest box on the critical path. Halve it to 6 and the pipeline drops to 24 minutes (the path through F now binds). Then re-find the critical path, because it moves. That loop — find it, shorten it, find it again — is how real performance work is done.

Work, Span & Maximum Speedup

Work — T₁

Total number of tasks.

= time on one processor (do them all in sequence).

Span — T∞

Critical-path length.

= time on infinite processors.

                             Work        T1
   Maximum speedup  =  ----------  =  ------
                             Span        T-inf

Everything else in this course is about getting close to that ceiling on real hardware — finite cores, real communication cost, load imbalance. For the 8-sum: T₁ = 7, T∞ = 3, ceiling ≈ 2.3×.

Watch: Granularity & the Critical Path

Comrevo — 18:38 total. Show ~8:00 to ~15:00, the task-graph and critical-path part. The opening repeats slides 5–7.

Someone else drawing the same graph and tracing the same longest path. The video says degree of concurrency — that is just how many tasks can run at once at a given moment, and it is not examinable here. Work over span is the number that matters.

Worked Example: Two Numbers Predict Everything

Same pipeline. Work T₁ = 46. Span T∞ = 28. From those two numbers alone you can predict the runtime on any machine, before writing a line of code.

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

Parallelism  =  T1 / T_inf  =  46 / 28  =  1.64
             =  the most processors that can ever be useful

Processors	T₁/p	T∞	Which one binds?	Best speedup
1	46	28	work — not enough processors	1.0×
2	23	28	span — already!	1.64×
8	5.8	28	span	1.64×
1,000	0.05	28	span	1.64×

From two processors onwards, the span is in charge and nothing else matters. Buying processor number 3 through 1,000 changes precisely nothing. Two numbers, computed on paper in five minutes, told you that.

And here is the connection that ties this session to the next one. The span is just the sequential part of your program, drawn as a graph. So:

sequential fraction  f  =  T_inf / T1  =  28 / 46  =  0.61
max speedup             =  1 / f       =  1 / 0.61 =  1.64   <-- the same answer

That is Amdahl's Law, which we make formal in Session 08. Work-and-span and Amdahl are not two ideas — they're the same statement, one drawn as a graph and one written as a fraction.

What to actually do with this: before you parallelise anything, sketch the task graph and compute T₁/T∞. If the answer is 1.6, do not buy a cluster — go and restructure the algorithm to shorten the span. If it's 500, you have a genuinely parallel problem and you can go shopping for cores.

This Is How Real Systems Are Built

Design concept	The same idea at company scale
Partition	Break a monolith into microservices; shard a database
Communication	The API calls & message queues between those services
Agglomeration	Two services chat constantly → merge them; batch small jobs
Mapping	Which servers/pods run which workload, in which region
Critical path	The longest dependency chain in any project plan (Gantt chart)

Foster wrote PCAM for supercomputers in 1995. It describes a modern cloud architecture diagram just as well. Thread → core → GPU → server → data center is one continuous idea.

The Design Checklist

Face a new problem? Run this — PCAM plus the ceiling check — before you write code:

1. Partition — data, functional, or recursive? Aim for many small independent tasks.
2. Communication — draw the data flow. Local (good) or global (costly)? Regular or irregular?
3. Agglomeration — group tasks so computation dwarfs communication.
4. Mapping — assign groups to balance load and keep talkers close.
5. Check the ceiling — sketch the DAG. What's the critical path? Best possible speedup (T₁/T∞)? If it's too low, no hardware saves you — redesign.

Do this up front and you avoid the "sprinkle threads on at the end" disaster. Parallelism becomes four clear questions you already know how to answer.

Your Turn: Design It, Don't Code It

In pairs, 8 minutes. The job: 50,000 property photos. For each one — download it (2 s, network), detect rooms with a model (0.5 s, GPU), generate three thumbnails (0.1 s, CPU), write to storage (1 s, network). Then produce one summary report over all 50,000.

P — Partition: what is one task?

One photo. The photos are fully independent, so this is a data decomposition and it's embarrassingly parallel — right up until the report.

C — Communicate: who talks to whom?

Nobody, during the work. Only at the end, when all 50,000 results must be combined into one report. That single join is your entire span.

A — Agglomerate: what's the task size?

Not one photo per task — batch ~50 photos. Enough to amortise startup, and 1,000 batches for 8–32 workers gives plenty of slack to rebalance.

M — Map: what runs where?

Download and upload are I/O-bound → many concurrent connections, few cores. Detection is GPU. Thumbnails are CPU. Three different resources, three different worker counts.

Now the arithmetic that decides the design. Per photo: 3 s of waiting on the network, 0.6 s of computing. That's 83% I/O.

So the naive "one thread per photo, do all four steps" design leaves your GPU idle 83% of the time. The right shape is a pipeline: downloads streaming in continuously, feeding a GPU that never stops, feeding uploads going continuously out. Overlap the waiting with the computing — which is Session 01's definition of concurrency, arriving as a design decision.

Sanity-check with work and span: T₁ ≈ 50,000 × 3.6 s = 50 hours. T∞ ≈ one photo's chain (3.6 s) plus the final report. Parallelism is in the tens of thousands — so this problem genuinely scales, and the only real questions are cost and how fast your storage is.

Compare that with the CI pipeline, where the same analysis said "1.64×, don't bother." Same four questions, opposite conclusions, both reached before writing any code. That is what PCAM is for.

Recap & What's Next

Key Takeaways

Design for parallelism up front — don't retrofit threads at the end.
PCAM: Partition & Communication expose it; Agglomeration & Mapping make it practical.
Three decompositions: data (split data), functional (pipelines), recursive (divide & conquer).
Granularity is a trade-off: fine balances load but adds overhead; coarse risks imbalance.
The critical path is the hard floor on speed — the graph-shaped preview of Amdahl.

Homework

Take a program you've written; find one parallelizable section; name the decomposition & one blocking dependency.
Draw the dependency DAG for making a sandwich; mark the critical path.
Come ready: "80% parallelizable, 20% not — max speedup with a million cores?"

Next session: Measuring Parallel Performance

Amdahl's & Gustafson's Laws — today's "critical path is the ceiling," turned into hard numbers.