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.

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 women, one month" of Session 01, made precise. Speeding up a task off the critical path changes nothing.

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

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.

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.