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 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)    |
   +---------+---------+

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

Worked Example: The Halo Tax

A 1000×1000 weather grid on 100 processors. Every processor does the same amount of work either way — 10,000 cells. The only question is the shape of its piece.

  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
       = 2000 cells exchanged              = 400 cells exchanged

1-D strips:  comm/compute  =  2p / N          grows LINEARLY with p
2-D blocks:  comm/compute  =  4√p / N         grows with the SQUARE ROOT

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
   +-------------------+

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

Two Poles of Parallelism

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.

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

Worked Example: The Shard Key Decides Everything

An orders table across 10 shards, taking 10,000 writes per second. Each shard can handle 2,000/s. Three candidate shard keys.

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

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?

Worked Example: Two Ways to Join, 1000× Apart

Join a 1 TB orders table to a 10 MB countries table, on 100 nodes. Both tables are sharded by something unrelated to the join key.

network traffic
  = 1 TB + 10 MB
  ~ 1 TB across the network

network traffic
  = 10 MB x 100 nodes
  = 1 GB across the network

OLAP Warehouses & the Big Picture

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.

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?"