Applications of Parallel Computing

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 — Scientific Computing & Parallel Databases

A1. Domain decomposition

Scientific simulation — weather, fluid dynamics, structural analysis — divides physical space into a grid of cells and repeatedly updates each cell from its neighbours' values. Domain decomposition splits that grid across processors: each owns a block of space and simulates only its own cells. This is PCAM's Partition step (Unit III) made physical.

The atmosphere over a region, split across 4 processors

   +---------+---------+
   |   P0    |   P1    |     Each processor owns a rectangular
   |  (NW)   |  (NE)   |     block of cells and simulates only
   +---------+---------+     those.
   |   P2    |   P3    |
   |  (SW)   |  (SE)   |
   +---------+---------+

The difficulty: to update a cell you need its neighbours' values, but cells on the edge of P0's block have neighbours living on P1, P2 and P3. So the processors must communicate every time step.

A2. Halo cells and the halo tax

P0's block, with a halo border received from neighbours

   . . . . . . .     ".":  halo cells — copies of neighbours' edges,
   . # # # # # .           refreshed every step
   . # # # # # .     "#":  P0's own cells, which P0 updates
   . # # # # # .
   . # # # # # .
   . . . . . . .

   Computation  — local to each block, scales beautifully
   Halo exchange — communication, the enemy

Worked example — the halo tax. A 1000×1000 grid on 100 processors. Every processor computes the same 10,000 cells either way; only the shape of its piece differs.

      1-D STRIPS                          2-D BLOCKS
  each proc: 10 x 1000                each proc: 100 x 100
  +--------------------------+        +------+------+------+
  |========= proc 0 =========|        | p0   | p1   | p2   |
  |========= proc 1 =========|        +------+------+------+
  |========= proc 2 =========|        | p3   | p4   | p5   |
  |           ...            |        +------+------+------+
  halo = 2 edges x 1000 cells         halo = 4 edges x 100 cells
       = 2,000 cells exchanged             = 400 cells exchanged

The principle is fat blocks, thin seams: a compact block maximises interior work per unit of border. Because computation scales with area and communication with perimeter, the surface-to-volume ratio improves as blocks get larger — which is exactly PCAM's Agglomeration step, and the reason communication overhead worsens as you spread a fixed problem over more processors.

A3. Monte Carlo methods

Some science needs no neighbours at all. Monte Carlo methods answer questions by averaging a large number of independent random samples — making them the archetype of an embarrassingly parallel workload (Unit III).

ESTIMATING pi BY THROWING DARTS

   +-------------------+     Square area  = (2r)^2 = 4r^2
   |    . . * . . *    |     Circle area  = pi * r^2
   |   . ( * * * ) .   |
   |  .  (* * * *) .*  |     inside / total  ->  pi*r^2 / 4r^2  =  pi/4
   |   . ( * * * ) .   |
   |    . * . . * .    |     so    pi  ~=  4 x inside / total
   +-------------------+

Every dart is independent. Split 10M darts across 8 cores, each throws
1.25M, then sum the inside-counts — ONE reduction at the end.
Near-perfect linear speedup.

One practical caution: each thread or rank must use an independent random-number stream. Sharing one generator either serialises the computation or produces correlated samples that silently corrupt the result.

A4. Parallel database architectures

A table with two billion rows will not scan — or even fit — on one machine. You can scale up (a bigger box, which has a ceiling) or scale out (more boxes, no ceiling). Parallel databases scale out.

Shared-nothing is the architecture behind every large modern database. Nodes communicate only over the network, so there is no shared resource to contend on — it is precisely the distributed-memory model of Unit I, which makes MPI and parallel databases close cousins.

A5. Sharding and the shard key

users table sharded by hash(user_id) % 3

   Shard 0          Shard 1          Shard 2
   +----------+     +----------+     +----------+
   | u3  u6   |     | u1  u4   |     | u2  u5   |
   | u9  u12  |     | u7  u10  |     | u8  u11  |
   +----------+     +----------+     +----------+
   Node A           Node B           Node C

