Unit V — Applications of Parallel Computing

Scientific Computing & Parallel Databases

Session 13 • 2311CSC501J — Parallel Processing

What You'll Learn

How simulations split the world across processors
Halo exchange & Monte Carlo methods
Sharding & shared-nothing databases
Parallel queries, joins & why OLAP scales

"A weather model and a data warehouse are the same idea in different clothes: partition, compute locally, combine."

— The through-line of this course

Simulating the World

You can't put a hurricane in a lab. So you simulate it: chop the physical world into a grid of tiny cells, store each cell's state, and step time forward — every cell updates from physics and its neighbors.

Domain	What's on the grid	Who uses it
Weather & climate	Atmosphere in 3D cells: temp, pressure, wind	IMD, ECMWF, NOAA
CFD / aerodynamics	Air over a wing or car body	Boeing, F1, ISRO
Molecular dynamics	Positions & forces of atoms	Drug discovery
Astrophysics	Gas & dark matter under gravity	Cosmology

Billions of cell-updates per step, thousands of steps. One machine takes weeks — but tomorrow's forecast can't wait. This is why supercomputers were invented.

Domain Decomposition

Split the grid across processors — each owns a block of space and simulates only its own cells. This is Session 07's Partition step, made physical.

The atmosphere over India, split across 4 processors

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

The problem: to update a cell you need its neighbors' values — but the cells on the edge of P0's block have neighbors living on P1, P2, and P3. So they must talk.

Halo Cells & the Trade-off

Each processor keeps a one-cell border copy of its neighbors' edges — the halo (ghost cells). Every step: exchange edges, then update.

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

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

Computation

Local to each block — scales beautifully.

Halo exchange

Communication — the enemy (Session 04).

Want fat blocks, thin seams. A bigger block has more interior work per unit of border — that's PCAM's Agglomeration step (Session 07). Don't be chatty.

Monte Carlo: π from Random Darts

Some science needs no neighbors at all. Monte Carlo answers questions by averaging many independent random samples.

   +-------------------+     Square area  = (2r)^2 = 4r^2
   |    . . * . . *    |     Circle area  = π r^2
   |   . ( * * * ) .   |
   |  .  (* * * *) .*  |     inside / total  ->  πr^2 / 4r^2  =  π/4
   |   . ( * * * ) .   |
   |    . * . . * .    |     so   π  ≈  4 × inside / total
   +-------------------+

Every dart is independent — split 10M darts across 8 cores, each throws 1.25M, then just sum the inside-counts (one reduction, Session 10). Near-perfect linear speedup.

Live demo: examples/01-monte-carlo-pi.html — watch π appear out of randomness.

Two Poles of Parallelism

Tightly coupled

Weather model.

Constant halo exchange between neighbors every step. Communication-bound. Hard.

Embarrassingly parallel

Monte Carlo.

Samples never talk. Almost no serial fraction → near-linear speedup. Easy.

Embarrassingly parallel = little or no communication between workers. Rendering movie frames, resizing a million images, grading 100 exams, hashing files — the jobs you love, because they just shard.

Callback to Amdahl (Session 08): almost no serial fraction is exactly why these scale near-perfectly.

Parallel Databases: One Box Isn't Enough

A table with two billion rows won't scan — or even fit — on one machine. Scale up (bigger box, has a ceiling) or scale out (more boxes, no ceiling). Parallel databases scale out.

Architecture	What's shared	Scales?
Shared-memory	One box, all cores share RAM & disk	To one machine's limit
Shared-disk	Separate CPUs, one shared storage	Storage bottlenecks
Shared-nothing	Nothing — each node owns its slice	Yes — add nodes

Shared-nothing: each node has its own CPU, RAM, disk; nodes talk only over the network. No shared resource to contend on — the distributed-memory model (Session 02) that makes MPI & databases cousins.

Sharding & the Shard Key

Sharding = splitting a table's rows across nodes (horizontal partitioning). Pick a shard key and a rule.

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

Hash sharding

Even spread, no hot spots. Great for key lookups, bad for range scans.

Range sharding

A–F, G–M… Great for ranges, risks a hot shard.

War story: shard by region and 80% of rows land in one region → one shard does all the work while the rest idle. That's load imbalance (Session 09) in a database costume. Pick a key that spreads evenly.

Parallel Query Execution

A query fans out to every shard at once; each scans only its slice in parallel; a coordinator merges the partials.

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

                    Coordinator
                   /     |      \      (1) fan-out to all shards
              Shard0   Shard1   Shard2
               scan     scan     scan  (2) each scans in parallel
               =12M     =15M     =11M
                   \     |      /
                    Coordinator          (3) merge: 12M+15M+11M
                        = 38M            = 38M, one answer

This is fan-out / fan-in — the same scatter/gather as MPI (Session 11) and the map-reduce of Session 14. COUNT/SUM/MIN/MAX are reductions.

Gotcha: you can't average the averages — each shard returns SUM and COUNT; divide at the end.

Live demo: examples/02-database-sharding.html

Parallel Joins — the Hard One

A row on shard 0 may need to match a row on shard 2. How do you join tables scattered across machines?

Co-located join

Both tables sharded on the join key → matches already on the same node. Zero network. The dream.

Shuffle join

Not co-partitioned → re-send data over the network, re-partitioned by join key. Expensive.

Broadcast join

One table tiny? Copy it to every node instead of shuffling the big one.

This is why the shard-key choice matters so much. Shard both tables on the join key and a slow report goes from minutes to seconds — a real lever a CTO pulls.

OLAP Warehouses & the Big Picture

OLTP

Live app DB. Millions of tiny reads/writes. Optimized for latency per transaction.

OLAP

Warehouse (BigQuery/Snowflake/Redshift). Scan-everything queries. Optimized for throughput.

A big scan is the perfect parallel workload — split a trillion rows across a thousand machines, scan in parallel, merge. That's Gustafson (Session 08) in production: bigger data in the same time.

Step	Science	Database
Partition	Split the grid	Shard the table
Compute	Update my cells	Scan my shard
Communicate	Halo exchange	Fan-out / shuffle
Combine	Assemble the field	Merge partials

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

Recap & What's Next

Key Takeaways

Scientific computing splits a grid across processors (domain decomposition) and exchanges halo cells each step.
Monte Carlo (darts → π) is embarrassingly parallel — independent samples, near-perfect speedup.
Parallel databases use shared-nothing nodes and sharding; queries fan out and a coordinator merges.
Joins are cheap when co-located on the join key, else you pay for a shuffle or broadcast.
OLAP warehouses are massively parallel because a big scan is the ideal parallel job. Partition → compute → combine.

Homework

Explain to a non-technical friend how a weather forecast and BigQuery are "the same idea."
Look up one real supercomputer (Fugaku/Frontier/Aurora) — its core count and its science.
Come ready: "Word-count over a terabyte across 100 machines — how do you split and combine it?"

Next session: Big Data & Parallel Processing

Hadoop, MapReduce & Spark — "partition → compute → combine" as a button anyone can press.