A6. Parallel query execution

SELECT COUNT(*) FROM events WHERE country = 'IN'

                    Coordinator
                   /     |      \       (1) fan-out to all shards
              Shard0   Shard1   Shard2
               scan     scan     scan   (2) each scans its own slice
               =12M     =15M     =11M       in parallel
                   \     |      /
                    Coordinator           (3) merge the partials
                        = 38M                 12M + 15M + 11M = 38M

This is fan-out / fan-in — the same scatter/gather shape as MPI collectives (Unit IV) and MapReduce (Part B). Aggregates such as COUNT, SUM, MIN and MAX are reductions, and combine trivially.

A7. Parallel joins — the hard one

A row on shard 0 may need to match a row on shard 2. Three strategies, best to worst:

This is why the shard-key choice matters so much: sharding both tables on the join key turns a shuffle join into a co-located join and can take a report from minutes to seconds without changing a line of query text.

A8. OLTP vs OLAP

A large scan is the perfect parallel workload: split a trillion rows over a thousand machines, scan in parallel, merge. That is Gustafson's Law (Unit III) in production — more data in the same time.

Same idea, different clothes: partition → compute → communicate as little as possible → combine.

Part B — Big Data & Parallel Processing

B1. Move the code, not the data

Suppose 1,000 GB of logs sit on 100 machines, 10 GB each, and you want to count something across all of it.

Data locality — run the computation where the data already lives. A program is kilobytes; the data is terabytes. Always move the small thing. This is simply data parallelism (Unit I) where the "cores" are now whole machines.

B2. HDFS — split and replicate

The Hadoop Distributed File System chops a huge file into blocks (typically 128 MB) and keeps three copies of each block on different machines.

A 512 MB file in HDFS   (4 blocks, replication factor 3)

           Block 1     Block 2     Block 3     Block 4
 Node A      [B1]                    [B3]
 Node B      [B1]        [B2]                    [B4]
 Node C                  [B2]        [B3]
 Node D      [B1]        [B2]                    [B4]
 Node E                              [B3]        [B4]

 Every block lives on 3 machines. A disk dies -> the data survives.

Replication serves two purposes: fault tolerance and locality — with three copies, the scheduler has three chances to place a task on a machine that already holds the data. In a cluster of thousands of cheap machines something is always broken, so a dead disk must be a non-event: Hadoop reads another copy and quietly creates a fresh third one. At this scale fault tolerance is not a feature, it is survival.

B3. The MapReduce model

INPUT --> MAP (parallel) --> SHUFFLE & SORT --> REDUCE (parallel) --> OUTPUT
           emit (k,v)          group by key       combine per key

You write only map and reduce; the framework provides parallelism, distribution, scheduling and failure recovery. The restriction is the point: because every job has the same shape, the framework solves the hard distributed-systems problems once, for everyone.

B4. Word count, and why the combiner decides everything

WORD COUNT — the "hello world" of MapReduce

  map(line):        for each word w in line:  emit(w, 1)
  reduce(w, list):  emit(w, sum(list))

  Input:  "the cat the dog"     "the cat sat"
  Map:    (the,1)(cat,1)        (the,1)(cat,1)(sat,1)
          (the,1)(dog,1)
  Shuffle: the -> [1,1,1]   cat -> [1,1]   dog -> [1]   sat -> [1]
  Reduce:  (the,3)          (cat,2)        (dog,1)      (sat,1)

Worked example — the shuffle is the whole cost. Word count over 1 TB of text, roughly 170 billion words, across 1,000 mappers. The map and reduce functions are trivial, so where does the time go?

WITHOUT a combiner:
  map emits ("the",1) once per occurrence
  intermediate pairs: 170,000,000,000
  at ~12 bytes each:  ~2 TB must cross the network in the shuffle

WITH a combiner (aggregate locally before sending):
  each mapper emits ("the", 4,213,905) — ONE pair per distinct word
  ~1,000,000 distinct words x 1,000 mappers x 12 bytes
                      ~12 GB crosses the network

Identical map and reduce functions; a 12× difference from one local aggregation step. Note what a combiner is: accumulate locally, combine once — the same principle as an OpenMP reduction, the fix for false sharing, and the CUDA reduction tree. A combiner is valid only when the reduce operation is associative and commutative (sum, max, count — but not average, for the reason in A6).

B5. Hadoop's flaw: the disk

MapReduce writes to disk between every step.

An iterative job (3 passes over the data):

  DISK -> Map -> Reduce -> DISK -> Map -> Reduce -> DISK -> Map -> Reduce -> DISK
          '--- a full disk round-trip between every stage — the killer ---'

For a single pass this is fine. But most analytics — and all machine learning — loop over the same data twenty or thirty times, which means thirty rounds of writing gigabytes to disk and reading them back. Recall from Unit II that RAM is roughly 100× faster than disk; that number is the whole plot.

B6. Apache Spark

Spark, the same iterative job:

  DISK -> [ load once ]  Map -> Reduce -> Map -> Reduce -> Map -> Reduce -> DISK
                         '------- all in memory, no disk between -------'

• RDD (Resilient Distributed Dataset) — a dataset split across the cluster's memory, rebuildable from its lineage if a machine dies. Wrapped by DataFrames, which behave like a distributed SQL table.
• Lazy DAG evaluation — transformations build a task graph (the dependency graph of Unit III); Spark optimises the whole plan and executes only when a result is actually requested.
• Lineage-based recovery — instead of replicating data, Spark records how each partition was computed and recomputes lost partitions on failure.

The honest nuance: Hadoop is not dead. HDFS remains a common storage layer and giant single-pass jobs still suit MapReduce. But for iterative and interactive work, Spark won. Twenty years of one idea: Google's MapReduce paper (2004) → Hadoop (2006) → Spark (2014) → cloud data platforms — split the data, map in parallel, shuffle by key, reduce in parallel, getting faster and easier the whole way.

Part C — Real-Time Systems & Recent Trends

C1. When being on time is being correct

A self-driving car that computes the correct braking decision 50 ms too late has computed the wrong decision. This is a deliberate reversal of the course's usual framing: Unit I established that parallelism buys throughput rather than latency. Real-time systems are the exception — here, guaranteed and predictable latency is the entire point, and determinism is prized over average speed. A system with a worse average response but a bounded worst case is the better real-time system.

C2. Hard vs soft real-time

Where parallelism appears in real-time systems:

• Cars (ADAS) — camera, radar and LiDAR fused in parallel; perception, planning and control run concurrently, each with its own deadline.
• Phones (big.LITTLE) — large power cores plus small efficient cores. This is the asymmetric multiprocessing (AMP) of Unit II, adopted for battery life rather than raw speed.
• RTOS scheduling — priority-based preemptive scheduling that optimises worst-case timing rather than average. Predictable beats fast.

C3. Schedulability — RMS and EDF

Real-time is the one place in this course where you can prove on paper, before running anything, that a system will be fast enough. For a set of n periodic tasks, task i having period T_i and worst-case execution time C_i, the total processor utilisation is U = Σ C_i/T_i.

RATE-MONOTONIC SCHEDULING (RMS)
   Fixed priority: shorter period = higher priority.
   Guaranteed schedulable if   U <= n( 2^(1/n) - 1 )
   for n = 3:                  U <= 3(1.2599 - 1) = 0.779
   we have U = 0.89            -> test FAILS, no guarantee

EARLIEST-DEADLINE-FIRST (EDF)
   Dynamic priority: whichever task's deadline is nearest runs next.
   Guaranteed schedulable if   U <= 1
   we have U = 0.89            -> GUARANTEED to meet every deadline

Note carefully that the RMS bound is sufficient but not necessary: failing it does not prove the task set is unschedulable, only that this simple test cannot guarantee it. EDF's bound of U ≤ 1 is both necessary and sufficient, which is why EDF is called optimal for single-processor periodic scheduling.

C4. Federated learning

Federated learning trains a shared machine-learning model across many devices holding local data, without that data ever leaving the device. It is the course's ideas assembled at planetary scale.

ONE FEDERATED ROUND

   +---------------------------------------------+
   |            CENTRAL SERVER (model)           |
   +---------------------------------------------+
        |  (1) send the current model to devices
        v           v           v           v
   +--------+  +--------+  +--------+  +--------+
   |Phone A |  |Phone B |  |Hospital|  |Phone D |
   | local  |  | local  |  | local  |  | local  |   (2) each trains
   | data   |  | data   |  | data   |  | data   |       LOCALLY on its
   +--------+  +--------+  +--------+  +--------+       OWN private data
        |           |           |           |
        +------ (3) send back ONLY the updates -------+
                    (weight changes / gradients —
                     never the raw data)
                            v
   +---------------------------------------------+
   |   SERVER AGGREGATES updates -> new model    |   (4) Federated
   |   (Federated Averaging: a weighted mean)    |       Averaging
   +---------------------------------------------+

Worked example — why you cannot centralise the data. Train a photo model across 1,000,000 phones, each holding about 1,000 photos of 2 MB. The arithmetic settles it before any privacy argument does.

Two petabytes at 100 Gb/s — about the fastest link you could realistically buy — takes roughly two days of continuous transfer, and that is before you have paid to store and secure it. Federated learning moves about 100× less data and removes the legal liability entirely. It is not primarily a privacy feature; it is the only arithmetic that works.

Why it is hard: devices have wildly unequal data (non-IID), unequal compute, and drop offline mid-round — load imbalance and fault tolerance from Units III and V, at the scale of a billion stragglers. It is nevertheless deployed in production, in mobile keyboard prediction and in cross-hospital medical models.

C5. Edge computing

Edge computing performs computation near where the data is produced — on the phone, in the car, at the 5G tower — rather than in a distant cloud. The benefits are lower latency, better privacy and less bandwidth consumed. It is Part B's "move the computation to the data" principle pushed all the way out to the device.

C6. Distributed AI training — three parallelisms at once

Large model training uses all three simultaneously. Note that these are exactly the data, task and pipeline decompositions of Unit I, reappearing at the largest scale computing currently operates at — and that data-parallel training's gradient-averaging step is an Allreduce (Unit IV).

C7. The one continuous idea

  thread -> core -> GPU -> node -> cluster -> data centre -> the planet
    |        |       |       |         |            |             |
  OpenMP   multi-  CUDA /   MPI      MPI /      MapReduce /   Federated
  thread   core     SIMT   ranks    clusters      Spark        learning

  "Split the work into independent pieces, run them at once,
   keep coordination cheap, and combine the results."

              ... the SAME idea, at a bigger and bigger scale.

Quick recall

Monte Carlo pi      pi ~= 4 x (darts inside circle) / (total darts)
Utilisation         U = sum of C_i / T_i
RMS bound           U <= n( 2^(1/n) - 1 )      n=3 -> 0.779, limit 0.693
EDF bound           U <= 1                     (optimal, uniprocessor)
Halo, 1-D strips    2 edges x 1000 = 2,000 cells  -> 20% overhead
Halo, 2-D blocks    4 edges x 100  =   400 cells  ->  4% overhead
HDFS                block ~128 MB, replication factor 3
Shuffle w/o combiner  ~2 TB, ~36 min   |   with combiner ~12 GB, ~3 min
Spark vs Hadoop     10-100x faster on iterative jobs (RAM ~100x disk)

Self-check

Answer each out loud before opening it.